uova

[alberto]

abbiamo 3 tipi di scatole, di ognuno di questi ne abbiamo quantità illimitate: un tipo può contenere 22 uova, uno 9 e uno 6.
<BR>dire qual\'è il massimo numero di uova tale che quel numero di uova non può essere diviso in scatole in modo che tutte le scatole siano piene

[Tassinari_Luca]

La risposta è 47.
<BR>Invito a risolvere il medesimo problema considerando a,b,c, capienze delle scatole con ovviamente (a,b,c)=1.
<BR>Bye

[jack202]

Direi che è un problema assai in voga ultimamente...
<BR>ho il risolto il caso con due scatole con capacità A e B,
<BR>con (A,B)=1, il massimo numero NON \"costruibile\" è
<BR>
<BR>(A-1)(B-1) - 1
<BR>
<BR>per tre scatole ci penso...
<BR>
<BR>

[ale86]

Dovrebbe essere (con c minore dei tre numeri e a mod c > b mod c( altrimenti si invertano nella formula a e b):
<BR>a(b mod c-1)-a mod c(b mod c-1)+b
<BR>Non funziona se i resti di a e b sono uguali, se uno dei 2 è zero ( ma sono casi riconducibili alla formula di Jack (che ho ricavato anch\'io)), oppure se uno dei resti è uno. Se ce ne sono altri (molto probabile), comunicatemeli.
<BR>Ciao

[ale86]

Dopo mesi e mesi mi sono ricordato che non avevo mai postato neanche una traccia del ragionamento che avevo fatto. Se me lo ricordassi tutto potrei anche farlo, però....
<BR>Comunque avevo lavorato (come si vede dalla formula) sui resti mod c. Se non ricordo male avevo cercato il massimo valore non esprimibile con questi e in base a questo valore ero riuscito a trovare il relativo valore non esprimibile con a,b,c.
<BR>Dopo tutto questo tempo non potete pretendere di più... magari fra qualche mese mi torna in mente il ragionamento completo e lo posto.
<BR>

[XT]

Cosa intendi con mod di un numero?

[ale86]

mod c: modulo c
<BR>a mod c: resto della divisione di a per c

[publiosulpicio]

Secondo me conviene (ma non ho provato) elencare tutti i numeri costruibili e osservare qual è l\'ultimo ce resta escluso. Motivare che da un certo momeno in poi sono tutti costruibili è semplice, per esempio utilizzando solo due delle tre casse.

[publiosulpicio]

Dimenticate quello che ho scritto, ho fatto una confusione enorme

[lordgauss]

IMO 1983, n°3
<BR>Let a , b and c be positive integers, no two of which have a common divisor greater than 1. Show that 2abc - ab - bc - ca is the largest integer which cannot be expressed in the form xbc + yca + zab, where x, y, z are non-negative integers.

[publiosulpicio]

Posto la soluzione per gli interessati (non mia purtroppo) chi non sa l\'inglese si attacca....
<BR>We start with the lemma that bc - b - c is the largest number which cannot be written as mb + nc with m and n non-negative. [Proof: 0, c, 2c, ... , (b-1)c is a complete set of residues mod b. If r > (b-1)c - b, then r º nc (mod b) for some 0 <= n <= b-1. But r > nc - b, so r = nc + mb for some m >= 0. That proves that every number larger than bc - b - c can be written as mb + nc with m and n non-negative. Now consider bc - b - c. It is º (b-1)c (mod b), and not congruent to any nc with 0 <= n < b-1. So if bc - b - c = mb + nc, then n >= b-1. Hence mb + nc >= nc >= (b-1)c > bc - b - c. Contradiction.]
<BR>
<BR>0, bc, 2bc, ... , (a-1)bc is a complete set of residues mod a. So given N > 2abc - ab - bc - ca we may take xbc º N (mod a) with 0 <= x < a. But N - xbc > 2abc - ab - bc - ca - (a-1)bc = abc - ab - ca = a(bc - b - c). So N - xbc = ka, with k > bc - b - c. Hence we can find non-negative y, z so that k = zb + yc. Hence N = xbc + yca + zab.
<BR>
<BR>Finally, we show that for N = 2abc - ab - bc - ca we cannot find non-negative x, y, z so that N = xbc + yca + zab. N º -bc (mod a), so we must have x º -1 (mod a) and hence x >= a-1. Similarly, y >= b-1, and z >= c-1. Hence xbc + yca + zab >= 3abc - ab - bc - ca > N. Contradiction.
<BR>

[publiosulpicio]

° sta per conruo, non è venuto bene il simbolo