[tex]n\mid\sum_{i\in I_j}{a_i}[/tex],[tex]\forall I_j[/tex]

[jordan]

Dato un intero $ n>1 $, siano fissati degli interi $ a_1,a_2,\ldots,a_n $ tali che $ n \nmid a_i $ per ogni $ 1\le i\le n $ e $ \displaystyle n \nmid \sum_{1\le i\le n}{a_i} $.

Dimostrare che esistono almeno $ n-1 $ sottoinsiemi distinti e non vuoti $ I_j \subseteq \{1,2,\ldots, n\} $ tali che $ \displaystyle n\mid \sum_{i\in I_j}{a_i} $ per ogni $ j $.

[dario2994]

Problema figo Ci ho messo un bel pezzo ma alla fine l'ho avuta vinta io

Lemma che vorrei Sia $A$ un insieme con $|A|=n\ge 2$. Siano $A_1,A_2,\dots, A_k$ con $k<n-1$ sottinsiemi di $A$ tali che $\forall i:\ 1<|A_i|<n$. Esiste un ordinamento degli elementi di $A$ tale che se ne prendo alcuni consecutivi non sono mai uno degli $A_i$.
Dim. (è scritta un po' male... è il tipo di dimostrazione che scritta a mano esce molto meglio)

Testo nascosto:

Dimostro il lemma per induzione su $n$:

• Passo base: $n=3$ C'è al massimo un sottinseime ed ha 2 elementi... basta metterli per primo e per ultimo e ho trovato l'ordinamento.
• Passo induttivo: $n->n+1$ (sono nel caso $n+1$) Siano $p,q$ rispettivamente il numero degli $A_i$ con cardinalità uguale a 2 e uguale a $n$. Vale $p+q\leq k<n$ poi chè i sottinsiemi sono distinti.
  Esistono almeno $n+1-p$ numeri contenuti in alpiù un sottinsieme di cardinalità $2$.
  Esistono almeno $n+1-q$ contenuti in ogni sottoinsieme di cardinalità $n$.
  Ma poichè $(n+1-p)+(n+1-p)=2(n+1)-(p+q)>n+1$ allora deve esistere un numero che non sta in 2 sottinsiemi da 2 elementi e sta in tutti quelli da $n$ elementi... Sia $x$ uno degli elementi con questa proprietà. Se $x$ è in un sottinsieme di cardinalità $2$ allora chiamo quel sottinsieme $X$, altrimenti scelgo un sottinsieme a caso e lo chiamo $X$ (se non c'è manco un sottinsieme il problema è banale... prendo un ordinamento a caso e funziona).
  Ora considero $B=A\backslash\{x\}$ e la famiglia dei sottinsiemi $B_1,B_2,\dots B_{k-1}$ creati a partire dagli $A_i$ tranne $X$ a cui se era presente viene tolto $x$. Per tutta la costruzione di prima $B$ e i $B_i$ rispettano ancora la costruzione ma allora per ipotesi induttiva riesco a ordinarli come richiesto... ora non resta che riaggiungere $x$.
  Dovunque vado a piazzare $x$ di sicuro non posso trovare uno degli $A_i$ in modo consecutivo (a meno che non sia $X$) perchè già nell'ordinamento senza $x$ ci stava.
  Invece devo fare in modo da piazzare $x$ senza che si crei $X$... Se $X\backslash{x}$ è già non presente nell'ordinamento... allora è facile il mio compito... perchè per quanto detto alla riga precedente posso piazzare $x$ dove mi pare... Se è presente allora esiste un blocco consecutivo che crea $X\backslash{x}$... ma allora basta mettere $x$ non dentro o accanto a quel blocco consecutivo e ce la faccio perchè il blocco consecutivo è lungo al massimo $n-1$ e allora non può essere adiacente a entrambi gli estremi della stringa... Quindi piazzo $x$ all'estremo a cui non è adiacente e ho trovato un ordinamento buono per n+1

Armato con il lemma che vorrei dimostro il problema.
Dimostro che dati $k<n-1$ sottinsiemi $I_1,\dots I_k$ come richiesti dalla tesi riesco anche a trovare $I_{k+1}$. E da questo la tesi segue.
Per il lemma che vorrei, sapendo dalle ipotesi del problema che $1< |I_j|<n$, riesco a trovare un ordinamento degli ${1,2\dots,n}$ tale che nessun $I_j$ vi compare in modo consecutivo. Sia $f(1),f(2),\dots f(n)$ questo ordinamento.
Definisco $\displaystyle S_j=\sum_{i=1}^ja_{f(i)}$.
Per il principio dei piccioni esistono $0\leq i<j\leq n$ tali che $S_i\equiv S_j\pmod{n}$. Ma allora pongo $I_k=\{f(i+1),f(i+2),\dots f(j)\}$. E questo è, per l'ordinamento scelto, distinto dagli altri $I_j$ ed inoltre rispetta le richieste del problema.

p.s. Davvero un bel problema... Da dove esce?
p.p.s. Voglio aggiungere che in effetti se si toglie un'ipotesi a caso il problema risulta falso... ed è figo