R: Il Gioco dei 4 numeri.

Forum dedicato ai quesiti irrisolti presenti nella collezione di Base5, nel vecchio forum ed in quello attuale.

Moderatori: Gianfranco, Bruno

Rispondi
Br1
Livello 6
Livello 6
Messaggi: 465
Iscritto il: mer feb 21, 2007 5:53 pm
Località: Bologna

R: Il Gioco dei 4 numeri.

Messaggio da Br1 » lun lug 23, 2007 1:56 pm

Admin ha scritto:Dalla sezione "Il gioco dei 4 numeri"

Il gioco dei 4 numeri:

Vai direttamente alla pagina della collezione
Ho aperto questo "irrisolto" venerdì scorso
e ho provato a scarabocchiare qualcosa.

Riporto via via i punti che finora ho avuto
il tempo di trattare e, per comodità, utilizzo
una rappresentazione del gioco simile a quella
indicata da Gianfranco come alternativa.

2. Trovare un quadrato che termini dopo 9 passaggi.
Eccolo:

Immagine

3. E' vero che, dati 4 numeri, il massimo numero di passaggi si ha quando tali numeri sono disposti in ordine crescente? O decrescente?
In generale, no.
All'inizio, tuttavia, alcune prove mi avevano fatto
pensare "sì", quindi sono andato a cercarmi una
giustificazione algebrica... che però non son
riuscito a immaginare senza complicazioni di
passaggi e calcoli!
Allora ho pensato di scovare un controesempio...
Click!

5. E' vero che il gioco dei 4 numeri con A, B, C, D termina nello stesso numero di mosse del gioco con i numeri m + A, m + B, m + C, m + D? Se esiste un gioco che non termina nel primo caso, non terminerà neanche in tutti gli altri.
Sicuramente è così, come dimostra questa immagine:

Immagine

6. E' vero che il gioco dei 4 numeri con A, B, C, D termina nello stesso numero di mosse del gioco con i numeri mA, mB, mC, mD? Se esiste un gioco che non termina nel primo caso, non terminerà neanche in tutti gli altri.
Certo:

Immagine

7. Utilizzate il risultato precedente per dimostrare che ogni versione del gioco con numeri razionali ha un'equivalente con numeri interi positivi o nulli.
Direi così: click!

Considero le frazioni ridotte ai minimi termini.
In questo modo è possibile passare da un
gioco all'altro.
Anche qui, naturalmente, come nei due casi
precedenti, le differenze sul "1° passaggio"
vanno poi prese in valore assoluto.

8. E' vero che ogni gioco contenente soltanto 0 e 1 termina sempre?
Più in generale, è sufficiente considerare i casi
rappresentati nelle seguenti tabelle per concludere
che il gioco termina sempre anche quando i valori
utilizzati sono 0 e 1: click!

13. Dato un gioco, trovare tutti i suoi equivalenti per rotazione e per simmetria.

Immagine
Riporto qui alcune libere riflessioni, ma non sono
sicuro che rispondano veramente al problema
pensato da Gianfranco.

Si può comporre agevolmente uno schema come
questo, in cui si vede come ritornare al gioco di
partenza attraverso le rotazioni (R) e le simmetrie
(F).
Con la notazione \/ CBA \/ intendo esprimere questo:
all'operazione A faccio seguire l'operazione B e, dopo
quest'ultima, eseguo l'operazione C.
Se partiamo da \small  (a, \/b, \/c, \/d), per esempio, possiamo
ritrovare tale quaterna applicando, successivamente:
\small F_4,\/F_3,\/F_2\/, F_1\/ oppure \small \/F_4,\/F_3,\/R^2.

Per quaterne particolari, si potrebbe giungere alla
quaterna originaria in maniera più diretta, come
accade con \small  (a, \/a+d, \/a+2d, \/a+3d).

Si può inoltre dire che, data una quaterna \small  (a, \/b, \/c, \/d),
le quaterne da essa ottenute tramite l'applicazione
di rotazioni e simmetrie hanno tutte, proprio tutte,
la stessa durata, cioè terminano (se terminano) dopo
il medesimo numero di passaggi.
Fra parentesi, possiamo quindi affiancare questi giochi
derivati a quelli visti più sopra, in corrispondenza delle
domande 5 e 6.
Questa cosa si può spiegare direttamente anche così.
Ho immaginato la seguente figura, dove le R e le F
sono "unificate":

Immagine

In essa troviamo:

- seguendo le frecce orizzontali, tutte le quaterne
derivate mediante rotazioni:
a, b, c, d \; (I)
d, a, b, c \; (R)
c, d, a, b \; (R²)
b, c, d, a \; (R³)

- seguendo le frecce diagonali, tutte le quaterne
derivate mediante simmetrie:
a, d, c, b \; (F1)
b, a, d, c \; (F3)
c, b, a, d \; (F2)
d, c, b, a \; (F4).

Notiamo che ogni termine si trova sempre, in
ciascuna quaterna evidenziata, fra gli stessi due
termini, ossia quelli rispetto ai quali dovrà essere
calcolata la differenza in valore assoluto.
Per esempio, la b si trova sempre fra la a e la c e
ciò indipendentemente dall'ordine (reso inifluente
dal fatto che, appunto, lavoriamo con dei valori
assoluti).
Per la stessa ragione, anche le differenze del
primo passaggio, quelle del secondo, quelle del
terzo etc., si troveranno sempre fra gli stessi
due termini in tutti i giochi.
Pertanto, questo è il punto importante, al passaggio
n-esimo di uno qualsiasi dei giochi ottenuti da quello
principale, applicando rotazioni o simmetrie, i valori
assoluti saranno gli stessi (tutti e soltanto quelli),
pur se con un altro ordine.
Ecco un'altra immagine per rendere ancor più
evidente la cosa: click!

9. E' vero che ogni gioco contenente soltanto numeri minori di 3 termina sempre?
Sì.

Questa domanda non mi è sembrata per niente
facile, in prima e seconda e poi terza battuta.
Qualunque strada immaginassi, non riuscivo a
scansare tutti i casi e sottocasi che man mano
si stipavano nel mio pensiero.
Il poco tempo a disposizione e la simpatia che
provo per le cose "svelte", mi hanno quasi subito
portato a rinviare il confronto.
In effetti, è andata bene così.
Passando alle altre questioni, sono riuscito a
trovare una giustificazione (penso) che mi pare
snella e convincente.

I numeri considerati devono essere minori di 3,
per cui sono 0, 1, 2.
Tralasciamo i casi in cui la quaterna sia composta
da due coppie di numeri uguali oppure da una
terna di numeri uguali, dal momento che sono già
stati analizzati per l'ottava domanda.
Il problema, allora, diventa questo: dobbiamo
esaminare tutte le quaterne derivanti dalle
permutazioni di 0, 1, 2, X (dove la X potrà essere 0
oppure 1 oppure 2), cioè ventiquattro casi.
E' molto facile scriverli tutti con carta e penna, in
maniera ordinata, uno dopo l'altro:

012X
01X2
02X1
021X
0X12
0X21

12X0
120X
1X02
1X20
102X
10X2

2X01
2X10
201X
20X1
21X0
210X

X012
X021
X120
X102
X201
X210


Per quello che abbiamo stabilito nel quesito precedente
riguardo alle rotazioni e alle simmetrie, andiamo ora
a cancellare le quaterne derivanti da 0, 1, 2, X per
l'applicazione di qualche R o F (visto che hanno uguale
durata) e facciamo la stessa cosa con 0, 1, X, 2 etc.
In tal modo ci troviamo davanti a una situazione di
questo tipo: click! (dove la F4 è stata sostituita con il
concetto equivalente, ma più immediato, di specularità).
Da ventiquattro casi (anzi, molti di più, a causa della X)
siamo passati a tre. Sostituendo la X, ne troviamo
nove e li portiamo subito a otto, perché saltan fuori
due quaterne identiche.

A questo punto, si potrebbero fare altre considerazioni
per semplificare ulteriormente la questione, ma per me
è stato più semplice e diretto scrivere due o tre passaggi
sugli otto casi rimasti: eccoli.

Concludendo, pertanto, i giochi utilizzanti numeri non
maggiori di 2 terminano in tutti i casi.

Le cose appena dette sono utili anche per affrontare
la questione seguente.

1. E' possibile modificare il quadrato dell'esempio in modo che il gioco richieda un passaggio in più?

Immagine
Se per modifica intendiamo un diverso ordine dei
quattro numeri scelti, devo dire no.
Il motivo è lo stesso che mi ha permesso di rispondere
alla domanda precedente.

Come abbiamo visto sopra, fra tutte le permutazioni
dei numeri 9, 7, 5, 1, potremmo limitarci a esaminare
queste soltanto: \; 9, 7, 5, 1;\; 9, 7, 1, 5; \; 9, 5, 7, 1.
(Giusto per non riscrivere tutto il ragionamento fatto
prima, immaginiamo di sostituire, nell'ordine, 0, 1, 2, X
con 9, 7, 5, 1.)
Trascuriamo l'ultima quaterna perché sappiamo già
come finisce, ma poi vediamo che neppure le altre
soddisfano la richiesta: carta e penna alla mano,
infatti, la seconda porta agli stessi passaggi dell'ultima,
mentre la prima presenta tre passaggi in più.

D'altra parte, se al posto di 1 mettessimo 3, il gioco
durerebbe esattamente un passaggio in più rispetto
a quello proposto e questo perché tutte le quaterne
come \; (a, a±d, a±2d, a±3d) \; terminano dopo il
quarto passaggio:

Immagine





Alle rimanenti questioni sto ancora pensando... :roll:
Bruno

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 778
Iscritto il: mer apr 20, 2005 2:47 pm
Località: Benevento

Re: R: Il Gioco dei 4 numeri.

Messaggio da Admin » dom giu 01, 2008 8:39 pm

Questo topic e il relativo problema, sebbene sia passato inosservato, lo trovo molto interessante, soprattutto il mirabile lavoro di Bruno.

Dal canto mio provo a rispondere alla questione numero 10.
10. Esiste un gioco che non termina mai (ad es. diventa ciclico)?
No.

Per dimostrarlo consideriamo 4 numeri interi non negativi ossia a, b, c, d.
Analizziamo le relazioni di disuguaglianza che vi possono essere tra i 4 numeri.
Abbiamo solo 3 casi possibili, ossia:

1) a\/{\small \ge}\/b ; a\/{\small >}\/c ; a\/{\small >}\/d ; b\/{\small >}\/c ; b\/{\small >}\/d ; c\/{\small >}\/d .
2) a\/{\small \ge}\/b ; a\/{\small \ge}\/c ; a\/{\small \ge}\/d ; b\/{\small \le}\/c ; b\/{\small \ge}\/d ; c\/{\small \ge}\/d .
3) a\/{\small \ge}\/b ; a\/{\small \ge}\/c ; a\/{\small \ge}\/d ; b\/{\small \ge}\/c ; b\/{\small \ge}\/d ; c\/{\small \le}\/d .

Tutte le altre relazioni possibili si ottengono per rotazione oraria o antioraria (simmetria) di questi 3 casi.
I segni di uguaglianza nella 2°, 3°, 4°, 5° e 6° diseguaglianza del caso 1) non vanno messi perchè quelle situazioni specifiche sono comprese nei casi 2) e 3).

Analizziamo i 3 casi.
Partiamo dai casi 2) e 3), che sono più semplici.

caso 2)

Risolviamo il gioco utilizzando la rappresentazione tabellare alternativa;
Immagine
In pratica, dopo il primo passaggio si ottengono, nell'ordine, i seguenti 4 numeri non negativi:
  • a\/-\/b (dato che a\/{\small \ge}\/b)
  • c\/-\/b (dato che b\/{\small \le}\/c)
  • c\/-\/d (dato che d\/{\small \ge}\/d)
  • a\/-\/d (dato che a\/{\small \ge}\/d)
Dopo il secondo passaggio otteniamo i numeri non negativi:
  • |(a\/-\/b)\/-\/(c\/-\/b)|\/=\/(a\/-\/c) (dato che a\/{\small \ge}\/c)
  • |(c\/-\/d)\/-\/(c\/-\/b)|\/=\/(b\/-\/d) (dato che b\/{\small \ge}\/d)
  • |(a\/-\/d)\/-\/(c\/-\/d)|\/=\/(a\/-\/c) (dato che a\/{\small \ge}\/c)
  • |(a\/-\/d)\/-\/(a\/-\/b)|\/=\/(b\/-\/d) (dato che b\/{\small \ge}\/d)
A questo punto, si nota che dopo il 3° passaggio si ottengono 4 numeri uguali, ossia |(a\/-\/c)\/-\/(b\/-\/d)|.
Quindi dopo il 4° passaggio otteniamo tutti 0, quindi il gioco termina.

Da notare che se i 4 numeri iniziali non sono tutti diversi, il gioco potrebbe terminare anche con meno di 4 passaggi.

caso 3)

Anche in questo caso risolviamo il gioco utilizzando la rappresentazione tabellare alternativa;
Immagine
In pratica, dopo il primo passaggio si ottengono i seguenti 4 numeri non negativi:
  • a\/-\/b (dato che a\/{\small \ge}\/b)
  • b\/-\/c (dato che b\/{\small \ge}\/c)
  • d\/-\/c (dato che c\/{\small \le}\/d)
  • a\/-\/d (dato che a\/{\small \ge}\/d)
Dopo il secondo passaggio otteniamo i numeri non negativi:
  • |(a\/-\/b)\/-\/(b\/-\/c)|
  • (b\/-\/d) (dato che b\/{\small \ge}\/d)
  • |(d\/-\/c)\/-\/(a\/-\/d)|
  • (b\/-\/d) (dato che b\/{\small \ge}\/d)
A questo punto, si nota che dopo il 3° passaggio si ottengono 4 numeri uguali a due a due (1° = 4° ; 2° = 3°).
Quindi dopo il 4° passaggio otteniamo numeri uguali alternati (1° = 3° ; 2° = 4°).
A questo punto, dopo il 5° passaggio otteniamo tutti numeri uguali.
Per cui dopo il 6° passaggio otteniamo tutti numeri 0, quindi il gioco termina.

Anche in questo caso se i 4 numeri iniziali non sono tutti diversi, il gioco potrebbe terminare anche con meno di 6 passaggi.


caso 1)

In questo caso, supponiamo che i 4 numeri iniziali a, b, c, d, siano tutti diversi (nel caso ve ne siano due o più uguali, il gioco termina in massimo 3 passaggi (Vedi Bruno N.8)).
Risolviamo il gioco utilizzando la rappresentazione tabellare alternativa;
Immagine
In pratica, dopo il primo passaggio si ottengono i seguenti 4 numeri non negativi:
  • a\/-\/b (dato che a\/{\small \ge}\/b)
  • b\/-\/c (dato che b\/{\small >}\/c)
  • c\/-\/d (dato che c\/{\small >}\/d)
  • a\/-\/d (dato che a\/{\small >}\/d)
A questo punto analizziamo i 4 numeri ottenuti:
se essi hanno relazioni di disuguaglianza che rientrano nei casi 2) e 3) allora sicuramente il gioco termina, come mostrato in precedenza.

Per cui affinchè il gioco non termini, c'è bisogno che i 4 numeri ottenuti dopo il 1° passaggio siano in relazioni di disuguaglianza che rientrano nel caso 1); e c'è bisogno che lo siano anche quelli ottenuti dopo il 2° passaggio, dopo il 3°, e cosi via fino all'infinito.
Tuttavia, ad ogni passaggio, il numero più alto, tra i 4 ottenuti, è sempre inferiore o uguale a quello più alto ottenuto al passaggio precedente (ma mai superiore).
Per cui, alla lunga, inevitabilmente, si arriverà ad un passaggio in cui il numero più alto, tra i 4 ottenuti, sia prossimo a 0, e quindi il gioco terminerà.
In realtà si potrebbe pensare ad una situazione in cui ad ogni passaggio il numero più alto che si ottiene sia sempre lo stesso, ossia non diminuisca in valore.
Ciò, però, non è possibile all'infinito.
Infatti, riprendendo il gioco per il caso 1), all'inizio abbiamo che il numero più alto è a. Poi dopo il 1° passaggio il numero più alto è a-d.
Chiaramente i numeri più alti dei due passaggi sono uguali se d=0.
Supponiamo che d sia pari a 0.
In questo caso i numeri ottenuti dopo il 1° passaggio diventano:
  • a\/-\/b
  • b\/-\/c
  • c
  • a
dove a è il numero più alto.
Gli altri numeri, però, sono tutti diversi da 0, dato che abbiamo detto poco sopra che a non può essere uguale a b.
quindi ciò significa che al successivo 2° passaggio, di sicuro il numero più alto che si ottiene sarà inferiore ad a.

Per questo, quindi, il gioco, anche nel caso 1), termina sempre.

Quindi, in definitiva, qualunque siano i numeri interi non negativi iniziali, il gioco termina sempre.

SE&O

Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Rispondi