Esercizio 10 - Scala e canguri

Selezioni provinciali delle Olimpiadi della Matematica 2014-2015
Rispondi
cip999
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Esercizio 10 - Scala e canguri

Messaggio da cip999 »

Una scala è formata da $N$ gradini, dove $N = p_1 \cdot p_2 \cdot \dots \cdot p_{2015}$ è il prodotto di $2015$ primi distinti. I gradini corrispondenti a un divisore di $N$ (compresi $1$ e $N$ stesso) sono speciali e sono inizialmente illuminati di verde.
$2015$ canguri iniziano a saltare, uno alla volta, sui gradini della scala con questo criterio: l'$i$-esimo canguro salta $p_i$ gradini alla volta (quindi, partendo dalla base della scala, salta prima sul gradino $p_i$, poi sul gradino $2p_i$, etc.). Quando un canguro tocca un gradino speciale, questo cambia colore: se è verde diventa rosso, se è rosso diventa verde.
Dopo che tutti i canguri hanno terminato la loro esibizione, quanti gradini rimangono verdi?

Soluzione che ho usato in gara:
Testo nascosto:
Sia $d = p_{i_1} \cdot p_{i_2} \cdot \dots \cdot p_{i_k}$ (con $1 \leq i_1 < \dots < i_n \leq 2015$) un divisore di $N$. Osserviamo che $d$ viene toccato da un canguro tante volte quanti sono i primi che compaiono nella sua fattorizzazione, cioè esattamente $k$ volte. I gradini che restano verdi sono quelli su cui salta un numero pari di canguri, cioè quelli cui è associato un divisore con un numero pari di primi, e questi sono:
$$\displaystyle \binom{2015}{0} + \binom{2015}{2} + \dots + \binom{2015}{2014} = \binom{2015}{0} + \binom{2015}{1} + \dots + \binom{2015}{1007} = \frac{1}{2} \left ( \binom{2015}{0} + \dots + \binom{2015}{2015} \right ) = \frac{2^{2015}}{2} = 2^{2014}$$
Quindi i gradini verdi alla fine saranno $2^{2014}$
Soluzione alternativa:
Testo nascosto:
Possiamo contare il numero di divisori con un numero pari di primi nel modo seguente.
Se $\displaystyle d < \sqrt{N}$ è un divisore di $N$, allora anche $\displaystyle \frac{N}{d} > \sqrt{N}$ lo è; inoltre, il numero di primi che compaiono nella fattorizzazione di $\displaystyle \frac{N}{d}$ è esattamente il complementare a $2015$ del numero di primi che stanno in $d$: questo implica che se $d$ ha un numero pari di primi nella scomposizione, allora il suo complementare ne ha in numero dispari, e viceversa. Poiché $N$ certamente non è un quadrato, possiamo raggruppare i suoi $2^{2015}$ divisori in $\displaystyle \frac{2^{2015}}{2}$ coppie di complementari. In ogni coppia, esattamente un divisore ha un numero pari di primi.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
Gerald Lambeau
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: Esercizio 10 - Scala e canguri

Messaggio da Gerald Lambeau »

Dubbio: ma se un divisore è formato da k primi con k dispari, non avrebbe comunque [tex]2^k[/tex] divisori?
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
cip999
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: Esercizio 10 - Scala e canguri

Messaggio da cip999 »

Gerald Lambeau ha scritto:Dubbio: ma se un divisore è formato da k primi con k dispari, non avrebbe comunque [tex]2^k[/tex] divisori?
Sì, ma un gradino non viene toccato una volta per ogni divisore, ma una volta per ogni primo che contiene. Per esempio, il gradino $p_1p_2p_3$ viene toccato dai canguri $1, \: 2, \: 3$ (che saltano rispettivamente $p_1, \: p_2, \: p_3$ gradini alla volta)... ;)
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
Gerald Lambeau
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: Esercizio 10 - Scala e canguri

Messaggio da Gerald Lambeau »

Allora aver contato [tex]2^{2015}-1=2^{2014}[/tex] è stato un bene! :D
PS: so che è sbagliato, si tratta di mera fortuna
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Rispondi