Un bulgaro di Caldé

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Azarus
Messaggi: 580
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Un bulgaro di Caldé

Messaggio da Azarus » 08 ago 2005, 00:59

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

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 08 ago 2005, 14:43

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! :?

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 10 ago 2005, 00:51

Il tuo presunto controesempio non va bene, info! Nella sequenza da te suggerita, infatti, si ha $ a_8 = 8 $. Senonché $ 8^8 \equiv 1 \bmod 13 $. Deh, finalmente un quesito interessante proposto da altri... 8)

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 10 ago 2005, 09:31

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 :oops:

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...

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 10 ago 2005, 10:39

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...
...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... :roll: :mrgreen:

MindFlyer

Messaggio da MindFlyer » 10 ago 2005, 10:49

HiTLeuLeR ha scritto:E soprattutto ho un'idea per dimostrarlo! Spero soltanto di riuscire a darle forma... :roll: :mrgreen:
Sì, ok.......
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?

ReKaio
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

Messaggio da ReKaio » 10 ago 2005, 13:37

MindFlyer ha scritto:
HiTLeuLeR ha scritto:E soprattutto ho un'idea per dimostrarlo! Spero soltanto di riuscire a darle forma... :roll: :mrgreen:
Sì, ok.......
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?
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?
_k_

MindFlyer

Messaggio da MindFlyer » 10 ago 2005, 14:24

Certo che credo che abbia il diritto di risolverlo in pace! Chi glielo nega?

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 10 ago 2005, 17:09

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?
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. :evil:

MindFlyer

Messaggio da MindFlyer » 10 ago 2005, 17:13

Fai come vuoi, il mio era solo un consiglio. :?

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 10 ago 2005, 17:29

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...
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...

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Come previsto, si generalizza!

Messaggio da HiTLeuLeR » 10 ago 2005, 17:37

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. :twisted: 8)
Ultima modifica di HiTLeuLeR il 12 ago 2005, 01:36, modificato 2 volte in totale.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 10 ago 2005, 17:44

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...
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".

MindFlyer

Messaggio da MindFlyer » 10 ago 2005, 17:51

Oh, ma che vi prende a tutti? Troppo sole? Troppe donne per la testa?
Ho solo fatto notare a HiTLeuLeR che poteva ritardare la pubblicazione della sua soluzione. Mica gli ho impedito di esprimersi.

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Re: Come previsto, si generalizza!

Messaggio da moebius » 10 ago 2005, 17:58

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) $
[...]
Sarà un problema di notazione, ma per me questa scrittura non ha senso... Me la spieghi?
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...

Rispondi