Carte caraibiche
Carte caraibiche
Sia $ {n} $ un intero positivo e $ {p} $ un numero primo fissato. Abbiamo un mazzo di carte numerate $ 1,2,\dots,n $ e $ {p} $ scatole. Determinare tutti i possibili interi $ {n} $ per i quali è possibile distribuire le carte nelle scatole in modo che la somma dei numeri delle carte contenute in ogni scatola è la stessa. (Centroamerican and Caribbean MO 2005).
per $ p=2 $ la condizione necessaria (e dimostriamo anche sufficiente)diviene $ \frac {n(n+1)}{2} \equiv 0 \pmod 2 $ cioè $ n(n+1) \equiv 0 \pmod 4 $ da cui $ n \equiv 0 \pmod 4 $ oppure $ n \equiv -1 \pmod 4 $.
è facile dimostrare per induzione che per tutti gli $ n $ della forma $ 4k $ è possibile tale costruzione, infatti ad ognuna scatola mettiamo una coppia $ (i, 4k-i) $, e dato che il numero di coppie è pari allora tale costruzione è sempre possibile. essendo possibile per $ n $ della forma $ 4k $ allora è possibile anche per $ n $ della forma $ 4k-1 $ infatti al primo sottoinsieme tolgo la coppia $ (1, 2k-1) $ mentre al secondo l'elemento $ 2k $: ciò è sempre possibile in quanto posso posizionare inizialmente tutti gli elementi dispari in un sottoinsieme e i pari nell'altro.
sia adesso $ p \ge 3 $ dispari. la condizione diviene come prima $ n(n+1) \equiv 0 \pmod {2p} $ e dato che non ci interessa del 2, dobbiamo concludere che condizione necessaria sia $ n\equiv 0 \pmod p $ o $ n \equiv -1 \pmod p $..
nel primo caso si vede che è necessario che $ n $ sia della forma $ 2p $, cioè tutti gli $ n \equiv p \pmod {2p} $ non hanno soluzione e tutti gli altri si..chi completa?
è facile dimostrare per induzione che per tutti gli $ n $ della forma $ 4k $ è possibile tale costruzione, infatti ad ognuna scatola mettiamo una coppia $ (i, 4k-i) $, e dato che il numero di coppie è pari allora tale costruzione è sempre possibile. essendo possibile per $ n $ della forma $ 4k $ allora è possibile anche per $ n $ della forma $ 4k-1 $ infatti al primo sottoinsieme tolgo la coppia $ (1, 2k-1) $ mentre al secondo l'elemento $ 2k $: ciò è sempre possibile in quanto posso posizionare inizialmente tutti gli elementi dispari in un sottoinsieme e i pari nell'altro.
sia adesso $ p \ge 3 $ dispari. la condizione diviene come prima $ n(n+1) \equiv 0 \pmod {2p} $ e dato che non ci interessa del 2, dobbiamo concludere che condizione necessaria sia $ n\equiv 0 \pmod p $ o $ n \equiv -1 \pmod p $..
nel primo caso si vede che è necessario che $ n $ sia della forma $ 2p $, cioè tutti gli $ n \equiv p \pmod {2p} $ non hanno soluzione e tutti gli altri si..chi completa?
The only goal of science is the honor of the human spirit.
-
_Francesca_
- Messaggi: 4
- Iscritto il: 23 nov 2007, 23:26
Per p = 2 non so dire il perché, ma è evidente che è necessario che n = p + 1 + k4 oppure n = 2p + k4.
Se p è maggiore di 2, dovendo essere un numero primo, evidentemente è dispari.
Detto ciò, s'è capito che, mettendo le carte nelle scatole a coppie, il valore di ogni coppia deve essere uguale ad n oppure ad n + 1 per ovvi motivi. Affinché la prima condizione sia soddisfatta è necessario che n = kp, con k maggiore di 2 (e allora se k è pari, si prende la prima e l'ultima carta e la si pone in ogni scatola, mentre se k è dispari si mette l'ultima carta nella prima scatola e per le altre si procede come sopra); affinché sia soddisfatta invece la seconda condizione, è necessario che n + 1 = kp, quindi n = kp - 1.
A me sembra che sia dimostrata così la seconda parte, ma la prima?
Se p è maggiore di 2, dovendo essere un numero primo, evidentemente è dispari.
Detto ciò, s'è capito che, mettendo le carte nelle scatole a coppie, il valore di ogni coppia deve essere uguale ad n oppure ad n + 1 per ovvi motivi. Affinché la prima condizione sia soddisfatta è necessario che n = kp, con k maggiore di 2 (e allora se k è pari, si prende la prima e l'ultima carta e la si pone in ogni scatola, mentre se k è dispari si mette l'ultima carta nella prima scatola e per le altre si procede come sopra); affinché sia soddisfatta invece la seconda condizione, è necessario che n + 1 = kp, quindi n = kp - 1.
A me sembra che sia dimostrata così la seconda parte, ma la prima?
Così l'affermazione è falsa in quanto non possiamo considerare la coppia (2k,4k-2k)=(2k,2k).jordan ha scritto:...
è facile dimostrare per induzione che per tutti gli $ n $ della forma $ 4k $ è possibile tale costruzione, infatti ad ognuna scatola mettiamo una coppia $ (i, 4k-i) $, e dato che il numero di coppie è pari allora tale costruzione è sempre possibile...
Tuttavia il ragionamento funziona se prendiamo le coppie (i,4k+1-i)
