2 giochi simili ...

[manto51]

Come altre volte, quando non riesco a venire a capo di un gioco, chiedo aiuto al forum. Vi garantisco però che ci ho provato, eccome ... ma senza successo. Questi sono i due giochi, diversi tra loro ma in sostanza uguali:
1) al casinò 5 e 8 esistono solo gettoni da 5 euro e gettoni da 8 euro. Qual è la puntata più alta che non può essere effettuata ?

2) Supponiamo di avere 2 tipi di mattoncini a base quadrata (tipo lego), un tipo alto 8 cm e l'altro tipo alto 11 cm.
Possiamo sovrapporre una quantità qualsiasi di mattoncini dei 2 tipi, nell'ordine che preferiamo.
Qual è la misura della torre più alta che non è possibile costruire ?

Traduzione matematica: qual è il più grande numero intero positivo che non può essere espresso come somma di un multiplo di 5 e di un multiplo di 8 (nel secondo gioco, come somma di un multiplo di 8 e di 11) ?

Ho cercato le soluzioni intere dell'equazione diofantea 5x + 8y = n, che è sempre risolvibile per qualsiasi valore di n perché 5, 8 sono primi tra loro, peccato che nel nostro caso x e y devono essere non solo interi ma anche positivi e bisogna quindi aggiungere la condizione che x e y siano maggiori o uguali a zero.

Poi ho provato con le combinazioni con ripetizione dei gettoni (k gettoni di 2 tipi) vedendo come varia la somma dei valori dei gettoni al variare di k, ma non sono arrivato a nulla di significativo.

Le soluzioni, trovate bovinamente per tentativi, dovrebbero essere 27 per il primo gioco e 69 per il secondo.
Esiste una "formula generale" che permette di calcolarle senza procedere come un bovino (come ho fatto io)
grazie

[kobeilprofeta]

Per il primo andrei ad "occhio".
Avendo il 5, sai che puoi guardare solo l'ultima cifra (per esempio se puoi generare il 16, allora puoi generare anche 26,36,...) ed inoltre
$1 <=> 6$
$2<=>7$
...
$5<=>0$


Bene, ora partiamo con la tabellina dell'8:
8,16,24,32,40. Dal 40 in poi siamo a posto perchè
16=1 mod 5
32=2 mod 5
8=3 mod 5
24=4 mod 5
40=0 mod 5

Poi dovresti controllare i numeri =0 mod 5 prima del 40, quelli =2 mod 5 prima del 32, etc...

[Pachisi]

Provo il primo, visto che il procedimento per il secondo e` uguale.
Noti che tutti i numeri della forma $5k$ si possono formare, infatti sono tutti i multipli di $5$. Tutti i numeri della forma $5k+1$ maggiori o uguali a $16$ si possono formare, infatti $1,6,11$ non si possono fare, mentre per $16$ usi due volte l'otto; per i numeri di questa forma maggiori di $16$ basta che sommi $5$ ripetutamente. Tutti i numeri della forma $5k+2$ maggiori o uguale a $32$ si possono formare. Tutti i numeri della forma $5k+3$ maggiori o uguali a $8$ si possono formare. Tutti i numeri della forma $5k+4$ maggiori o uguali a $24$ si possono formare. Il maggior numero che non si puo` formare e` $32-5=27$.

[orsoulx]

Dati m ed n interi positivi, se MCD(m,n)=1, il più grande numero che non si può ottenere sommando multipli di m ed n è mn-(m+n), altrimenti tutti gli infiniti non multipli del MCD(m,n) sono impossibili.

[axpgn]

Premesso che non ho capito molto ( ), potresti spiegare meglio questa frase ?

"orsoulx":... altrimenti tutti gli infiniti non multipli del MCD(m,n) sono impossibili.

Perché in questo caso [$M.C.D.(5,8)=1$] è vera ... non esistono "non multipli" di uno ...

Cordialmente, Alex

[orsoulx]

"axpgn":potresti spiegare meglio questa frase ?

altrimenti=quando MCD(m,n)>1, ad esempio MCD(6,15)=3, si possono ottenere solo multipli di 3, ed essendo tutti quelli che non lo sono infiniti, non esisterà il più grande di questi, come richiesto dal problema.
Ciao

[manto51]

Innanzi tutto ringrazio tutti quelli che hanno risposto alla mia domanda, ora devo leggere attentamente le soluzioni proposte, per capirle.
Uno di voi (orsolux) ha scritto:
"dati m,n interi positivi, se MCD(m,n) = 1 (cioè m,n sono primi tra loro) allora il più grande numero che non si può ottenere sommando multipi di m e di n è (m x n) - (m + n)

E' certamente vero ma, confesso la mia ignoranza, è la prima volta che lo leggo.
E' un teorema di teoria dei numeri ? Posso avere la dimostrazione ?
grazie

[Pachisi]

Provo a dare una dimostrazione del fatto postato da orsoulx.

Siano $m$ ed $n$ interi con $m

Cita

Segnala

[axpgn]

@orsoulx

Ho interpretato "altrimenti=il più grande numero che si può ottenere sommando multipli di m ed n NON è mn-(m+n)"

Cordialmente, Alex

[orsoulx]

@manto51:
si può dimostrare sfruttando le proprietà delle classi di resto modulo uno dei due numeri dati.
Forse coi numeri è più chiaro, il passaggio alle incognite non modifica alcunché di sostanziale.
Prendiamo 8 e 11; le classi di resto modulo 8 (11 andrebbe altrettanto bene) sono 8: 0,1,...7.
Aggiungendo ad una somma s già trovata un numero qualsiasi di 8 si ottengono tutti e soli i numeri della stessa classe maggiori di s.
I primi 8 multipli di 11 (da 1 a 8) appartengono a classi diverse, se così non fosse la loro differenza (in valore assoluto) sarebbe multipla tanto di 8 quanto di 11 e più piccola di 88, mentre MCD(8,11)=1 garantisce che mcm(8,11)=8*11.
Tutti i multipli di 8 si possono ottenere ed allora l'ultima classe raggiungibile con multipli di 11 e quella di 11*7 (in questo caso è la classe 5).
L'ultimo numero non ottenibile sarà quello di questa classe immediatamente più piccolo di 77, cioè:
\(\displaystyle 11 \cdot 7-8=11 \cdot 8-8-11=11 \cdot 8-(8+11) \).
Ciao