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
@3m0o
Scusami, chiaramente intendevo \(s_n=n_1+n_2+\dots+n_n\). Per adesso preferisco continuare a chiamarli così, ancora non riesco a individuare subito il metodo migliore per applicare il principio nei contesti più disparati. Però certo, presto subentrerà l'esigenza del fattore "rigore linguistico"!
@axpgn
Chiaro adesso. Bella dimostrazione!
Grazie ancora a entrambi.
Scusami, chiaramente intendevo \(s_n=n_1+n_2+\dots+n_n\). Per adesso preferisco continuare a chiamarli così, ancora non riesco a individuare subito il metodo migliore per applicare il principio nei contesti più disparati. Però certo, presto subentrerà l'esigenza del fattore "rigore linguistico"!
@axpgn
Chiaro adesso. Bella dimostrazione!
Grazie ancora a entrambi.
Ok ho capito. E perdonami di non aver capito subito cosa tu intendessi
@_clockwise
Certo figurati. Se ti è più comodo chiamarli così per ora continua pure a farlo.
Comunque se vuoi degli Hint per questo qui fammi sapere
Certo figurati. Se ti è più comodo chiamarli così per ora continua pure a farlo.
Comunque se vuoi degli Hint per questo qui fammi sapere
"3m0o":
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo