ancora residui..

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

ancora residui..

Messaggio da jordan » 12 ott 2007, 01:35

a mio parere questo è uno dei piu simpatici che abbia fatto..

prendiamo un numero n di 3 cifre.
calcoliamo i resti modulo 2, 3, 4, 5, 6, 7, 8, 9 e 10.
facciamo la somma di tali resti e la chiamiamo S(n).

a) trovare il minimo di S(n)
b)trovare il massimo di S(n)

Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 » 12 ott 2007, 08:40

a) ovviamente S(n) non può essere uguale a 0 perchè n è di 3 cifre e il più piccolo numero congruo a 0 modulo 2,3,4,5,6,7,8,9,10 è 2520.Sappiamo che:

$ 2520=2^3*3^2*5*7 $. Ora per trovare il minimo S(n) dobbiamo fare in modo che S(n) sia 0 in quanti più moduli possibili. Quindi n è un divisore di 2520.
Vediamo che per n=360 S(n)=3. Dimostriamo che S(n) non può essere minore di 3.
1)S(n) non è mai uguale a 1. Infatti per essere uguale a 1 dovrebbe essere 0 in tutti i moduli tranne 1. Però notiamo che i moduli 2,4,8 3,6,9 5,10 si coimplicano, ossia se un numero non è congruo a 0 modulo 1 di essi, allora non lo sarà modulo gli altri. L'unico modulo che nn implica nessun altro è 7, però ponendo n congruo a 0 modulo 2,3,4,5,6,8,9,10 otteniamo n=360, che come già detto ha S(n)=3.
2)S(n) non è mai uguale a 2.Per un ragionamento analogo al punto 1, avremo che S(n) deve essere congruo a 0 in tutti i moduli meno al massimo 2. Poichè però i moduli 2,4,8 3,6,9 5,10 si coimplicano tra loro, allora S(n) sarà certamente congruo a 0 modulo 2,3,4,6,8,9 altrimenti se così nn fosse S(n) sarebbe diverso da 0 in almeno tre moduli, impossibile. Quindi
$ n=2^3*3^2*... $
2.1)Ora se n è diverso da 0 modulo 5 e modulo 10, dovrà essere obbligatoriamente congruo a 0 modulo 7. Analizzando il caso viene n=504 e S(n)=8.
2.2)Se n è invece diverso da 0 modulo 7, sarà congruo a 0 modulo 5 e 10 e avremo n=360, che da S(n)=3.
Quindi il minimo di S(n) è 3 per n=360.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 12 ott 2007, 11:07

good, simpatico no?
e il massimo?

Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 » 12 ott 2007, 14:02

b)Ragioniamo analogamente.
Affinchè S(n) sia massimo, il resto di n nei moduli sopracitati deve essere massimo in quanti + moduli possibili. D'altro canto, è un fatto noto che, dati dei moduli $ m_1,m_2,...,m_k $ il numero che massimizza S(n) è $ mcm(m_1,m_2,...,m_k)-1 $. Nel nostro caso $ mcm(2,3,4,5,6,7,8,9,10)-1=2519 $ e $ S(n)=40 $che è troppo grande per noi. Quindi come prima dobbiamo togliere qualche modulo.
Ricordando dalla parte a della soluzione che l'unico modulo che nn ne coimplica altri è 7, proviamo con $ mcm(2,3,4,5,6,8,9,10)-1=359 $. Per n=359 $ S(n)=1+2+3+4+5+2+7+8+9=35 $.Dimostriamo che S(n) non è mai maggiore di 35. Escludendo solo 8 dal nostro mcm abbiamo n=314 e S(n)=34. Escludendo solo 9 abbiamo n=279 e S(n)=1+3+4+3+6+7=24. Escludendo solo 10 abbiamo n=251 e S(n)=1+2+3+1+6+7+8+1=29. Il massimo S(n) è quindi 35 con n=359.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 16 ott 2007, 11:04

Boh, a me pare un po' piu' TdN, che Combinatioria, ma comunque...
Alex89 ha scritto:L'unico modulo che nn implica nessun altro è 7, però ponendo n congruo a 0 modulo 2,3,4,5,6,8,9,10 otteniamo n=360, che come già detto ha S(n)=3.
Capisco che e' la mia e' un'obiezione questione pignolesca e asfittica, ma cosi' dimostri solo che le candidate soluzioni sono multiple di 360, e, sfortunatamente, 360 non e' l'unico multiplo di 360 con tre cifre. Poi, che 720 vada anche peggio di 360, e' ovvio, ma andrebbe detto.

In alternativa, potevi dire che risolvi il sistema modulo 2520, con le condizioni 0 su tutti i moduli e 1 su mod 7, che ha soluzione 360 . 5, che ha quattro cifre.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Rispondi