Un bulgaro di Caldé
Un bulgaro di Caldé
Let $ p \ge 3 $ be a prime number and $ a_1, a_2, ... , a_{p-2} $ be a sequence of natural numbers such that p does not divide $ a_k $ nor $ (a_k)^k-1 $ for all $ k=1,2,...,p-2 $. Prove that tre product of some elements of the sequence is congruent 2 modulo p.
Fase nazionale della Bulgaria
Corretto il LaTeX. MindFlyer
Fase nazionale della Bulgaria
Corretto il LaTeX. MindFlyer
mmm… c’ho perso il primo pomeriggio con questo es… L’idea era considerare un generatore modulo p e trovare condizioni sulle somme invece che sulle produttorie che mi sembrano difficili da gestire (oltreche non saprei come fare entrare in gioco le condizioni altrimenti)… ma andando avanti ho trovato questo contro-esempio:
p=13
serie: 8 8 8 9 8 8 8 8 8 8 8
da cui le osservato che 8^(4) == 1 mod 13 si ha che le uniche possibilita sono:
8 == 8
8^2 ==12
8^3 == 5
8^4 == 1
8*9 == 7
8^2*9 ==4
8^3*9 == 6
8^4*9 == 9
d’altra la serie rispetta le ipotesi…
uff.. dopo la sommatoria di totienti e il secondo es che non riesco a fare in 24 ore… sara un piacere leggere le vostre sol!
p=13
serie: 8 8 8 9 8 8 8 8 8 8 8
da cui le osservato che 8^(4) == 1 mod 13 si ha che le uniche possibilita sono:
8 == 8
8^2 ==12
8^3 == 5
8^4 == 1
8*9 == 7
8^2*9 ==4
8^3*9 == 6
8^4*9 == 9
d’altra la serie rispetta le ipotesi…
uff.. dopo la sommatoria di totienti e il secondo es che non riesco a fare in 24 ore… sara un piacere leggere le vostre sol!
oooops... evidentemente con i generatori avevo imposto solo che la condizione fosse verificata per i possibili ord_8 (13), ovvero 2 3 4 e 6 e 12, incappando in quella fregatura... anche se sinceramente non ne sarei troppo sicuro... sorry
Non credo che ci riprovero, cmq mi pare che la difficolta piu grossa con i generatori fosse trovare condizioni su quell'm tale che G^m==2 mod 13... che altrimenti ogni ragionamento risultava uguale per tutti i valori, non solo 2....
forse e meglio qualche altra via...
bah! cmq ora faro altro: mi devo informare sull'equilibrio delle fasi condensate...
Non credo che ci riprovero, cmq mi pare che la difficolta piu grossa con i generatori fosse trovare condizioni su quell'm tale che G^m==2 mod 13... che altrimenti ogni ragionamento risultava uguale per tutti i valori, non solo 2....
forse e meglio qualche altra via...
bah! cmq ora faro altro: mi devo informare sull'equilibrio delle fasi condensate...
...ma infatti sono convinto (certo, ci si può sempre sbagliare!) che quel 2 lì non abbia alcun significato particolare, e che si possa generalizzare il risultato ad un qualunque residuo dell'insieme $ \{2, 3, \ldots, p-1\} $. E soprattutto ho un'idea per dimostrarlo! Spero soltanto di riuscire a darle forma...info ha scritto:[...] cmq mi pare che la difficolta piu grossa con i generatori fosse trovare condizioni su quell'm tale che G^m==2 mod 13... che altrimenti ogni ragionamento risultava uguale per tutti i valori, non solo 2...
visto che è appunto lui il principale fornitore di problemi "per i giovani del forum", avrà un briciolo di diritto di risolvere in pace uno dei pochi problemi non suoi, non credi?MindFlyer ha scritto:Sì, ok.......HiTLeuLeR ha scritto:E soprattutto ho un'idea per dimostrarlo! Spero soltanto di riuscire a darle forma...
Magari, quando la tua idea avrà una forma, aspetta un po' prima di postarla, e lascia spazio ai "giovani". Ché altrimenti non si faranno mai le ossa, non credi?
_k_
No, non lo credo affatto! Il tuo discorso avrebbe forse senso altrove, ma non qui, nel subforum di TdN, dove si contano dozzine di problemi irrisolti ai quali potersi dedicare. Curiosamente capita poi che di questi la quasi totalità sia stata proposta dal sottoscritto. Sottoscritto che non ha certo alcuna intenzione di risolvere i problemi ch'egli stesso propone. Dunque di che preoccuparsi? Non c'è rischio che i "più giovani" restino colle braccia conserte, non ti pare? E ciò detto vado abbozzando la soluzione al problema di Azarus, che tu lo gradisca o meno, Flyer.MindFlyer ha scritto:Magari, quando la tua idea avrà una forma, aspetta un po' prima di postarla, e lascia spazio ai "giovani". Ché altrimenti non si faranno mai le ossa, non credi?
Sinceramente mi sento di spezzare una lancia per Hit.
In fondo se uno ha una soluzione, perchè non dovrebbe postarla; nessuno obbliga un altro potenziale solutore a leggerla. Inoltre nessuno vieta di postare la propria, anche se il problema avesse già 30 soluzioni diverse...
La matematica è sempre stata (almeno per me) farsi delle domande e (cercare di) darsi delle risposte, in modo da porsi altre domande: anche una soluzione non tua può darti uno spunto per qualcosa di nuovo; se non si sa fare di meglio che leggersi le risposte altrui, forse è meglio lasciar perdere...
In fondo se uno ha una soluzione, perchè non dovrebbe postarla; nessuno obbliga un altro potenziale solutore a leggerla. Inoltre nessuno vieta di postare la propria, anche se il problema avesse già 30 soluzioni diverse...
La matematica è sempre stata (almeno per me) farsi delle domande e (cercare di) darsi delle risposte, in modo da porsi altre domande: anche una soluzione non tua può darti uno spunto per qualcosa di nuovo; se non si sa fare di meglio che leggersi le risposte altrui, forse è meglio lasciar perdere...
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Come previsto, si generalizza!
Claim: siano $ p \ge 3 $ un numero primo naturale ed $ a_1, a_2, ... , a_{p-2} $ una sequenza di interi tali che, per ogni $ k = 1, 2, \ldots, p-2 $: $ p \nmid a_k $ e così pure $ p \nmid (a_k^k - 1) $. E allora, comunque scelto un residuo $ r\in\{2, 3, \ldots, p-1\} $, esistono $ t = 1, 2, \ldots, p-2 $ e una $ t $-upla $ (i_1, i_2, \ldots, i_t) $ estratta dall'insieme $ \{1, 2, \ldtos, p-2\} $, con $ i_1 < i_2 < \ldots < i_t $, per cui $ \displaystyle \prod_{k=1}^t a_{i_k} \equiv r \bmod p $.
Dim.: poiché $ p $ è primo in $ \mathbb{N} $, esiste $ g\in\mathbb{Z} $ tale che $ \mbox{ord}_p(g) = \varphi(p) = p-1 $ (si dice in questi casi che $ g $ è un generatore $ \bmod\: p $, oppure una radice primitiva $ \bmod\: p $). Ergo, per ogni $ k = 1, 2, \ldots, p-2 $, esiste $ \alpha_k \in \{0, 1, \ldots, p-2\} $ tale che $ a_k \equiv g^{\alpha_k} \bmod p $, ché $ \gcd(p, a_k) = 1 $. Osserviamo che, per ogni $ k = 1, 2, \ldots, p-2 $, deve pure ammettersi $ \alpha_k > 0 $, ché altrimenti $ a_k \equiv 1 \bmod p $, e quindi $ a_k^k \equiv 1 \bmod p $, contro le ipotesi.
Ciò premesso, poniamo $ \mathcal{A}_0 = \{0\} $ ed $ \mathcal{A}_{k+1} = \mathcal{A}_k \oplus \{0, \alpha_{k+1}\} $, per ogni $ k = 0, 1, \ldots, p-3 $. Qui "$ \oplus $" denota la somma diretta in $ \mathbb{Z}/(p-1)\mathbb{Z} $, nel senso che ogni elemento del generico insieme della sequenza $ \mathcal{A}_0, \mathcal{A}_1, \ldots, \mathcal{A}_{p-2} $ s'intende calcolato $ \bmod\: (p-1) $. Ebbene, a questo punto si tratta semplicemente di dimostrare il seguente:
Lemma: per ogni $ k = 0, 1, \ldots, p-2 $: $ |\mathcal{A}_k| \geq k + 1 $. Perciò, in particolare: $ |\mathcal{A}_{p-2}| = p-1 $.
Bene, posso lasciarne la dimostrazione a te, Mind? O credi davvero che i pargoli abbiano la maturità necessaria e sufficiente per affrontare un problema del genere, quando qui in Italia, per via delle idee bislacche che si vanno sponsorizzando, già ricorrere al teorema di Dirichlet o al postulato di Bertrand suscita una sorta di sdegno generalizzato? E pensare che alle Olimpiadi Nazionali Bulgare del 2004 è stata proposta... la dimostrazione del teorema di Cauchy-Davenport.
Dim.: poiché $ p $ è primo in $ \mathbb{N} $, esiste $ g\in\mathbb{Z} $ tale che $ \mbox{ord}_p(g) = \varphi(p) = p-1 $ (si dice in questi casi che $ g $ è un generatore $ \bmod\: p $, oppure una radice primitiva $ \bmod\: p $). Ergo, per ogni $ k = 1, 2, \ldots, p-2 $, esiste $ \alpha_k \in \{0, 1, \ldots, p-2\} $ tale che $ a_k \equiv g^{\alpha_k} \bmod p $, ché $ \gcd(p, a_k) = 1 $. Osserviamo che, per ogni $ k = 1, 2, \ldots, p-2 $, deve pure ammettersi $ \alpha_k > 0 $, ché altrimenti $ a_k \equiv 1 \bmod p $, e quindi $ a_k^k \equiv 1 \bmod p $, contro le ipotesi.
Ciò premesso, poniamo $ \mathcal{A}_0 = \{0\} $ ed $ \mathcal{A}_{k+1} = \mathcal{A}_k \oplus \{0, \alpha_{k+1}\} $, per ogni $ k = 0, 1, \ldots, p-3 $. Qui "$ \oplus $" denota la somma diretta in $ \mathbb{Z}/(p-1)\mathbb{Z} $, nel senso che ogni elemento del generico insieme della sequenza $ \mathcal{A}_0, \mathcal{A}_1, \ldots, \mathcal{A}_{p-2} $ s'intende calcolato $ \bmod\: (p-1) $. Ebbene, a questo punto si tratta semplicemente di dimostrare il seguente:
Lemma: per ogni $ k = 0, 1, \ldots, p-2 $: $ |\mathcal{A}_k| \geq k + 1 $. Perciò, in particolare: $ |\mathcal{A}_{p-2}| = p-1 $.
Bene, posso lasciarne la dimostrazione a te, Mind? O credi davvero che i pargoli abbiano la maturità necessaria e sufficiente per affrontare un problema del genere, quando qui in Italia, per via delle idee bislacche che si vanno sponsorizzando, già ricorrere al teorema di Dirichlet o al postulato di Bertrand suscita una sorta di sdegno generalizzato? E pensare che alle Olimpiadi Nazionali Bulgare del 2004 è stata proposta... la dimostrazione del teorema di Cauchy-Davenport.
Ultima modifica di HiTLeuLeR il 12 ago 2005, 01:36, modificato 2 volte in totale.
E a questo proposito, cito testualmente le parole di un celeberrimo problem solver della grande madre Russia, donate ai posteri quand'egli muoveva ancora i primi passi nell'incantato mondo della Matematica olimpica: "I suppose sometimes it's very useful to read what others write".moebius ha scritto:[...] anche una soluzione non tua può darti uno spunto per qualcosa di nuovo; se non si sa fare di meglio che leggersi le risposte altrui, forse è meglio lasciar perdere...
Re: Come previsto, si generalizza!
Sarà un problema di notazione, ma per me questa scrittura non ha senso... Me la spieghi?HiTLeuLeR ha scritto: [...]
Ciò premesso, poniamo $ \mathcal{A}_0 = \{0\} $ ed $ \mathcal{A}_{k+1} = \mathcal{A}_k \oplus \{0, \alpha_{k+1}\} $, per ogni $ k = 0, 1, \ldots, p-3 $. Qui "$ \oplus $" denota la somma diretta in $ \mathbb{Z}/(p-1)\mathbb{Z} $, nel senso che ogni elemento del generico insieme della sequenza $ \mathcal{A}_0, \mathcal{A}_1, \ldots, \mathcal{A}_{p-2} $ s'intende calcolato $ \bmod\: (p-1) $
[...]
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...