$I$ e $J$
Inviato: 08 giu 2017, 22:33
Sia $n$ un intero positivo. Partiamo da una $n$-upla $A_0 = (a_1, \: \dots, \: a_n)$ e definiamo ricorsivamente le $n$-uple $A_1, \: A_2, \: \dots$: data $A_k = (x_1, \: \dots, \: x_n)$, costruiamo $A_{k + 1}$ in questo modo.
Per prima cosa, scegliamo insiemi disgiunti $I$ e $J$ tali che $I \cup J = \{1, \: \dots, \: n\}$, con la proprietà che l'espressione $$\left\lvert\sum_{i \in I} x_i - \sum_{j \in J} x_j\right\rvert$$ abbia il minimo valore possibile (poniamo la somma vuota uguale a $0$). Se ci sono più coppie $(I, \: J)$ valide, ne scegliamo una qualunque.
Poi, definiamo $A_{k + 1} = (y_1, \: \dots, \: y_n)$ con $y_i = x_i + 1$ se $i \in I$ e $y_j = x_j - 1$ se $j \in J$.
Dimostrare che, per qualche $k$, $A_k$ contiene almeno un elemento $x$ tale che $\displaystyle \lvert x\rvert \ge \frac{n}{2}$.
Per prima cosa, scegliamo insiemi disgiunti $I$ e $J$ tali che $I \cup J = \{1, \: \dots, \: n\}$, con la proprietà che l'espressione $$\left\lvert\sum_{i \in I} x_i - \sum_{j \in J} x_j\right\rvert$$ abbia il minimo valore possibile (poniamo la somma vuota uguale a $0$). Se ci sono più coppie $(I, \: J)$ valide, ne scegliamo una qualunque.
Poi, definiamo $A_{k + 1} = (y_1, \: \dots, \: y_n)$ con $y_i = x_i + 1$ se $i \in I$ e $y_j = x_j - 1$ se $j \in J$.
Dimostrare che, per qualche $k$, $A_k$ contiene almeno un elemento $x$ tale che $\displaystyle \lvert x\rvert \ge \frac{n}{2}$.