Divisibilità per 100
Buonasera. So di tediarvi, ma è per una buona causa. 
Ho due problemi che hanno a che fare con la divisibilità per 100 e che proprio non riesco a risolvere.
1) Determinare il più piccolo intero positivo \(n\) tale che il coefficiente binomiale \({2n \choose n}\) sia divisibile per 100.
2) Dimostra che, dati 52 numeri interi, esiste almeno una coppia la cui somma o differenza è divisibile per 100.
Nel secondo credo che non saprei dove mettere le mani, anche se ammetto di non essermici applicato molto. Nel primo ho notato solo che quella scrittura si può riscrivere come:
Credo che bisogni valutare separatamente la divisibilità per 4 e poi quella per 25. Volevo applicare qualche strumento di aritmetica modulare (come operare su una scrittura del tipo \(\dfrac{2^n(2n-1)!!}{n!}\equiv0\;\text{mod}\;100\)) ma non ne trovo modo. In generale, c'è qualche strategia per risolvere problemi che coinvolgono test di divisibilità et similia?
Ho due problemi che hanno a che fare con la divisibilità per 100 e che proprio non riesco a risolvere.
1) Determinare il più piccolo intero positivo \(n\) tale che il coefficiente binomiale \({2n \choose n}\) sia divisibile per 100.
2) Dimostra che, dati 52 numeri interi, esiste almeno una coppia la cui somma o differenza è divisibile per 100.
Nel secondo credo che non saprei dove mettere le mani, anche se ammetto di non essermici applicato molto. Nel primo ho notato solo che quella scrittura si può riscrivere come:
\(\displaystyle{2n \choose n} = \dfrac{2^n(2n-1)!!}{n!}\).
Credo che bisogni valutare separatamente la divisibilità per 4 e poi quella per 25. Volevo applicare qualche strumento di aritmetica modulare (come operare su una scrittura del tipo \(\dfrac{2^n(2n-1)!!}{n!}\equiv0\;\text{mod}\;100\)) ma non ne trovo modo. In generale, c'è qualche strategia per risolvere problemi che coinvolgono test di divisibilità et similia?
Risposte
Per la 1) farei così ... metto sotto spoiler così chi vuole può arrivarci da solo 
Cordialmente, Alex
Cordialmente, Alex
Una possibilità è usare il teorema cinese dei resti, perché risolvere il sistema
\[\begin{cases} \binom{2n}{n}\equiv 0\pmod{2^2} \\ \binom{2n}{n} \equiv 0 \pmod{5^2} \end{cases}\] equivale a risolvere l'unica equazione \(\binom{2n}{n}\equiv 0\pmod{100}\). Questo significa che devi trovare il più piccolo \(n\ge 2\) tale che \(\binom{2n}{n}\equiv 0\pmod{25}\); questo $n$ è 13, se non erro.
\[\begin{cases} \binom{2n}{n}\equiv 0\pmod{2^2} \\ \binom{2n}{n} \equiv 0 \pmod{5^2} \end{cases}\] equivale a risolvere l'unica equazione \(\binom{2n}{n}\equiv 0\pmod{100}\). Questo significa che devi trovare il più piccolo \(n\ge 2\) tale che \(\binom{2n}{n}\equiv 0\pmod{25}\); questo $n$ è 13, se non erro.
Per la 2) dovrebbe essere ...
Cordialmente, Alex
Cordialmente, Alex
La 1) che così come l'ho scritta non va bene ...
Questa dovrebbe andare bene ...
Cordialmente, Alex
Cordialmente, Alex
"_clockwise":
2) Dimostra che, dati 52 numeri interi, esiste almeno una coppia la cui somma o differenza è divisibile per 100.
"axpgn":
Per la 2) dovrebbe essere ...
Cordialmente, Alex
13 dimostra il punto 2? Penso tu intendessi il punto 1.
Comunque per il punto 2) è il classico problema in cui applicare il principio dei cassetti.
Hai 52 oggetti da distribuire in 51 cassetti!
Infatti puoi ragionare solo sui resti. Hai 52 due interi, \(a_1 < a_2 < \ldots < a_{52} \) tutti distinti, puoi supporre che non vi siano due interi uguali altrimenti la loro differenza è \(0\) che è divisibile per 100.
Quindi ciascuno di questi numeri si scriverà \( a_j = 100 q_j + r_j \) con \( 0 \leq r_j \leq 99 \). Un ragionamento analogo al precedente ci porta a supporre che tutti i resti siano distinti.
La somma ( o la differenza) tra due numeri sarà divisibile per \(100\) se \( r_j + r_k = 0 \mod 100 \). Nel nostro caso se \(r_j+r_k = 0 \) oppure \(r_j+r_j = 100 \). Quante coppie di interi minori di \(100 \) hai che sommate ti danno 100? Contiamole:
1) 0 + 100 (\(=0 \mod 100\))
2) 1 + 99
3) 2 + 98
4) 3 + 97
...
51) 50 + 50.
Bene! Scegline tra questi 102 numeri, ognuna delle 51 coppie è formata da due numeri, 52 e avrai forzatamente che almeno 2 scelti ti formeranno una coppia che sommati ti da 100.
Per convincerti cerca di prenderli tutti in modo tale da non formare nessuna coppia che sommata da 100.
Beh iniziamo a scegliere i numeri "a sinistra" della nostra coppia.
Quindi prendo 0,1,2,3,4,\(\ldots\), 50. E fino a qui sono tutti presi da coppie diverse, ma ne abbiamo scelti solo 51. Dobbiamo prenderne un' altro. Ma qualunque esso prendiamo formeremo una coppia. Se prendi ad esempio 54 allora formerai 54+46=100. Etc.
Hai 52 oggetti da distribuire in 51 cassetti!
Infatti puoi ragionare solo sui resti. Hai 52 due interi, \(a_1 < a_2 < \ldots < a_{52} \) tutti distinti, puoi supporre che non vi siano due interi uguali altrimenti la loro differenza è \(0\) che è divisibile per 100.
Quindi ciascuno di questi numeri si scriverà \( a_j = 100 q_j + r_j \) con \( 0 \leq r_j \leq 99 \). Un ragionamento analogo al precedente ci porta a supporre che tutti i resti siano distinti.
La somma ( o la differenza) tra due numeri sarà divisibile per \(100\) se \( r_j + r_k = 0 \mod 100 \). Nel nostro caso se \(r_j+r_k = 0 \) oppure \(r_j+r_j = 100 \). Quante coppie di interi minori di \(100 \) hai che sommate ti danno 100? Contiamole:
1) 0 + 100 (\(=0 \mod 100\))
2) 1 + 99
3) 2 + 98
4) 3 + 97
...
51) 50 + 50.
Bene! Scegline tra questi 102 numeri, ognuna delle 51 coppie è formata da due numeri, 52 e avrai forzatamente che almeno 2 scelti ti formeranno una coppia che sommati ti da 100.
Per convincerti cerca di prenderli tutti in modo tale da non formare nessuna coppia che sommata da 100.
Beh iniziamo a scegliere i numeri "a sinistra" della nostra coppia.
Quindi prendo 0,1,2,3,4,\(\ldots\), 50. E fino a qui sono tutti presi da coppie diverse, ma ne abbiamo scelti solo 51. Dobbiamo prenderne un' altro. Ma qualunque esso prendiamo formeremo una coppia. Se prendi ad esempio 54 allora formerai 54+46=100. Etc.
"3m0o":
Comunque per il punto 2) è il classico problema in cui applicare il principio dei cassetti.
E io che ho fatto? Lo stesso, peraltro usando meno parole delle tue
Tra l'altro non mi è chiarissimo il tuo procedimento ...
"3m0o":
13 dimostra il punto 2? Penso tu intendessi il punto 1.
Adesso che me lo fai notare, vedo che ho mescolato un po' le cose
Cordialmente, Alex
E non hai risposto alla 2) ma alla 1)... credo!
Comunque il mio procedimento è semplice. Prova a prendere 52 numeri non formano una di quelle coppie. Non ce la fai! Finito.
È il principio dei cassetti. Se hai 51 cassetti e 52 piccioni allora 2 piccioni li devi mettere nello stesso buco.
Comunque il mio procedimento è semplice. Prova a prendere 52 numeri non formano una di quelle coppie. Non ce la fai! Finito.
È il principio dei cassetti. Se hai 51 cassetti e 52 piccioni allora 2 piccioni li devi mettere nello stesso buco.
Certo, è il principio dei cassetti, l'ho usato anch'io ma non devi partire dai numeri ma dai resti (voglio dire che non è chiaro, a parer mio, come l'hai esposto mescolando numeri e resti, tra l'altro perché i resti dovrebbero essere tutti distinti? Difatti non è vero ...)
Sì, ho scambiato le risposte, non me n'ero accorto ...
Cordialmente, Alex
Sì, ho scambiato le risposte, non me n'ero accorto ...
Cordialmente, Alex
Puoi assumere i numeri diversi perché se hai due numeri uguali \(n-n=0\) e \(0\) è multiplo di tutti gli interi. Quindi 100 divide 0!
Puoi assumere tutti i resti distinti perché se hai due resti uguali allora \(100q_1 + r - (100 q_2 + r) = 100(q_1-q_2) \) che è divisibile per 100.
Puoi assumere tutti i resti distinti perché se hai due resti uguali allora \(100q_1 + r - (100 q_2 + r) = 100(q_1-q_2) \) che è divisibile per 100.
L'ho scritto nel primo post che i numeri devono essere tutti distinti ...
Per i resti, intendevo quelli relativi alla divisione per $50$ (è ovvio che quelli relativi a $100$ son tutti distinti)
"axpgn":
I numeri sono tutti diversi (altrimenti zero è divisibile per 100) ...
Per i resti, intendevo quelli relativi alla divisione per $50$ (è ovvio che quelli relativi a $100$ son tutti distinti)
"axpgn":
Per la 2) dovrebbe essere ...
Cordialmente, Alex
Grazie infinite! Insomma, devo dare più peso al vecchio metodo "per tentativi".
Per quanto riguarda l'altro problema, perdonatemi ma mi sono un po' perso. Innanzitutto non conoscevo il principio dei cassetti, che è a dir poco fenomenale. Se ne fossi venuto a conoscenza prima, quante ore avrei risparmiato... Comunque, se ho capito bene ci sono due casi:
1) ci sono due numeri uguali, dunque la tesi è banalmente vera;
2) tutti i numeri sono distinti.
In quest'ultimo caso allora posso individuare 52 "oggetti" (i numeri interi) e 51 "cassetti" (i resti modulo 52), per cui so per certo che due numeri hanno lo stesso resto modulo 52. Se li chiamo \(a_1\) e \(a_2\):
\(a_1=52q_1+r,\;\;\;\;\;\;a_2=52q_2+r, \;\;\;\;\;\;\text{con}\:\:q_1,q_2,r\in\mathbb{Z} \wedge q_1>q_2 \wedge 0\leq r \leq 51\)
da cui
\(a_1-a_2=52(q_1-q_2)\)
e concludo che questa differenza è divisibile per 52, ossia per 4. Ho letto più volte le vostre dimostrazioni ma mi sfugge come estendere quest'ultimo risultato al campo della divisibilità per 100. Se pongo \(a_j=100q_j+r_j\) non ho 99 cassetti?
"solaàl":
Una possibilità è usare il teorema cinese dei resti, perché risolvere il sistema
\[\begin{cases} \binom{2n}{n}\equiv 0\pmod{2^2} \\ \binom{2n}{n} \equiv 0 \pmod{5^2} \end{cases}\] equivale a risolvere l'unica equazione \(\binom{2n}{n}\equiv 0\pmod{100}\). Questo significa che devi trovare il più piccolo \(n\ge 2\) tale che \(\binom{2n}{n}\equiv 0\pmod{25}\); questo $n$ è 13, se non erro.
Ho studiato il teorema! È molto utile. Se lo applico a quel sistema chiaramente riottengo l'equazione che hai scritto. Hai fatto qualche passaggio per ricavare il 13 o hai proceduto anche tu per tentativi contando i fattori 5 che spuntano al numeratore e al denominatore?
1) ci sono due numeri uguali, dunque la tesi è banalmente vera;
2) tutti i numeri sono distinti.
Esatto, se ci sono due numeri uguali è banalmente vero. Se sono tutti distinti prendi i resti modulo 100 e non come ha fatto axpgn modulo 52 (non ho capito troppo come ha fatto lui, ma è diverso dal modo proposto da me, penso che anche il suo funzioni)
In quest'ultimo caso allora posso individuare 52 "oggetti" (i numeri interi) e 51 "cassetti" (i resti modulo 52), per cui so per certo che due numeri hanno lo stesso resto modulo 52. Se li chiamo \(a_1\) e \(a_2\):
No!
In modo analogo hai 2 casi
1) Se ci sono due resti uguali, banalmente vero
2) Se tutti i resti diversi allora:
Hai 52 oggetti, li chiamo \(r_1,\ldots,r_{52} \), che sono i resti modulo 100 dei tuoi 52 interi scelti arbitrariamente.
E hai 51 cassetti che sono le coppie le chiamo \( (a_0,b_{0}), (a_1,b_{99}), (a_2,b_{98}), \ldots , (a_{49},b_{51}) ,(a_{50},b_{50}) \) tale che \(a_j+b_{100-j}=100 \) oppure \(a_0+b_0=0 \).
Quindi sai per certo che inserendo nei tuoi cassetti i 52 resti sicuramente almeno due saranno nello stesso cassetto quindi esisteranno \(1 \leq j ,k \leq 52 \) tale che \( r_j = a_m \) e \( r_k = b_{100-m} \) e dunque hai che \(r_j+r_k = 100 \).
Per cui se i tuoi numeri iniziali erano \(n_j = 100 q_j + r_j \) e \(n_k = 100 q_k + r_k \) ottieni \[ n_j + n_k = 100(q_j + q_k) + r_j+r_k = 100(q_j + q_k +1 )\]
quindi la somma è divisibile per 100!!
Grazie davvero, tutto chiaro!
EDIT: Giusto per vedere se ho capito, ho cercato altri problemi simili e ho provato a risolverli. Potreste dirmi se il procedimento è corretto?
Dimostrare che dati \(n\) numeri interi positivi, ve ne sono alcuni (anche uno solo) la cui somma è divisibile per \(n\).
Ci sono due modi. Nell'ipotesi che \(n\) sia pari, posso procedere come 3m0o, quindi noto che ho a disposizione \(n\) oggetti, cioè i numeri, e \(n/2+1\) cassetti, ossia le coppie di resti modulo \(n\) tali che la loro somma è nulla oppure \(n\): siccome almeno un cassetto conterrà almeno due oggetti, allora ci sono almeno due numeri con resti "complementari". (Chiaro che la tesi è immediatamente vera se un numero è divisibile per \(n\).) Altrimenti, prendo le \(n\) somme del tipo \(s_1=n_1\), \(s_2=n_1+n_2\), \(s_n=n_1+n_2+\dots+n_n\) e, siccome i resti modulo \(n\) sono in tutto \(n-1\), concludo che almeno due somme avranno lo stesso resto modulo \(n\). Se le chiamo \(s_j\) e \(s_k\), con \(s_j>s_k\), per le proprietà delle congruenze è vero che \(s_j \equiv s_k\;\text{mod}\;n\), da cui si vede che \(s_j-s_k\), una possibile somma nell'insieme degli \(n\) numeri, è divisibile per \(n\). \(\square\)
Questo procedimento l'avevo già visto in azione ieri, ma credo che non si adatti bene al problema sulla divisibilità per 100, perché lì lavoriamo già con \(n/2+2\) numeri e l'insieme è troppo ristretto.
Dimostrare che in qualunque modo si scelgono cinque punti in un triangolo equilatero di lato 1 ve ne sono sempre 2 la cui distanza è minore o uguale a \(1/2\).
Questo è facile: disegno il triangolo, unisco i punti medi dei lati ottenendo quattro triangoli equilateri di lato \(1/2\) e concludo che, dovendo per il principio dei cassetti esserci almeno due punti in uno dei triangolini, questi possono distare una lunghezza non maggiore del lato, ossia proprio \(1/2\). \(\square\)
Dimostrare che dati comunque 5 interi ne esistono 3 la cui somma è divisibile per 3.
Allora, la somma di tre numeri è divisibile per 3 se e solo se i numeri hanno lo stesso resto modulo 3 (0, 1 o 2) o hanno tutti resti diversi. Siccome ho 5 oggetti (gli interi) e 3 cassetti (i resti modulo 3), allora in qualunque configurazione ci sono o un cassetto con almeno tre elementi o tre cassetti con almeno un elemento ciascuno. Da qui la tesi! \(\square\)
5 è anche il numero minimo di oggetti tali per cui la proprietà è vera. Se fossero 4, allora sarebbe possibile che due di questi avessero resto 0 e gli altri due resto 1, o qualsiasi altra disposizione di classe 2 dei 3 resti.
EDIT: Ho letto una bella dimostrazione di un'affermazione simile all'ultima, quindi la ripropongo, con i dovuti aggiustamenti, perché mi sembra interessante. Dunque, divido l'insieme dei numeri interi nelle classi di equivalenza modulo 3:
\(C_3(0)=\{...,-6,-3,0,3,6,...\}\)
\(C_3(1)=\{...,-5,-2,1,4,7,...\}\)
\(C_3(2)=\{...,-3,-1,2,5,8,...\}\)
e scelgo in prima istanza dei numeri tali che non vi siano terne dalla somma divisibile per 3. Questo significa che non posso scegliere tre numeri appartenenti alla medesima classe di equivalenza, perché in quel caso mi ritroverei con tre numeri \(a_1,a_2,a_3\) tali che \(a_1\equiv r\;\text{mod}\;3\), \(a_2\equiv r\;\text{mod}\;3\), \(a_3\equiv r\;\text{mod}\;3\), per cui \(a_1+a_2+a_3\equiv 3r\;\text{mod}\;3\equiv 0\;\text{mod}\;3\). Posso quindi sceglierne, ad esempio, due da \(C_3(1)\) e due da \(C_3(2)\), arrivando a 4. Ora, se estraggo il quinto da una delle stesse classi, ho una somma divisibile per 3 e quindi la tesi. Se lo estraggo da \(C_3(0)\), infine, ottengo lo stesso risultato: infatti, scelti, oltre il quinto numero, due numeri a piacere appartenenti a classi di equivalenza diverse e sommando membro a membro le congruenze corrispondenti, vien sempre fuori un resto pari a 3.
EDIT: Giusto per vedere se ho capito, ho cercato altri problemi simili e ho provato a risolverli. Potreste dirmi se il procedimento è corretto?
Dimostrare che dati \(n\) numeri interi positivi, ve ne sono alcuni (anche uno solo) la cui somma è divisibile per \(n\).
Ci sono due modi. Nell'ipotesi che \(n\) sia pari, posso procedere come 3m0o, quindi noto che ho a disposizione \(n\) oggetti, cioè i numeri, e \(n/2+1\) cassetti, ossia le coppie di resti modulo \(n\) tali che la loro somma è nulla oppure \(n\): siccome almeno un cassetto conterrà almeno due oggetti, allora ci sono almeno due numeri con resti "complementari". (Chiaro che la tesi è immediatamente vera se un numero è divisibile per \(n\).) Altrimenti, prendo le \(n\) somme del tipo \(s_1=n_1\), \(s_2=n_1+n_2\), \(s_n=n_1+n_2+\dots+n_n\) e, siccome i resti modulo \(n\) sono in tutto \(n-1\), concludo che almeno due somme avranno lo stesso resto modulo \(n\). Se le chiamo \(s_j\) e \(s_k\), con \(s_j>s_k\), per le proprietà delle congruenze è vero che \(s_j \equiv s_k\;\text{mod}\;n\), da cui si vede che \(s_j-s_k\), una possibile somma nell'insieme degli \(n\) numeri, è divisibile per \(n\). \(\square\)
Questo procedimento l'avevo già visto in azione ieri, ma credo che non si adatti bene al problema sulla divisibilità per 100, perché lì lavoriamo già con \(n/2+2\) numeri e l'insieme è troppo ristretto.
Dimostrare che in qualunque modo si scelgono cinque punti in un triangolo equilatero di lato 1 ve ne sono sempre 2 la cui distanza è minore o uguale a \(1/2\).
Questo è facile: disegno il triangolo, unisco i punti medi dei lati ottenendo quattro triangoli equilateri di lato \(1/2\) e concludo che, dovendo per il principio dei cassetti esserci almeno due punti in uno dei triangolini, questi possono distare una lunghezza non maggiore del lato, ossia proprio \(1/2\). \(\square\)
Dimostrare che dati comunque 5 interi ne esistono 3 la cui somma è divisibile per 3.
Allora, la somma di tre numeri è divisibile per 3 se e solo se i numeri hanno lo stesso resto modulo 3 (0, 1 o 2) o hanno tutti resti diversi. Siccome ho 5 oggetti (gli interi) e 3 cassetti (i resti modulo 3), allora in qualunque configurazione ci sono o un cassetto con almeno tre elementi o tre cassetti con almeno un elemento ciascuno. Da qui la tesi! \(\square\)
5 è anche il numero minimo di oggetti tali per cui la proprietà è vera. Se fossero 4, allora sarebbe possibile che due di questi avessero resto 0 e gli altri due resto 1, o qualsiasi altra disposizione di classe 2 dei 3 resti.
EDIT: Ho letto una bella dimostrazione di un'affermazione simile all'ultima, quindi la ripropongo, con i dovuti aggiustamenti, perché mi sembra interessante. Dunque, divido l'insieme dei numeri interi nelle classi di equivalenza modulo 3:
\(C_3(0)=\{...,-6,-3,0,3,6,...\}\)
\(C_3(1)=\{...,-5,-2,1,4,7,...\}\)
\(C_3(2)=\{...,-3,-1,2,5,8,...\}\)
e scelgo in prima istanza dei numeri tali che non vi siano terne dalla somma divisibile per 3. Questo significa che non posso scegliere tre numeri appartenenti alla medesima classe di equivalenza, perché in quel caso mi ritroverei con tre numeri \(a_1,a_2,a_3\) tali che \(a_1\equiv r\;\text{mod}\;3\), \(a_2\equiv r\;\text{mod}\;3\), \(a_3\equiv r\;\text{mod}\;3\), per cui \(a_1+a_2+a_3\equiv 3r\;\text{mod}\;3\equiv 0\;\text{mod}\;3\). Posso quindi sceglierne, ad esempio, due da \(C_3(1)\) e due da \(C_3(2)\), arrivando a 4. Ora, se estraggo il quinto da una delle stesse classi, ho una somma divisibile per 3 e quindi la tesi. Se lo estraggo da \(C_3(0)\), infine, ottengo lo stesso risultato: infatti, scelti, oltre il quinto numero, due numeri a piacere appartenenti a classi di equivalenza diverse e sommando membro a membro le congruenze corrispondenti, vien sempre fuori un resto pari a 3.
Leggo dopo che ora ho da fare. Ma se ti interessa un affascinante applicazione del principio dei cassetti. Puoi dimostrare il teorema di Erdos-Szekeres con questo principio.
Il teorema afferma quanto segue:
Sia data una successione finita di numeri reali di lunghezza \(n \geq sr + 1 \), allora esiste almeno una sotto-successione di lunghezza \( s+1 \) che sia monotona crescente oppure esiste almeno una sotto-successione di lunghezza \(r+1 \) che sia monotona decrescente.
Ad esempio prendiamo \( n=10 \geq 3 \cdot 3 +1 = sr+1 \), e prendiamo 10 numeri reali qualunque \( a_1, a_2, \ldots, a_{10} \). Ad esempio
\[ 3, 10,\pi,e,11,109,7, \frac{1}{2} , \sqrt{2} , \ln(2) \]
allora qui dentro puoi trovare una sotto-successione monotona crescente di lunghezza \(4\). Ad esempio scegliendo \( a_1, a_2, a_5 , a_6 \), che sono \( 3,10,11,109 \). Oppure avremmo potuto prendere anche \( a_1,a_3,a_5,a_6 \) ovvero \( 3 , \pi, 11 , 109 \).
In questa c'è anche ad esempio quella decrescente di lunghezza \(4 \). Ad esempio
\[ 10, \pi, e, \frac{1}{2} \]
Il teorema afferma quanto segue:
Sia data una successione finita di numeri reali di lunghezza \(n \geq sr + 1 \), allora esiste almeno una sotto-successione di lunghezza \( s+1 \) che sia monotona crescente oppure esiste almeno una sotto-successione di lunghezza \(r+1 \) che sia monotona decrescente.
Ad esempio prendiamo \( n=10 \geq 3 \cdot 3 +1 = sr+1 \), e prendiamo 10 numeri reali qualunque \( a_1, a_2, \ldots, a_{10} \). Ad esempio
\[ 3, 10,\pi,e,11,109,7, \frac{1}{2} , \sqrt{2} , \ln(2) \]
allora qui dentro puoi trovare una sotto-successione monotona crescente di lunghezza \(4\). Ad esempio scegliendo \( a_1, a_2, a_5 , a_6 \), che sono \( 3,10,11,109 \). Oppure avremmo potuto prendere anche \( a_1,a_3,a_5,a_6 \) ovvero \( 3 , \pi, 11 , 109 \).
In questa c'è anche ad esempio quella decrescente di lunghezza \(4 \). Ad esempio
\[ 10, \pi, e, \frac{1}{2} \]
"_clockwise":
Dimostrare che dati \(n\) numeri interi positivi, ve ne sono alcuni (anche uno solo) la cui somma è divisibile per \(n\).
Ci sono due modi. Nell'ipotesi che \(n\) sia pari, posso procedere come 3m0o, quindi noto che ho a disposizione \(n\) oggetti, cioè i numeri, e \(n/2+1\) cassetti, ossia le coppie di resti modulo \(n\) tali che la loro somma è nulla oppure \(n\): siccome almeno un cassetto conterrà almeno due oggetti, allora ci sono almeno due numeri con resti "complementari". (Chiaro che la tesi è immediatamente vera se un numero è divisibile per \(n\).) Altrimenti, prendo le \(n\) somme del tipo \(s_1=n_1\), \(s_2=n_1+n_2\), \(s_n=s_1+s_2+\dots+s_n\) e, siccome i resti modulo \(n\) sono in tutto \(n-1\), concludo che almeno due somme avranno lo stesso resto modulo \(n\). Se le chiamo \(s_j\) e \(s_k\), con \(s_j>s_k\), per le proprietà delle congruenze è vero che \(s_j \equiv s_k\;\text{mod}\;n\), da cui si vede che \(s_j-s_k\), una possibile somma nell'insieme degli \(n\) numeri, è divisibile per \(n\). \(\square\)
Questo procedimento l'avevo già visto in azione ieri, ma credo che non si adatti bene al problema sulla divisibilità per 100, perché lì lavoriamo già con \(n/2+2\) numeri e l'insieme è troppo ristretto.
C'è qualcosa che non va nella tua dimostrazione.
La tua successione \( s_1,\ldots, s_n \) non ha resti necessariamente distinti e potrebbero essere tutti diversi da \(0\). Ad esempio con \( n = 7 \), prendi \( 2,2,2,3,2,2,2 \) allora hai
\[ s_1 = 2, s_2 = 4, s_3 = 6, s_4 = 2, s_5 = 4, s_6 = 6, s_7 = 1 \]
nessuno tra questi è divisibile per \(7 \).
Tu mi dirai... embhe ho supposto \(n \) pari. Beh allora considera \( 1,1,1,2 \) con \(n = 4 \) allora
\[ s_1 = 1, s_2 = 2 , s_3 = 3, s_4 = 1 \]
nessuno di questi è divisibile per \(4 \).
"_clockwise":
Dimostrare che in qualunque modo si scelgono cinque punti in un triangolo equilatero di lato 1 ve ne sono sempre 2 la cui distanza è minore o uguale a \(1/2\).
Questo è facile: disegno il triangolo, unisco i punti medi dei lati ottenendo quattro triangoli equilateri di lato \(1/2\) e concludo che, dovendo per il principio dei cassetti esserci almeno due punti in uno dei triangolini, questi possono distare una lunghezza non maggiore del lato, ossia proprio \(1/2\). \(\square\)
Penso vada bene.
"_clockwise":
Dimostrare che dati comunque 5 interi ne esistono 3 la cui somma è divisibile per 3.
Allora, la somma di tre numeri è divisibile per 3 se e solo se i numeri hanno lo stesso resto modulo 3 (0, 1 o 2) o hanno tutti resti diversi. Siccome ho 5 oggetti (gli interi) e 3 cassetti (i resti modulo 3), allora in qualunque configurazione ci sono o un cassetto con almeno tre elementi o tre cassetti con almeno un elemento ciascuno. Da qui la tesi! \(\square\)
5 è anche il numero minimo di oggetti tali per cui la proprietà è vera. Se fossero 4, allora sarebbe possibile che due di questi avessero resto 0 e gli altri due resto 1, o qualsiasi altra disposizione di classe 2 dei 3 resti.
Giusto. Ma scritto in modo un poco chiaro, una volta che è chiaro il principio dei cassetti all'interno del problema non chiamarli cassetti
Ad esempio io avrei scritto che le partizioni di \(5\) di lunghezza inferiore o uguale a \(3\) sono le seguenti
\[ 5, 1+4,2+3, 1+1+3,1+2+2 \]
comunque si scelgano 5 interi, i rispettivi resti modulo 3 possibili sono tre: \(0,1,2 \). I criteri di divisone per \(3\) fanno il resto
Ah ho capito cosa intendi
C'è qualcosa che non va nella tua dimostrazione.
La tua successione \( s_1,\ldots, s_n \) non ha resti necessariamente distinti e potrebbero essere tutti diversi da \( 0 \). Ad esempio con \( n = 7 \), prendi \( 2,2,2,3,2,2,2 \) allora hai
\[ s_1 = 2, s_2 = 4, s_3 = 6, s_4 = 2, s_5 = 4, s_6 = 6, s_7 = 1 \]
nessuno tra questi è divisibile per \( 7 \).
Tu mi dirai... embhe ho supposto \( n \) pari. Beh allora considera \( 1,1,1,2 \) con \( n = 4 \) allora
\[ s_1 = 1, s_2 = 2 , s_3 = 3, s_4 = 1 \]
nessuno di questi è divisibile per \( 4 \).
[/quote]
Okay funziona, però hai scritto delle cose in modo impreciso.
Consideri la somma \( s_1 = n_1 \), \( s_2 = n_1 + n_2 \), \( \ldots \), \( s_j = n_1 + \ldots + n_j \) , \( \ldots \), \( s_n = n_1 + \ldots + n_n \) (attento che non è \( s_1 + \ldots + s_n \)).
Se tra queste \( n \) somme ve ne è almeno una che è divisibile per \(n \) abbiamo terminato!
Altrimenti se nessuna di essere è divisibile per \(n \) tra gli \(n \) resti modulo \(n\) possiamo escludere lo zero. Quindi ci restano \(n-1 \) resti possibili. Ora per il principio dei cassetti troviamo \(j,k \) tale che \( s_j \equiv s_k \mod n \) pertanto \( n_{k+1} + \ldots + n_j = s_j - s_k \equiv 0 \mod n \).
"3m0o":
[quote="_clockwise"]
Dimostrare che dati \( n \) numeri interi positivi, ve ne sono alcuni (anche uno solo) la cui somma è divisibile per \( n \).
Ci sono due modi. Nell'ipotesi che \( n \) sia pari, posso procedere come 3m0o, quindi noto che ho a disposizione \( n \) oggetti, cioè i numeri, e \( n/2+1 \) cassetti, ossia le coppie di resti modulo \( n \) tali che la loro somma è nulla oppure \( n \): siccome almeno un cassetto conterrà almeno due oggetti, allora ci sono almeno due numeri con resti "complementari". (Chiaro che la tesi è immediatamente vera se un numero è divisibile per \( n \).) Altrimenti, prendo le \( n \) somme del tipo \( s_1=n_1 \), \( s_2=n_1+n_2 \), \( s_n=s_1+s_2+\dots+s_n \) e, siccome i resti modulo \( n \) sono in tutto \( n-1 \), concludo che almeno due somme avranno lo stesso resto modulo \( n \). Se le chiamo \( s_j \) e \( s_k \), con \( s_j>s_k \), per le proprietà delle congruenze è vero che \( s_j \equiv s_k\;\text{mod}\;n \), da cui si vede che \( s_j-s_k \), una possibile somma nell'insieme degli \( n \) numeri, è divisibile per \( n \). \( \square \)
Questo procedimento l'avevo già visto in azione ieri, ma credo che non si adatti bene al problema sulla divisibilità per 100, perché lì lavoriamo già con \( n/2+2 \) numeri e l'insieme è troppo ristretto.
C'è qualcosa che non va nella tua dimostrazione.
La tua successione \( s_1,\ldots, s_n \) non ha resti necessariamente distinti e potrebbero essere tutti diversi da \( 0 \). Ad esempio con \( n = 7 \), prendi \( 2,2,2,3,2,2,2 \) allora hai
\[ s_1 = 2, s_2 = 4, s_3 = 6, s_4 = 2, s_5 = 4, s_6 = 6, s_7 = 1 \]
nessuno tra questi è divisibile per \( 7 \).
Tu mi dirai... embhe ho supposto \( n \) pari. Beh allora considera \( 1,1,1,2 \) con \( n = 4 \) allora
\[ s_1 = 1, s_2 = 2 , s_3 = 3, s_4 = 1 \]
nessuno di questi è divisibile per \( 4 \).
[/quote]
Okay funziona, però hai scritto delle cose in modo impreciso.
Consideri la somma \( s_1 = n_1 \), \( s_2 = n_1 + n_2 \), \( \ldots \), \( s_j = n_1 + \ldots + n_j \) , \( \ldots \), \( s_n = n_1 + \ldots + n_n \) (attento che non è \( s_1 + \ldots + s_n \)).
Se tra queste \( n \) somme ve ne è almeno una che è divisibile per \(n \) abbiamo terminato!
Altrimenti se nessuna di essere è divisibile per \(n \) tra gli \(n \) resti modulo \(n\) possiamo escludere lo zero. Quindi ci restano \(n-1 \) resti possibili. Ora per il principio dei cassetti troviamo \(j,k \) tale che \( s_j \equiv s_k \mod n \) pertanto \( n_{k+1} + \ldots + n_j = s_j - s_k \equiv 0 \mod n \).
"3m0o":
... e non come ha fatto axpgn modulo 52 (non ho capito troppo come ha fatto lui, ma è diverso dal modo proposto da me, penso che anche il suo funzioni) ...
Non è modulo $52$
ma modulo $50$ e modulo $25$@clockwise
Ricapitolo il ragionamento che ho usato ...
I $52$ numeri sono tutti distinti altrimenti se due sono uguali la loro differenza sarebbe zero e quindi divisibile per cento.
I resti modulo $50$ sono $0, 1, 2, ..., 49$ ma possiamo vederli anche in questo modo alternativo $0, +-1, +-2, ...$
In tal caso, tenendo conto solo del valore assoluto abbiamo $25$ resti diversi, quindi per il principio dei cassetti, avendo $52$ numeri differenti avremo almeno tre resti uguali (in valore assoluto).
Rappresentiamo i tre numeri così $n_i=50q_i+-r$ con $i=1,2,3$
Almeno due quozienti avranno la stessa parità quindi $q_j+-q_k$ è pari e ne consegue che $50(q_j+-q_k)$ è multiplo di cento mentre i resti si elidono sommando i due numeri, se sono di segno diverso, o facendo la differenza se sono dello stesso segno.
Cordialmente, Alex
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo