X jack 202 ed altri

In questo forum vengono proposti i sondaggi che verranno fatti sul sito delle olimpiadi

Moderatore: tutor

Bloccato
Ospite

Messaggio da Ospite » 01 gen 1970, 01:33

Come sei arrivato alla formula (a-1)(b-1)-1 nel gioco delle uova (o centesimi) x calcolare il massimo numero nn componibile????????
<BR>Risp. please
<BR>10Q (thank you)

Avatar utente
ale86
Messaggi: 613
Iscritto il: 01 gen 1970, 01:00
Località: ovunque

Messaggio da ale86 » 01 gen 1970, 01:33

Io ho notato che il numero che ti risulta è sempre a*(b-1)-b, che è uguale a quello che ha trovato jack. Succede perchè moltiplicando a per ogni numero naturale da 1 fino a b-1 il resto della divisione per b cambia sempre se i due numeri sono primi tra loro (infatti se non succedesse non lo sarebbero). a*(b-1) è il numero più basso della sua classe di resti e il più alto non ottenibile è perciò a*(b-1)-b. E\' il massimo numero non ottenibile perchè a*b è congruo a 0 in modulo b, a*(b+1) ha lo stesso resto di a....
<BR>Spero di non aver scritto caz..ate

jack_202
Messaggi: 33
Iscritto il: 01 gen 1970, 01:00
Località: Chieti

Messaggio da jack_202 » 01 gen 1970, 01:33

Parto con l\'esempio numerico
<BR>(ipotesi a minore di b e MCD(a;b)=1)
<BR>
<BR>a=5
<BR>b=7
<BR>
<BR>l\'inverso di 7 modulo 5 è 3, dunque possiamo costruire tutti i k nella forma
<BR><pre>
<BR>k=5d con k maggioreuguale 0*7
<BR>k=5d+1 con k maggioreuguale 3*7
<BR>k=5d+2 con k maggioreuguale 1*7
<BR>k=5d+3 con k maggioreuguale 4*7
<BR>k=5d+4 con k maggioreuguale 2*7
<BR></pre><br>
<BR>Nel caso generico, detto c l\'inverso di b modulo a, possiamo
<BR>costruire tutti i numeri nella forma
<BR><pre>
<BR>k=ad+n con k maggioreuguale (nc mod a)*b
<BR>[0 minoreuguale n minore a]
<BR></pre>
<BR>Ma il massimo valore che può assumere (nc mod a) è,
<BR>ovviamente, (a-1), dunque il più grande numero NON costruibile è
<BR>
<BR>(a-1)*b - a
<BR>
<BR>ovvero
<BR>
<BR> (a-1)(b-1) - 1
<BR>
<BR>Ti convince?
<BR>
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: jack_202 il 28-11-2002 16:23 ]

Bloccato