$I$ e $J$

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

$I$ e $J$

Messaggioda cip999 » 04/06/2017, 16:02

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}$.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti