Problema dalla Nuova Zelanda...

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Problema dalla Nuova Zelanda...

Messaggio da Alex89 » 18 apr 2007, 21:53

Credo sia semplice... cmq astenersi super-esperti et similia.

Tre macchinari possono leggere e stampare fogli con scritti coppie di interi positivi. La prima, leggendo un foglio con su scritto due interi (a,b) ne stampa una nuova con scritto (a+1,b+1). La seconda, leggendo un foglio con su scritto due interi (a,b), se entrambi gli interi sono pari ne stampa una con su scritto (a/2,b/2). La terza dopo aver letto due fogli con su scritto (a,b) e (b,c) ne stampa una con su scritto (a,c). I fogli sono riutilizzabili. All'inizio abbiamo solo un foglio con su scritto (5,19). E' possibile ottenere i fogli (1,50) e (1,100)?

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

Messaggio da jordan » 19 apr 2007, 16:48

Ciao a tutti, sn paolo, questo è il mio primo messaggio ke mando..spero di avere almeno azzeccato la soluzione.. allora…prima di tutto in ogni caso se partiamo dalla coppia di interi(5, 19) con 5 < 19 otteniamo tutte coppie (a, b) con a < b (è facilissimo verificarlo in ogni caso). Dato che (5, 19) è una coppia della forma (a, a+7k) dimostriamo che tutte le possibili coppie di interi che possiamo creare sono della forma (a, a+7k). Allora..nel primo caso. (a, a+7k)-(a+1, a+1+7k)=(b, b+7k) ponendo b=a+1. Caso II, a deve essere pari e k anke quindi (a, a+7k)-(a/2, (a+7k)/2)=(b, b+7c) ponendo a=2b e k=2c. Caso III. (a, a+7k)(a+7k, a+7k+7c)-(a, a+7k+7c)=(a, a+7(k+c)). Dimostriamo adesso infine che è possibile avere tutte e sole le coppie di interi positivi (a, a+7k) con a,k in N, partendo dalla sola coppia (5, 19). Per far questo è sufficiente trovare la coppia (1, 8):infatti usando ripetutamente con la prima makkina otteniamo tutte le coppie della forma (a, a+7) e infine utilizzando la terza tutte le coppie della forma (a, a+7k). Allora…praticamente..
Partiamo da (5, 19) -(i)(6, 20)-(ii)(3, 10)-(i)(4, 11)-(i)(5, 1 2)-…fino a -(i)(25, 32)
Utilizzando adesso la terza makkina otteniamo (4, 11)(11, 18)-(4, 18) e poi (18, 25)(25, 32)-(18, 32) e quindi infine (4,18)(18, 32)-(4, 32).
Utilizzando adesso la seconda makkina abbiamo (4, 32)-(2, 16)-(1, 8).
In conclusione possiamo formare tutte e sole le coppie di interi positivi della forma(a, a+7k)
Quindi (1, 50) possiamo realizzarla dato che 50-1=49≡0 mod 7 mentre (1, 100) non possiamo realizzarla perche 100-1=99 ≡1mod 7. spero sia giusta.. :D

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

Messaggio da Alex89 » 19 apr 2007, 21:35

Perfetto!

Rispondi