Cortona 95
Cortona 95
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?
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?
Re: Cortona 95
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.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: Cortona 95
Io non sto cercando una soluzione non banale, sto cercando solo di capire se la mia soluzione è giusta o no<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.
Re: Cortona 95
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...
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)
Re: Cortona 95
Sì, con tutti fino ad un certo puntoDrago96 ha scritto:si può fare anche con tanti altri numeri al posto di 1001...
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Cortona 95
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.
E con 1024?
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:
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: Cortona 95
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.
Re: Cortona 95
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.
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.
Re: Cortona 95
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 ha scritto:ed avrei sequenza banale di zeri.
Re: Cortona 95
@ 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?!?
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?!?
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Cortona 95
@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).
\(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
Re: Cortona 95
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}$
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}$
Re: Cortona 95
@ 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]$....
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]$....
Ultima modifica di gpzes il 21 lug 2014, 02:27, modificato 1 volta in totale.
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Cortona 95
@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!
- 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
Re: Cortona 95
@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.
..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.