Cortona 95

[BorisM]

Siano $a_{1} a_{2}...a_{10}$ dei numeri interi. Dimostrare che è possibile trovare dei numeri $x_{1} x_{2}...x_{10}$ appartenenti all' insieme {${-1,0,1}$} tali che $a_{1}x_{1}+a_{2}x_{2}...a_{10}x_{10}$ sia divisibile per $1001$.

Vi posto questo esercizio perchè la soluzione che ho dato non mi sembrava fosse sbagliata ma allo stesso tempo mi sembrava troppo banale perchè potesse funzionare quindi ho deciso di controllare le soluzioni proposte dalle schede olimpioniche ma il risultato è del tutto diverso dal mio.
Vi propongo la soluzione che avrei dato (non mi sparate se quello che è scritto qui sotto è una schifezza assurda ):
Semplicemente se la somma algebrica degli $a_{1} a_{2}...a_{10}$ è un multiplo di $1001$ sono a cavallo perchè sceglierò per $x_{1} x_{2}...x_{10}$ tutti $1$. In caso contrario sceglierò tutti $0$ e quindi otterò come somma $0$ che è multiplo di $n$.
Sinceramente non capisco dove la mia soluzione faccia acqua..l' unico dubbio che mi viene è: forse avrei dovuto usare ogni elemento dell' insieme {${-1,0,1}$} almeno una volta?

[<enigma>]

A questo punto chi ti impedisce di sceglierli tutti nulli comunque? Perché sia non banale una buona condizione può essere che i coefficienti non siano tutti nulli.

[BorisM]

A questo punto chi ti impedisce di sceglierli tutti nulli comunque? Perché sia non banale una buona condizione può essere che i coefficienti non siano tutti nulli.

Io non sto cercando una soluzione non banale, sto cercando solo di capire se la mia soluzione è giusta o no

[Drago96]

Quello che intende è che se si potessero scegliere tutti 0, il problema sarebbe banale...
Quindi prova a risolverlo con questa condizione!

Se la stanchezza non mi gioca brutti scherzi, direi che si può fare anche con tanti altri numeri al posto di 1001...

[xXStephXx]

si può fare anche con tanti altri numeri al posto di 1001...

Sì, con tutti fino ad un certo punto

[Gottinger95]

Il problema si può riformulare con \(k\) al posto di \(10\) e \(n\) al posto di 1001 in questo modo.
Siano \(n,k \in \mathbb{N} \) e sia \(A = \{1, \ldots, k\}\). Dati \(a_1, \ldots, a_k \in \mathbb{N} \), trovare (se esistono) \( S_1, S_2 \subseteq A\) tali che
\[ \sum_{i \in S_1} a_i = \sum_{i \in S_2} a_i\]
Spostando tutto a sinistra si ottengono gli \(x_i\) del problema originario.
Soluzione.

Testo nascosto:

Le possibili somme sono \(2^k\); se \(2^k> n\) allora per pidgeonhole ne trovo di certo due uguali, che è la tesi. E' vero invece che con \(n=2^k\) potrei non farcela?

E con 1024?

[xXStephXx]

con $1024$ non ce la fai se hai: $1,2,4,8,...,512$. Dovresti ottenere per forza $0$ ma non puoi visto che la più piccola potenza che prendi ti sballa il resto modulo quella successiva.

[gpzes]

Seguendo soluzione di Gottinger …forse affermazione rimane valida anche per ${{2}^{k}}=n.$
Se almeno uno dei dieci numeri è congruente a zero mod n, allora gli assegno coefficiente uno e zero agli altri.
Se almeno due dei dieci numeri appartengono alla stessa classe mod n , allora assegno 1 e -1 a loro due e zero agli altri.
Se tutti i dieci numeri appartengono a classi resto distinte potrebbe succedere di non trovare multipli di n ed avrei sequenza banale di zeri. Altrimenti, le classi resto potrebbero dare come somma zero, ed assegnerei coefficiente 1 a tutti.

[xXStephXx]

ed avrei sequenza banale di zeri.

Ma così funziona per ogni numero. Lui chiedeva se usando $k$ numeri puoi sempre ottenere un valore divisibile per $2^k$, senza però annullare tutto.

[gpzes]

@ xXStephxx ..ehh sì..ho estremizzato un po' affermazione ...sicuramente non è possibile come ho anche rimarcato.
Posso avere, come hai illustrato con Tuo controesempio, 1 , 2, 4, ....256, 512 ma anche 1, 1023, 4, ...., 512 per cui potrei scegliere coefficiente uno per 1 e 1023 e zero gli altri.
Si può dire che avrei $1023^{10} - \binom {1023}{9}$ possibilità modulo 1024 di operare con le classi resto tra cui scegliere numeri che danno luogo a sequenze banali di zero?!?

[Gottinger95]

@gzpes:
\(1,2,4, \ldots, 512\): nessuna assegnazione di \(0,\pm 1\) produce un numero divisibile per \(1024\).
\(1,1023,4, \ldots, 512\): assegnando \(+1, +1, 0, \ldots, 0 \) si produce un numero divisibile per \(1024\).
Che intendi con il tuo "ma anche"?

Rilancio:
Siano \(k,n \in \mathbb{N}_0\), con \(n \ge 2\). Trovare il più piccolo \(m \in \mathbb{N}_0\) tale che, dati qualsiasi \(a_1, \ldots, a_k \in \mathbb{Z} \), è possibile scegliere degli interi \( -m < x_1, \ldots, x_k < +m\) che soddisfano
\[ \sum_{i=1}^k a_i x_i \equiv 0 \pmod{n} \]
Questa può essere vista come una sorta di generalizzazione del Lemma di Thue (che vi consiglio di non guardare se non volete spoilerarvi la soluzione).

[xXStephXx]

Dovrebbe funzionare un ragionamento analogo xD Però è davvero simpatica quella generalizzazione

In pratica per un certo $m$ e $k$ fissati posso farlo divisibile per tutti gli interi fino a $(m+1)^k$.
Il motivo è che stavolta mi costruisco tutte le somme possibili dove ogni coefficiente lo posso scegliere tra $0$ e $m$. Quindi ottengo $(m+1)^k$ somme diverse.
Se il numero è minore di tale somma per pigeonhole ne trovo due con lo stesso resto e faccio la differenza. La differenza funziona anche stavolta perchè i coefficienti della differenza variano tra $-m$ ed $m$.
Analogamente $(m+1)^k$ non è detto che lo riesco ad ottenere. Anche qui, basta prendere le prime $k$ potenze $m+1-esime$. Per lo stesso ragionamento fatto prima al massimo ottengo $(m+1)^k-1$. Quindi dovrei per forza ottenere $0$, ma non posso perchè non viene la congruenza modulo la seconda potenza più piccola con coefficiente non nullo.

Quindi $k > log_{m+1}{n}$

[gpzes]

@ Gottinger
Sì..mi sono espresso malissimo volevo solo dire che si possono dare sequenze che vanno bene ed altre no
Mitico rilancio comunque
mmm..mi verrebbe da dire che debba essere $m>[n/2^k]$....

[Gottinger95]

@xXStephXx: tutto giusto, solo piccoli dettagli "formali":
- avevo messo \(< m\), quindi va sostituito un \(m\) a tutti gli \(m+1\) (ma questa è solo estetica, diciamocelo);
- avevo fissato \(n,k\), perciò la condizione era su \(m\), perciò il risultato è \( m \ge \sqrt[k]{n} \); nella prima parte (ossia è sufficiente che valga bla bla) non cambia nulla chi è quello fissato, però la parte del necessario andrebbe un po' riformulata. Mi pare che regga lo stesso ragionamento con i ruoli cambiati, comunque.
@gzpes: tranquillo, no problema! Mmm, pensaci meglio, un buon ragionamento fa più di mille guess!

[gpzes]

@Gottinger
..chiedo scusa per errore...scrivo dettagli per farmi perdonare

Siano $0\le {{\alpha }_{i}}\le m-1$ e $0\le {{\beta }_{i}}\le m-1$, consideriamo $\sum\limits_{i=1}^{k}{{{a}_{i}}{{\alpha }_{i}}}$ e $\sum\limits_{i=1}^{k}{{{a}_{i}}{{\beta }_{i}}}$. Le somme possibili sono ${{m}^{k}}$. Se ${{m}^{k}}>n$, ossia, se $m\ge \left\lceil \sqrt[k]{n} \right\rceil $(parte intera superiore), per Pigeon-hole almeno due sommatorie stanno nella stessa classe modulo n. La loro differenza \[\sum\limits_{i=1}^{k}{{{a}_{i}}{{\alpha }_{i}}}-\sum\limits_{i=1}^{k}{{{a}_{i}}{{\beta }_{i}}}=\sum\limits_{i=1}^{k}{{{a}_{i}}\left( {{\alpha }_{i}}-{{\beta }_{i}} \right)}\] è tale che \[-\left( m-1 \right)\le {{\alpha }_{i}}-{{\beta }_{i}}\le \left( m-1 \right)\]. Quindi la Tesi.