Cortona 95

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
BorisM
Messaggi: 45
Iscritto il: 08 lug 2013, 20:11

Cortona 95

Messaggio da BorisM » 16 lug 2014, 21:43

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 :mrgreen: ):
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?

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: Cortona 95

Messaggio da <enigma> » 16 lug 2014, 22:02

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.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

BorisM
Messaggi: 45
Iscritto il: 08 lug 2013, 20:11

Re: Cortona 95

Messaggio da BorisM » 16 lug 2014, 22:40

<enigma> ha scritto: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 :?

Avatar utente
Drago96
Messaggi: 1139
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Cortona 95

Messaggio da Drago96 » 16 lug 2014, 22:56

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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Cortona 95

Messaggio da xXStephXx » 17 lug 2014, 01:55

Drago96 ha scritto:si può fare anche con tanti altri numeri al posto di 1001...
Sì, con tutti fino ad un certo punto :wink:

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Re: Cortona 95

Messaggio da Gottinger95 » 17 lug 2014, 15:21

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?
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Cortona 95

Messaggio da xXStephXx » 17 lug 2014, 18:37

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.

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Cortona 95

Messaggio da gpzes » 18 lug 2014, 22:49

Seguendo soluzione di Gottinger :wink: …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
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Cortona 95

Messaggio da xXStephXx » 18 lug 2014, 23:49

gpzes ha scritto: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.

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Cortona 95

Messaggio da gpzes » 19 lug 2014, 11:51

@ 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?!? :oops:

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Re: Cortona 95

Messaggio da Gottinger95 » 20 lug 2014, 15:24

@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).
Ultima modifica di Gottinger95 il 21 lug 2014, 20:15, modificato 1 volta in totale.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Cortona 95

Messaggio da xXStephXx » 20 lug 2014, 20:41

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

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}$

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Cortona 95

Messaggio da gpzes » 21 lug 2014, 01:42

@ Gottinger
Sì..mi sono espresso malissimo :oops: :oops: volevo solo dire che si possono dare sequenze che vanno bene ed altre no :oops:
Mitico rilancio comunque :wink: :wink:
mmm..mi verrebbe da dire che debba essere $m>[n/2^k]$....
Ultima modifica di gpzes il 21 lug 2014, 02:27, modificato 1 volta in totale.

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Re: Cortona 95

Messaggio da Gottinger95 » 21 lug 2014, 02:26

@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!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Cortona 95

Messaggio da gpzes » 21 lug 2014, 04:53

@Gottinger
:oops: :oops: ..chiedo scusa per errore...scrivo dettagli per farmi perdonare :wink: :wink:

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.

Rispondi