Secvente si partitii

[Filip Chindea]

Fie \( A_0 = (a_1, ..., a_n) \) o secventa de numere reale. Pentru fiecare \( k \) natural, \( A_k = (x_1, ..., x_n) \),

(a) Alegem o partitie \( (I, J) \) a intregilor pozitivi cel mult \( n \) astfel ca expresia

\( \left| \sum_{i \in I} x_i - \sum_{j \in J} x_j \right| \)

sa atinga valoarea minima (permitem ca \( I \) sau \( J \) sa fie vide.)

(b) Consideram \( A_{k+1} = (y_1, ..., y_n) \) cu \( y_i = x_i + 1 \) pentru \( i \in I \) si \( y_j = x_j - 1 \) daca \( j \in J \).

Aratati ca exista un rang \( k \) astfel ca o componenta a secventei \( A_k \) sa fie cel putin \( n/2 \).

[ IMO Shortlist 2007, C4, si Teste tip OIM 2008, Problema 3/Test 4 ]