Dio disse che era combinatoria, e combinatoria fu

[bern-1-16-4-13]

sia $ABC$ un triangolo rettangolo in $A$. Dati $n$ punti interni al triangolo ($n\ge 2$) dimostrare che è possibile assegnargli in un certo ordine i nomi $P_1,...,P_n$ in modo che $$\sum_{i=1}^{n-1}{P_iP_{i+1}}^2\le BC^2$$.

[cip999]

Meno male che ci sei tu ad occuparmi il viaggio con questi problemi swag...

Testo nascosto:

Dato un insieme (non vuoto) di punti interni ad $ABC$, definiamo catena una qualunque spezzata aperta che passi una e una sola volta per ciascun punto dell'insieme. Chiamiamo poi valore di una catena la somma dei quadrati delle lunghezze dei segmenti di cui è composta.
Dimostriamo ora per induzione la seguente tesi più forte di quella richiesta: dati $n \ge 2$ punti interni a un triangolo rettangolo $PQR$ o sul suo bordo, esiste sempre una catena che passa per questi punti tale che:

1. il suo valore sia $\le QR^2$ (dove $QR$ è l'ipotenusa);
2. se uno degli $n$ punti coincide con $Q$, quel punto è un estremo della catena;
3. se uno degli $n$ punti coincide con $R$, quel punto è un estremo della catena.

Supponiamo quindi di avere i nostri $n$ punti in $PQR$. Se uno di questi coincide con $P$, siamo felici e non facciamo nulla; altrimenti, aggiungiamo temporaneamente un $(n + 1)$-esimo punto magico coincidente con $P$. Sia quindi $H$ il piede dell'altezza uscente da $P$. Costruiamo due insiemi di punti $\mathfrak{S}_1$ ed $ \mathfrak{S}_2$ nel modo seguente: il punto che coincide con $P$ sta in tutti e due gli $\mathfrak{S}_i$; i punti interni a o sul bordo di $PQH$ vanno in $\mathfrak{S}_1$; tutti i restanti punti vanno in $\mathfrak{S}_2$. Ora, per ipotesi induttiva esistono:

• una catena dei punti di $\mathfrak{S}_1$ di valore non superiore a $PQ^2$, che ha un estremo in $P$ e l'altro eventualmente in $Q$, se c'è un punto che coincide con tale vertice;
• una analoga catena dei punti di $\mathfrak{S}_2$, di valore non superiore a $PR^2$.

Ma allora possiamo "concatenare" queste due catene nel loro estremo comune $P$ per ottenere una lunga catena passante per tutti i punti. Questa catena - chiamiamola $\mathcal{C}$ - soddisfa la condizione sugli estremi e ha valore $$v \le PQ^2 + PR^2 = QR^2$$
A questo punto, se tra gli $n$ punti magici iniziali ce n'era uno coincidente con $P$ abbiamo finito. Altrimenti, sia $P_i$ il punto magico: se lui è un estremo di $\mathcal{C}$, semplicemente lo rimuoviamo e otteniamo una catena di valore minore; se no, siano $P_{i - 1}$ e $P_{i + 1}$ i due punti collegati direttamente a $P_i$. Costruiamo la catena $\mathcal{C}'$ ottenuta rimuovendo $P_i$ e unendo con un segmento $P_{i - 1}$ e $P_{i + 1}$. Il valore di questa nuova catena è $$v' = v + P_{i - 1}P_{i + 1}^2 - P_iP_{i - 1}^2 - P_iP_{i + 1}^2 \stackrel{(\star)}{=} v - 2P_iP_{i - 1} \cdot P_iP_{i + 1} \cdot \cos\widehat{P_{i - 1}P_iP_{i + 1}}$$ (dove $(\star)$ è Carnot). Ma chiaramente $\widehat{P_{i - 1}P_iP_{i + 1}} \le 90^{\circ}$ e quindi $v' \le v \le QR^2$, il ché conclude.
Ah, il passo base è banale (tipo se ho un solo punto coincidente con $P$ ritorno la "catena nulla" di valore $0$).

[bern-1-16-4-13]

Vai perfetta

Edit: Come giustamente Cip999 mi fa notare per potere applicare l'ipotesi induttiva occorre che al momento della divisione in due triangoli uno dei due non sia completamente vuoto. D'altronde non è un grosso problema poiché potremo reiterare la divisione, e questa situazione non si può verificare all'infinito

[AlexThirty]

Vai perfetta

Edit: Come giustamente Cip999 mi fa notare per potere applicare l'ipotesi induttiva occorre che al momento della divisione in due triangoli uno dei due non sia completamente vuoto. D'altronde non è un grosso problema poiché potremo reiterare la divisione, e questa situazione non si può verificare all'infinito

Mini-Spoiler