[N] : Partizione 6,10,15

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Trovare il piu\' grande intero n che non sia esprimibile come 6x+10y+15z, dove x,y,z sono interi positivi.
 
 Una variante:
 Dati a,b,c interi positivi, trovare il piu\' grande intero n (dipendente, ovviamente, da a,b,c) che non sia esprimibile come ax+by+cz dove x,y,z sono interi positivi.
 (Quest\'ultimo mi e\' venuto in mente adesso, quindi non vi assicuro esista una soluzione semplice, ma lavorarci su non fa male).
 
 Ripeto l\'osservazione (giusta) di EvaristeG: sarebbe bello che anche altre persone partecipassero al forum, non i soliti quattro gatti...

DB85 · Messaggio da **DB85** » 01 gen 1970, 01:33

Allora noi dobbiamo trovare il più grande intero non esprimibile nella forma
 
 6x + 10y + 15z con x, y, z >=0 (1)
 
 Riscriviamo la relazione come:
 
 3*(2x + 5z) + 10y (2)
 
 2x + 5z assume tutti i valori interi a partire da 2*5 - 2 - 5 + 1 = 4, ossia
 la (2) equivale a:
 
 3*(t + 4) + 10y = 3t + 12 +10y
 
 Ora, 3t + 10y assume tutti i valori a partire da 3*10 - 3 - 10 + 1 = 18
 e quindi la formula esprime tutti i valori a partire da 30. Dunque -se non ho sbagliato- 29 è il più grande intero non esprimibile con la (1)
 
 Se non erro, sotto l\'ipotesi che a, b, c non abbiano fattori comuni, quello che ti è venuto in mente è il problema di Frobenius, che non è ancora stato risolto per n=3 (ossia il tuo caso). <IMG SRC="images/forum/icons/icon_wink.gif">

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

Ciao a tutti.
 
 Scusate la pignoleria.La risposta 29 è esatta, ma c\'è un piccolo errore nel ragionamento di DB.
 
 DB ha dimostrato che 29 non si può ottenere se 2x+5z fa almeno 4.
 Non ha provato però che non si può ottenere con 2x+5z che vale meno di 4 (0 e 2 sono gli altri valori possibili). Ora, qui siamo stati fortunati, perché con 0 e 2 effettivamente non si può, ma andrebbe scritto...
 
 Del resto, se questo filone di ragionamento funzionasse sempre, il problema di Frobenius non sarebbe tutto questo granché...
 
 Ciao.
 
 M.
 [addsig]

DB85 · Messaggio da **DB85** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-09-23 10:09, marco wrote:
 
 Scusate la pignoleria.La risposta 29 è esatta, ma c\'è un piccolo errore nel ragionamento di DB.
 
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Non sei pignolo, far notare le sviste è l\'unico modo che può indurmi a migliorare. Ti ringrazio per questo... Le critiche e i suggerimenti sono sempre ben accetti, soprattutto se vengono da uno del tuo calibro! <IMG SRC="images/forum/icons/icon_smile.gif"> [ Questo Messaggio è stato Modificato da: DB85 il 23-09-2004 10:26 ]

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Allora, controllando, DB85 ha ragione. Il secondo problema e\' il problema di fröbenius:
 dati n interi positivi distinti {a[k]}, il cui MCD e\' uno, trovare il massimo numero intero N non esprimibile nella forma Sum[C[k]a[k],k=1...n] dove C sono numeri interi positivi.
 E\' stato risolto negli anni ottanta nel caso n = 3, il caso generale e\' ancora irrisolto.
 [ Questo Messaggio è stato Modificato da: Catraga il 23-09-2004 10:32 ]