IMO2007/1

[Simo_the_wolf]

Siano $ a_1, a_2, ... , a_n $ numeri reali. Per ogni $ i $ tra $ 1 $ ed $ n $ (compresi) definiamo:

$ \displaystyle d_i = max \left\{ a_j : 1\leq j \leq i \right \} - min \left\{ a_j : i\leq j \leq n \right \} $

e poniamo

$ \displaystyle d=max \left\{ d_i : 1\leq i \leq n \right\} $.

(a) Dimostrare che, per qualsiasi numeri reali $ x_1\leq x_2 \leq ... \leq x_n $, si ha

$ \displaystyle max \left\{ |x_i-a_i| : 1\leq i \leq n \right \} \geq \frac d2 $. (*)

(b) Dimostrare che esistono dei numeri reali $ x_1\leq x_2 \leq ... \leq x_n $ tali che in (*) vale l'uguaglianza.


Good luck!

[teppic]

Up!

Proprio nessuno dei giovani che si cimenti? Gli IMO1 sono fattibili!

[TADW_Elessar]

Mi sa che l'ho già proposto io pochi giorni fa

[salva90]

Forse ci sono... mi accorgo però che si capisce maluccio...

raffiguriamo le due n-uple di reali su un' unica retta ordinata.

d diventa la lunghezza di un segmento che ha $ ~a_h $ come estremo sinistro e $ ~a_k $ come destro. Per definizione dei d_i dev'essere $ h>k $. abbiamo vari casi:

- $ ~x_k $ sta fuori del segmento, a sinistra. in tal caso la tesi è ovvia, in quanto la sua distanza da $ ~a_k $ è maggiore di d e non solo di d/2

- $ ~x_k $ sta fuori del segmento, a destra. In tal caso $ ~x_h $ sta ancora più a destra, e di nuovo il segmento di estremi $ ~x_h, ~a_h $ è più lungo di d

- $ ~x_k $ sta dentro al segmento, nella metà sinistra. in questo caso il segmento di estremi $ ~x_k, ~a_k $ è più lungo di d/2

- $ ~x_k $ sta dentro il segmento, nella metà destra. allora $ ~x_h $ sta ancora più a destra, e il segmento di estremi $ ~x_h, ~a_h $ è più lungo di d/2

il punto b dovrebbe seguire facilmente, ora, ma non ho voglia di farlo...

edit: ora dovrei avere sistemato tutto (spero)

[teppic]

Forse ci sono... mi accorgo però che si capisce maluccio...

Mi sa infatti che l'hai capito male. Ad esempio...

è palese che possiamo non considerare i $ ~d_i $ negativi, che creano solo casino.

Per definizione i $ d_i $ sono tutti non negativi.

i $ ~d_i $ sono segmenti che ha come estremo destro un certo $ ~a_i $ e come estremo sinistro il più lontano da esso $ ~a_j $ esistente, con$ j>i $.

Non è detto che l'estremo destro sia $ a_i $.

[salva90]

EDIT: ok, visto... al massimo sono nulli, ma non negativi... beh tanto meglio, la dim scorre ugualmente

per quanto riguarda la seconda obiezione: lo so, avrei dovuto usare un altro indice, ma non mi sembra che la dim cada su questo

[Hammond]

Allora... rappresentiamo la situazione su un piano cartesiano, con gli indici 1, 2, ... , n sull'asse x e i rispettivi valori $ a_1, a_2, ... , a_n $ sull'asse y.
Visto così d è il massimo "salto" discendente tra due elementi della successione (che non è necessariamente unico).
Siano $ A < B $ gli indici corrispondenti a uno di questi salti massimi, così che $ a_A - a_B = d $.

a)
Consideriamo solo gli $ x_i $ di indice compreso tra A e B; abbiamo $ (a_A - x_A) + (x_B - a_B) = d + (x_B - x_A) \ge d $ per la crescenza degli $ x_i $. Perciò almeno uno tra $ (a_A - x_A) $ e $ (x_B - a_B) $ è maggiore o uguale a d/2.

b)
Costruiamo una successione di $ x_i $ che vada bene.
Partiamo con $ x_1 = a_1 - d/2 $ e manteniamo x costante finché non troviamo un elemento $ a_{k1} $ tale che $ a_{k1} - x > d/2 $. A quel punto poniamo $ x_{k1} = a_{k1} - d/2 $ e proseguiamo ancora con x costante finché non troviamo $ a_{k2} $ tale che...
In pratica il risultato sarà una successione non decrescente costante a tratti. Dimostriamo che funziona davvero:
- non ci sono $ a_i $ "troppo maggiori" del rispettivo $ x_i $ per il modo stesso in cui la successione x è stata costruita;
- non ci sono $ a_i $ "troppo minori" perché se così fosse avremmo un salto discendente maggiore di d;
quindi la differenza massima è esattamente d/2.

Ok, non è chiarissima, ma mi basterebbe che fosse giusta

[teppic]

@Salva: ok la parte a), ma la parte b) non è ovvia.

@Hammond: eccellente la parte a), giusta l'idea della parte b), ma nota quanto pesante è dimostrare formalmente che la successione funziona.

[salva90]

tento di buttare giù la parte b... vediamo che viene fuori

PREMESSA: ANCHE QUESTA E' SCRITTA MALISSIMO. più tardi la sistemerò (correggerò le ca**ate che man mano troverò e la renderò più leggibile)

fino a che è possibile farlo senza contraddire la non decrescenza della sequenza, piazzo ogni $ ~x_i $ esattamente d/2 a sinistra del rispettivo $ ~a_i $.

Supponiamo che a un certo passo ciò non sia più possibile.
Sia $ ~a_k $ il punto più a destra finora considerato. Allora i successivi $ ~a_i $ (con $ ~i>k $ ) stanno al massimo a distanza d alla sua sinistra. Pertando, piazzando ogni successivo x in coincidenza con $ ~x_k $ manteniamo soddisfatte le ipotesi (e ciò è possibile perchè $ ~x_k $ dista al massimo d/2 da ogni $ ~a_i $_ $ ~i>k $ _ posto alla sua sinistra). Invece, se un certo $ ~a_j $ è posto a destra rispetto ad $ ~a_k $, non abbiamo alcun problema: mettiamo il corrispondente $ ~x_j $ a d/2 alla sua sinistra, e ripetiamo per i successivi punti il passo precedente, con $ ~a_j $ nel ruolo precedentemente occupato da $ ~a_k $

Si è cosi dimostrato che riusciamo a collocare tutti gli x in modo che nessuno disti più di d/2 dal corrispondente a e che la non decrescenza della successione sia soddisfatta.