SNS 2017 n.3

[Gandalf73]

Qui nel forum anche se non titolato ho scovato il testo di un esercizio assegnato nell'anno 2017 nella prova si ammissione alla SNS, precisamente il numero 3.
Riporto il testo per comodità:

Siano $ d_1,....,d_n $ numeri reali positivi, con $ n≥2 $.
Si trovi una condizione necessaria e sufficiente, affinchè esista una successione $ p_0,....,p_n $ di punti del piano euclideo tali che:
Per ogni $ i=1,...,n, $ la distanza tra $p_i e p_(i−1) $ è di di;
$ p_n=p_0 $.

La soluzione proposta in un vecchio thread:
https://www.matematicamente.it/forum/vi ... 0#p8338124

Mi chiedo se non vi sia una una strada meno "articolata" per la dimostrazione della condizione sufficiente, consultabile nello svolgimento proposto da .Ruben.
Intendo qualcosa che abbia a che fare con la geometria euclidea piana riguardante i poligoni...
Un saluto ed un grazie a tutti.

[Quinzio]

Siii... ok, credo che si possa trovare una strada meno articolata.
Non c'e' bisogno di tante formule.
La dimostrazione che metto qui sotto e' prolissa perche' ho giustificato praticamente tutti i passaggi, ma i concetti che stanno alla base sono abbastanza intuitivi.
Oserei dire che e' relativamente facile da capire in quanto discorsiva e poco densa di formule, ma rimango a disposizione per chiarimenti.
Di dimostrazioni piu' semplici, onestamente non me ne sono venute in mente.

Ormai e' chiaro che la condizione necessaria e sufficiente che soddisfa il problema e':

$ not\exists d_i: d_i > sum_({: ( 1 \leq j \leq n ),( j \ne i ) :} ) d_j$

Non spaventatevi.
Questa scritta qui sopra e' un modo forbito ed aulico per dire che "non esiste una distanza che sia maggiore della somma delle altre". Il simbolo $\not$ e' la negazione, "non esiste". Tutto qui.

Procediamo prima con la dimostrazione che la condizione e' necessaria, e poi che e' sufficiente.

Per dimostrare che la condizione supposta (posta qui sopra) sia necessaria, si procede con una reductio ad absurdum ossia con una dimostrazione "per assurdo".
In pratica si nega la condizione che e' stata proposta e poi si fa vedere un controesempio, che allora mostra che la negazione della condizione e' falsa. Ne consegue che la condizione deve essere vera necessariamente .
In altre parole, se nego la negazione di A, allora A deve necessariamente essere vera.

Quindi la negazione della condizione proposta e'

$ \exists d_i: d_i > sum_({: ( 1 \leq j \leq n ),( j \ne i ) :} ) d_j$

Ora facciamo vedere il controesempio...
si costruisca una spezzata con i punti
$p_i, ..., p_n, p_1, ..., p_{i-1}$.
Notare che la spezzata non deve "chiudersi", ma le estremita' sono libere.
In pratica ho costruito una spezzata con dei segmenti che hanno le lunghezze $d_{i+1}..., d_n, d_1, d_{i-1} $, tutte tranne quella maggiore della somma delle altre, che ha lunghezza $d_i$.
E' semplice da dimostrare che la distanza massima tra l'inizio e la fine della spezzata si realizza quando i segmenti sono tutti allineati, tutti "in fila". Questa affermazione va dimostrata e lo faremo in seguito[nota]da completare[/nota], ma intuitivamente e' molto chiara.
Per concludere, si deve solo far vedere come un segmento lungo $d_i$, piu' lungo della somma degli altri, non richiude la spezzata, perche' e' appunto piu' lungo.
Ovvero, anche dopo aver massimizzato la distanza tra l'inizio e la fine della spezzata, la spezzata e' troppo corta per ricongiungersi con il segmento lungo $d_i$.
Questo conclude la parte "necessaria".

Per dimostrare poi che la condizione proposta sia sufficiente, dobbiamo mostrare appunto che la condizione rende sempre possibile l'enunciato. La dimostrazione di questo punto procedera' in modo da costruire un triangolo con i punti sul piano e quindi mostrando che tale triangolo e' sempre possibile.

Chiamiamo $d_i$ la distanza maggiore.
Senza perdere di generalita', effettuiamo una rotazione degli indici in modo da portare l'indice generico $k$ in posizione $k'= (k+n-i)\ "mod"\ n$, ovvero gli indici ruotano fino a portare l'indice $i$ in posizione $n$.
Il segmento piu' lungo e' ora $d_n$.
Costruiamo di nuovo una spezzata uguale a quella fatta prima, composta da segmenti lunghi $d_1,..., d_{n-1} $, tutti tranne il piu' lungo.
I segmenti della spezzata sono tutti allineati sulla stessa retta, come prima.
I punti iniziale e finale della spezzata sono quindi $p_0$ e $p_{n-1}$.
Senza perdere di generalita' collochiamo $p_0$ nell'origine e gli altri punti sul semiasse positivo delle ascisse.
Con la scritta $x_k$ indichiamo l'ascissa del generico punto $p_k$
Troviamo quindi il punto $m$ tale che

1) $\forall q \ne m, |x_m - (x_{n-1}) /2| \leq |x_q - (x_{n-1}) /2| $.

In altre parole, il punto $p_m$ e' il piu' vicino al punto medio della spezzata.
Ora, dovremmo considerare entrambi i casi del valore assoluto $|x_m - (x_{n-1}) /2|$.
Noi proseguiremo con $|x_m - (x_{n-1}) /2| = x_m - (x_{n-1}) /2$ e lasciamo a chi legge in modo facile di rifare le stesse considerazioni per $|x_m - (x_{n-1}) /2| = -(x_m - (x_{n-1}) /2) $.

Abbiamo quindi che
$0 < |x_m - (x_{n-1}) /2| = x_m - (x_{n-1}) /2$

Riscriviamo la 1) con $q = m-1$, leviamo i valori assoluti[nota]Nel levare il modulo di
$x_m - (x_{n-1}) /2 \leq |x_{m-1} - (x_{n-1}) /2|$
la scelta obbligatoria e'
$x_m - (x_{n-1}) /2 \leq (x_{n-1}) /2 - x_{m-1}$

In caso contrario si avrebbe
$x_m - (x_{n-1}) /2 \leq x_{m-1} - (x_{n-1}) /2$
$x_m \leq x_{m-1} $
che e' contraddittorio in quanto l'ascissa di $x_m$ e' maggiore di quella di $x_{m-1}$[/nota] e otteniamo
$x_m - (x_{n-1}) /2 < (x_{n-1}) /2 - x_{m-1}$.

Con semplici passaggi otteniamo:
$x_m - (x_{n-1} - x_m ) < x_m - x_{m-1}$.

Ricordando che avevamo volutamente escluso dalla spezzata il segmento con la distanza maggiore, che avevamo chiamato $d_n$, possiamo completare la disuguaglianza precedente con:
$x_m - (x_{n-1} - x_m ) < x_m - x_{m-1} = d_m \leq d_n$.

Ora consideriamo un triangolo i cui lati sono $ABC$ e che sono lunghi:
$A = x_m$
$B = x_{n-1} - x_m $
$C = d_n$
Riscriviamo l'ultima disuguaglianza usando i lati del triangolo
$A - B \leq C$
ovvero
$A \leq B + C$.

L'esistenza di tale triangolo $ABC$ e' garantita dalla disuguaglianza triangolare, teorema che afferma che e' possibile costruire un triangolo di lati $ABC$ con $A \leq B + C$.
I punti $p_0, ..., p_n$ del problema (con la rotazione degli indici in modo che la distanza $d_n$ sia la maggiore) saranno quindi disposti in modo da formare il triangolo $p_0, p_m, p_{n-1}$.
Se $A = B + C$ si ha il caso particolare in cui i punti sono tutti allineati.

Questo conclude la parte sufficiente della dimostrazione e l'intera dimostrazione.

[vict85]

Perché hai scritto il messaggio in Analisi Matematica di Base?

Io comunque procederei così. Segno con \(\lVert \mathbf{p}_i - \mathbf{p}_{i-1} \rVert\) la distanza tra \(p_i\) e \(p_{i-1}\). Si ha ovviamente che \(\lVert \mathbf{p}_i - \mathbf{p}_{i-1} \rVert = \lVert \mathbf{p}_{i-1} - \mathbf{p}_{i} \rVert\). Geometricamente parlando, la notazione non è a caso, infatti \(\lVert \mathbf{p}_i - \mathbf{p}_{i-1} \rVert\) è effettivamente la norma del vettore \(\mathbf{p}_i - \mathbf{p}_{i-1}\) dove \(\mathbf{p}_i\) è il vettore da \(\mathbf{0}\) all'\(i\)-esimo punto. Non intendo usare l'algebra lineare, uso questa notazione solo per evitare l'uso della \(d\) per la distanza.
Uso inoltre la seguente terminologia: dico che \((p_0, p_1, p_2, \dotsc, p_n)\) è soluzione del problema \((d_1, d_2, \dotsc, d_n)\) se \(p_0 = p_n\) e \(\lVert \mathbf{p}_i - \mathbf{p}_{i-1} \rVert = d_i\) per ogni \(i\).

Il caso \(n = 2\) è banale: l'unica possibilità è che si abbia \(d_1 = d_2\). Infatti dalle ipotesi si ricava \( d_1 = \lVert \mathbf{p}_1 - \mathbf{p}_{0} \rVert = \lVert \mathbf{p}_{0} - \mathbf{p}_{1} \rVert = \lVert \mathbf{p}_{2} - \mathbf{p}_{1} \rVert = d_2\). Per l'esistenza mi basta considerare \(p_0 = (0,0)\) e \(p_1 = (0, d_1)\). Suppongo che per l'esistenza si possano persino usare gli assiomi della geometria euclidea.

Il caso \(n=3\) non è molto diverso. Infatti, fissati due punti ad una certa distanza, il terzo punto deve essere necessariamente nell'intersezione di due circonferenze. Quindi la condizione necessaria e sufficiente è che le due circonferenze abbiano intersezione non nulla. Questo avviene se \(d_1 \le d_2 + d_3\) e similmente per le altre distanze. Quindi la condizione è \(\forall i,\;d_i \le \sum_{j\neq i} d_j\). Sommando per \(d_i\) da entrambi i lati e dividendo per due si ha la seguente forma: \(\forall i,\;d_i \le \frac12 \sum d_i\). È più compatta ma trovo sia più difficile da lavorarci.

Il resto lo dimostrerò per induzione e ovviamente devo dividere la dimostrazione in due.

Dimostriamo prima di tutto che la condizione è necessaria, ovvero che se esiste una soluzione \((p_0, p_1, p_2, \dotsc, p_n)\) del problema \((d_1, d_2, \dotsc, d_n)\) allora si deve avere \(\forall i,\;d_i \le \sum_{j\neq i} d_j\). Supponiamo che valga per un certo \(N \ge 3\) e sia \(n = N+1\). Consideriamo quindi i primi 3 punti. Questi formano un triangolo, eventualmente degenere. Se \(d = \lVert \mathbf{p}_2 - \mathbf{p}_0 \rVert\), allora \((p_0, p_1, p_2)\) è soluzione del problema \((d_1, d_2, d)\) e \((p_0, p_2, \dotsc, p_n )\) è soluzione del problema \((d, d_3,\dotsc, d_n )\). Siccome \((d_1, d_2, d)\) è un problema di dimesione \(3\) e \((d, d_3,\dotsc, d_n )\) ha dimesione \(N\), entrambi soddisfano la condizione.
Si ricava quindi che \(d_1 \le d_2 + d \le d_2 + \sum_{i\ge 3} d_i = \sum_{i\ge 2} d_i\). Che \(d_2 \le d_1 + d \le d_1 + \sum_{i\ge 3} d_i = \sum_{i\neq 2} d_i\).
E che \( \forall i\ge 3,\;d_i \le d + \sum_{j\ge 3\wedge j \neq i} d_j \le d_1 + d_2 + \sum_{j\ge 3\wedge j \neq i} d_j = \sum_{j\neq i} d_j \). Quindi la condizione è necessaria per ogni \(N\).

Supponiamo che la condizione sia anche sufficiente per un certo \(N\ge 3\) ovvero che se \(\forall i,\;d_i \le \sum_{j\neq i} d_j\) allora il problema \((d_1, d_2, \dotsc, d_N)\) ammette una qualche soluzione \((p_0, p_1, p_2, \dotsc, p_N)\). Consideriamo quindi il problema \((d_1, d_2, \dotsc, d_n)\) e supponiamo che soddisfi \(\forall i,\;d_i \le \sum_{j\neq i} d_j\). Quello che voglio fare è di identificare un numero reale \(d\) e tre punti \(p_0, p_1, p_2\) tali che: [list=1][*:6ytl361r] \((p_0, p_1, p_2)\) è soluzione del problema \((d_1, d_2, d)\); [/*:m:6ytl361r][*:6ytl361r] \((d, d_3, \dotsc, d_n)\) soddisfa la condizione. [/*:m:6ytl361r][/list:o:6ytl361r]
Infatti, per ipotesi induttiva il problema \((d, d_3, \dotsc, d_n)\) avrà una soluzione e usando una trasformazione rigida mi è possibile fare in modo che i primi due punti della soluzione siano \(p_0\) e \(p_2\).
Il \(d\) che prendo è il massimo tra \(\lvert d_1 - d_2 \rvert\) e il massimo dei valori della forma \(d_i - \sum_{j\ge 3\wedge j \neq i} d_j\) per \(i\ge 3\). Questo massimo esiste perché tutti i valori sono più piccoli di \(d_1 + d_2\) (per via della condizione). L'esistenza di \(p_2\) deriva dalla considerazioni fatte sul caso \(n=3\).

È interessante osservare che questa dimostrazione proponga un effettivo algoritmo per calcolare una soluzione.

[Gandalf73]

Grazie a tutti per il prezioso aiuto/soluzione!
@vict85: non sapevo in quale sezione inserirla francamente.
Chiedo aiuto a qualche admin nel caso desiderasse migrare il post in una sezione più idonea e di più rapida accessibilità.
Grazie ancora!