Girotondo numerico alla Flavio Giuseppe

[giobimbo]

Alcuni giorni fa ho trovato nel gruppo di discussione hobby.enigmi un interessante problema posto da Dario Uri (i link al newsgroup e al sito di Dario sono in fondo alla homepage di Base 5, alla voce "Collegamenti").

I numeri da 1 a n sono disposti in cerchio, in senso orario dal più piccolo al più grande. Indicando con p(1), p(2), p(3), ..., le posizioni sulla circonferenza occupate inizialmente dai numeri 1, 2, 3, ... una mossa consiste nel muovere il numero m dalla sua posizione di partenza p(m) alla posizione p(m + m modulo n), ovvero p(2m mod n); altre sue mosse lo manderanno successivamente in p(3m mod n), p(4m mod n), ecc. Quando muoviamo m mettiamo 0 al suo posto e il numero su cui finisce m dopo m passi sparisce, al suo posto rimane m.
Il gioco consiste nel rimanere con un solo numero maggiore di 0 facendo n-1 mosse, con l'unica limitazione di non muovere uno stesso numero due volte consecutive.

Qua sotto la soluzione di Dario Uri per n=12 in 11 mosse, i numeri sono messi in linea, con la convenzione solita che dopo il 12 si passa all'1; in blu il numero che verrà mosso, in rosso il numero che verrà mangiato.

1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 8 5 6 7 0 9 10 11 12
1 2 0 8 5 3 7 0 9 10 11 12
1 2 0 8 0 3 7 0 9 5 11 12
0 1 0 8 0 3 7 0 9 5 11 12
0 1 0 8 0 3 7 0 9 11 0 12
0 7 0 8 0 3 0 0 9 11 0 12
0 7 0 8 0 3 0 0 11 0 0 12
0 0 0 8 0 3 0 0 7 0 0 12
0 0 0 8 0 0 0 0 3 0 0 12
0 0 0 0 0 0 0 0 3 0 0 8
0 0 0 0 0 0 0 0 0 0 0 3

Un altro modo di scrivere questa soluzione, usando gli indici i = 1, 2, ..., n delle posizioni p(i):
8-4, 3-6, 5-10, 1-2, 11-10, 7-2, 10-9, 2-9, 6-9, 4-12, 9-12. Molto più veloce e si vede subito che se una mossa termina con il numero r la coppia seguente non può iniziare col numero r, segno che si è mosso due volte lo stesso numero.

Uno dei partecipanti alla discussione ha fatto un programma per computer, usando un algoritmo non ottimizzato, trovando che per n da 2 a 18 solo i valori n=2, 12 e 15 sono risolvibili, mentre per n=19 o più, il computer ci mette troppo tempo. Ragionandoci sopra ho trovato che n=30 ha una soluzione in 29 mosse, pertanto chiedo:

Problema 1. Escludendo i casi banali in cui vale 1 o 2, come dev'essere n affinché il problema sia risolvibile (condizione necessaria)?
Problema 2. Trovare una soluzione per n = 30.
Attenzione, ho cambiato le domande, vedere le parole in grassetto più avanti.


Il listato in linguaggio C del programma usato, più tutti gli interventi si trovano all'indirizzo:

http://groups.google.it/group/it.hobby. ... c525e07d05

[Sancho Panza]

Per quanto riguarda il problema 1 le condizioni necessarie perché il problema sia risolvibile possono essere tante,
ma la condizione principale ritengo che sia la seguente:

Per N>2, affinché il problema sia risolvibile: N deve essere il prodotto di due numeri che siano primi tra loro

Dimostrazione

Sicuramente il numero restante è il più grande perché p(n+n modulo n) = n e quindi non esistono mosse possibili partendo da questo numero.
Siccome non è possibile muovere un numero due volte consecutive, le ultime due mosse sono state fatte da due numeri diversi tra loro e ciò significa che N ha almeno due divisori e quindi non è un numero primo; ma si può dedurre di più, se i due numeri sono potuti entrambi giungere a N significa che non si sono mangiati tra loro e da ciò deriva che sono primi tra loro.
Quindi N ha tra i suoi divisori anche due numeri che sono primi tra loro, e quindi è sicuramente possibile scriverlo anche come prodotto di due numeri che siano primi tra loro.
Questa è comunque soltanto una condizione necessaria (ma non sufficiente!!!)

Per quanto riguarda il problema 2 mi piacerebbe sia cercare una soluzione per via informatica (per valori di N>30), sia provare con carta e penna a trovare una soluzione per N=30, purtroppo però in questo periodo ho pochissimo tempo libero per la matematica e quindi non mi risulta possibile affrontare un problema così impegnativo; quando avrò più tempo libero (se non viene risolto nel frattempo) proverò a cercare una soluzione

Prima di concludere voglio solo aggiungere che considero questo problema particolarmente interessante e quindi spero di trovare presto il tempo e le idee per risolverlo.

Hasta luego,
Sancho Panza

[giobimbo]

Bravo Sancho, ci sei andato vicinissimo, giuste le tue considerazioni, ma se è n=2p, il prodotto di un primo pari per uno dispari, non c'è soluzione (perché?).
Forse ho messo troppo prematuramente il problema 1, visto che ho cominciato a lavorare alla cosa solo solo sabato pomeriggio e quindi ho non ancora in mano tutti i dati che servono, ma di una cosa sono certo, n deve avere almeno due fattori primi dispari oppure uno solo dispari se è un numero divisibile per 4.

[giobimbo]

Ultimo e definitivo aggiornamento. Escludendo i casi banali in cui vale 1 o 2, affinché n sia risolvibile è necessario che non sia un numero primo o una potenza di un primo; inoltre, se p è un numero primo dispari allora non deve essere n=2*p.
Per n da 1 a 34 ci sono soluzioni per n = 1, 2, 12, 15, 28, 30, 33. C'è una minuscola probabilità che anche 24 sia risolvibile, visto che questo numero ha una struttura complicata e potrebbe essermi sfuggita una soluzione.
Tenendo conto di questi risultati finali modifico leggermente i due precedenti problemi.

Problema 1. Perché per n = 2*p non ci sono soluzioni?
Problema 2. Trovare una soluzione per n=28, oppure per n=30 o per n=33.

[Sancho Panza]

Nel caso n = 2*p non ci possono essere soluzioni in quanto in tal caso n ha come divisori p e 2, quindi ci saranno due percorsi che porteranno a n: uno che passa attraverso tutti i numeri pari e l'altro costituito dalla mossa p-n
Siccome il doppio di ogni numero dispari è un numero pari, da ogni numero dispari con una mossa si giunge su un numero pari e non si può proseguire per non lasciare uno 0 che taglierebbe il percorso dei numeri pari rendendo impossibile la soluzione; inoltre i numeri pari minori di n sono tanti quanto i numeri dispari minori di n (e diversi da p), per cui se non ci sono due numeri dispari tali che il loro doppio (modulo n) coincida la soluzione risulterà impossibile perché verrebbero occupati tutti i numeri pari, rendendo in tal modo impossibile avere un punto di partenza del percorso.
Ciò è proprio quanto accade, infatti tutti i numeri dispari minori di p hanno il doppio che è uguale a (2 modulo 4) e sono tutti diversi tra loro (modulo n), mentre tutti i numeri dispari maggiori di p hanno il doppio che è uguale a (0 modulo 4) e sono tutti diversi tra loro (modulo n); quindi non ci sono due numeri dispari tali che il loro doppio (modulo n) coincida.

Non sono riuscito invece a dimostrare che per n = p*q*r non ci sono soluzioni, ma continuo a tentare.

[giobimbo]

Ottimo lavoro, bravo ancora!
Per quanto riguarda n=p*q*r... posso invocare la seminfermità mentale? Faccio molte visualizzazioni mentali e in questo modo ero giunto alla conclusione che non potessero esistere 3 percorsi che portassero a n, così per constatare de visu questa congettura ho fatto fare al computer la tabella dei 105*105 prodotti di n=3*5*7, poi ho controllato le colonne del 3, del 5 e del 7, appunto. Qui ho trovato che le colonne/percorsi s'incrociavano nel 15, nel 21 e nel 35, dal che ne ho dedotto (?) che anche con due soli percorsi, di cui uno iniziale con uno di questi tre numeri composti, fosse impossibile risolvere il gioco. Ma il bello è che, come ho visto poco fa, nella tabella sono evidenziate pure le colonne di 15, 21 e 35... Cose simili mi succedevano giocando a scacchi: vedevo che era pericoloso muovere certi pezzi, ma continuando l'analisi della situazione, facendo piani su piani, talvolta andava a finire che muovevo proprio un pezzo che non si doveva.

Per quanto riguarda il secondo problema suggerisco a chi vuol provare un attacco al numero 33, che contrariamente all'apparenza è il più facile dei tre.

[Sancho Panza]

Ho seguito il tuo suggerimento Giobimbo,
(cioè ho tentato un attacco al numero 33)
e ritengo di aver trovato una soluzione valida per N = 33

31-29
11-22
29-27
5-10
20-7
10-15
7-27
30-27
16-32
27-24
32-15
24-21
4-8
21-18
8-12
18-15
26-19
25-17
19-12
17-9
15-12
1-2
14-28
2-3
28-9
12-9
23-13
9-6
13-3
6-3
22-33
3-33

[Sancho Panza]

Ritengo di aver trovato una soluzione anche per il caso in cui: N=30

29-28, 17-4, 23-16, 11-22,
1-2, 7-14, 13-26, 19-8, 24-18, 25-20,
2-3, 14-21, 26-9, 8-27, 18-12, 20-15,
3-4, 21-28, 9-22, 27-16, 12-6, 15-10,
4-5, 28-5, 22-5, 16-5, 10-5,
6-30, 5-30

[giobimbo]

Chiedo scusa per il ritardo ma, una volta accertato che la soluzione di Sancho fosse corretta, ho voluto fare dei disegni che dessero l'idea del perché questo problema mi ha affascinato. Tra l'altro vedo solo ora un suo nuovo intervento, riguardante n=30.
Nella prima figura sotto è disegnato il tavoliere di un solitario, formato da caselle circolari e linee nere (le strade) che collegano le caselle. Sulle caselle blu si mette un gettone, se ne muove uno alla volta, un passo per volta, dove per passo s'intende il passaggio da una casella a quelle che subito segue lungo la strada. Ogni gettone si muove in linea retta, mai due volte consecutive lo stesso; se finisce in una casella già occupata, il gettone occupante viene tolto dal gioco. L'obiettivo del solitario consiste nel rimanere con un solo gettone sopra la casella rossa, dopo aver fatto 29 mosse.
Come si vede eseguendo sul tavoliere le mosse di Sancho Panza ogni soluzione del solitario è anche una soluzione del problema di Dario Uri. Ma il percorso rettilineo
30 - 27 - 24 - 21 - 18 - 15 - 12 - 9 - 6 - 3 - 33
può essere sostituito col percorso
3 - 6 - 9 - 12 - 15 - 18 - 21 - 24 - 27 - 30 - 33
al che si ottiene il duale del solitario di Sancho , illustrato dalla seconda figura sotto. Ancora, invece del percorso 11-22-33 potremmo usare 22-11-33 quindi, se il numero di soluzioni del solitario di Sancho è m, il corrispondente problema di Dario ha 4m possibili soluzioni.

A scanso di confusione, per non ammucchiare troppe figure assieme apro un altro intervento per parlare dei casi n=30 e n=28.

[giobimbo]

Un tavoliere corrispondente al problema per n=30 è quello della figura sotto. Ha un duale identico a parte che il percorso principale diventa
24 - 18 - 12 - 6 - 30
invece di
6 - 12 - 18 - 24 - 30
ma le strade laterali sono le stesse; ugualmente invece di 10-20-30 possiamo usare 20-10-30, quindi se il solitario in figura ha m soluzioni il problema ne ha 4m. Però il totale delle soluzioni per n=30 è di 8m, infatti si può costruire un tavoliere identico a quello in figura sostituendo in due caselle blu il numero 13 col numero 23 (e quindi la nuova sequenza 23-16-9-2-25-18 ), e sostituendo il 17 col 7 (e quindi ...).

Non metto il disegno per n=28, è simile a quello per n=33: un percorso principale 4-8-12-16-20-24-28, uno secondario 7-14-21-28, più sei strade laterali con tre caselle ciascuna invece di due. Stavolta non esiste il duale, si può solo invertire il percorso secondario: 21-14-28-7, quindi le soluzioni totali sono solo in numero di 2m.
In teoria dei grafi queste figure si chiamano alberi orientati, le caselle blu sono le foglie e quella rossa è la radice.

[Sancho Panza]

Ciao Giobimbo,
avrei un favore da chiederti.

Siccome non riesco a trovare la soluzione per N=28, gradirei molto vedere la tua soluzione.
Grazie.



Nota:
A me, sinceramente, pare che sia impossibile trovare una soluzione valida per N=28,
ma se tu l'hai risolto significa che una soluzione esiste, per cui spero di poter leggere la tua soluzione. Grazie.

[Pasquale]

Intanto facciamo vedere anche il 15 (i numeri a lato sono quelli che si spostano):

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 - 02
01 00 03 02 05 06 07 08 09 10 11 12 13 14 15 - 07
01 00 03 02 05 06 00 08 09 10 11 12 13 07 15 - 02
01 00 03 00 05 02 00 08 09 10 11 12 13 07 15 - 13
01 00 03 00 05 02 00 08 09 10 13 12 00 07 15 - 08
08 00 03 00 05 02 00 00 09 10 13 12 00 07 15 - 07
08 00 03 00 05 07 00 00 09 10 13 12 00 00 15 - 13
08 00 03 00 05 07 00 00 13 10 00 12 00 00 15 - 03
08 00 00 00 05 03 00 00 13 10 00 12 00 00 15 - 08
00 00 00 00 05 03 00 00 08 10 00 12 00 00 15 - 03
00 00 00 00 05 00 00 00 03 10 00 12 00 00 15 - 10
00 00 00 00 10 00 00 00 03 00 00 12 00 00 15 - 03
00 00 00 00 10 00 00 00 00 00 00 03 00 00 15 - 10
00 00 00 00 00 00 00 00 00 00 00 03 00 00 10 - 03
00 00 00 00 00 00 00 00 00 00 00 00 00 00 03

[Pasquale]

Please, siccome sto cercando anch'io la soluzione per il 28 richiesta da Sancho, eventualmente potrebbe essere inviata su posta privata, se siete daccordo.

[giobimbo]

Allora, la soluzione per n=28 ce l'ho ed è giusta, ma l'ho ottenuta usando un tavoliere sbagliato, quindi non vale niente. Me ne sono accorto ieri sera, riflettendo sulle condizioni sufficienti del problema. Mi dava noia quel tavolere asimmetrico che complicava tutta la faccenda, così investigando da vicino ho visto che c'era un errore, delle tre strade laterali che finivano nella casella 8:
23-18-13-8
9-18-27-8
15-2-17-8,
l'ultima era sbagliata, doveva essere 15-2-17-4, ripristinando la simmetria dei percorsi ma rendendo impossibile una soluzione del gioco, come subodorato da Sancho, a cui avevo intenzione di inviare un messaggio privato per evitargli di perdere altro tempo, nel caso ci studiasse ancora sopra. Son contento di vedere che anche Pasquale è interessato e a lui come a tutti dico: NON esiste soluzione. In effetti, nel mio primo intervento parlavo solo di n=30, poi approfondendo lo studio ho ripassato nuovamente tutti i numeri arrivando anche fino a n=33, usando grafi diversi, quelli delle figure sopra, e nel fare quello per n=28 sono incorso nell'errore descritto.

[Sancho Panza]

Ciao Giobimbo,
ti ringrazio per avermi confermato che per N=28 non esiste soluzione.

Hasta pronto,
Sancho Panza