Newsgroup: it.hobby.enigmi
Titolo: I cavalieri di Dudeney

Nel suo Amusements in Mathematics, Dover 1970, H.E.Dudeney a pag.80
propone il suo problema num.273 " The Round Table"
Sistemare le stesse n persone attorno ad un tavolo (n-1)(n-2)/2 volte,
in modo tale che ciascuna persona risulti alla fine, seduta tra  tutte
le possibili coppie ottenibili con le altre n-1 persone.
Per la storia di questo problema rimanda all'altro suo libro The
Canterbury Puzzles.
Ecco una sol. per il semplice caso n=4. Dato che con 3 persone si
possono formare 3*2/2=3 differenti coppie, 
gli incontri saranno appunto 3:
1 2 3 4
1 3 4 2
1 4 2 3
Le 3 stringhe rappresentano l'ordine di collocazione attorno il tavolo
delle 4 persone, e vanno considerate ciclicamente, come si vede ciscuno
ha ai suoi lati le possibili coppie formate dalle altre 3 persone.
Una sol. per n=5 con 6 incontri:
1 2 3 4 5
1 2 4 5 3
1 2 5 3 4
1 3 2 5 4
1 4 2 3 5
1 5 2 4 3
Poi l'autore riporta le sol. per n=6,7,8,9,10,11,12.
Afferma anche di aver trovato soluzioni fino a n=25, e dice che molti
matematici stavano ancora considerando il caso n=13.  A quanto ne so, la
sol. di questo caso 13 non e' mai stata pubblicata, sarei curioso di
conoscere vostre idee a tal proposito.
ciao :) dario

le possibili coppie ottenibili con le altre n-1 persone.
[omissis]
.
.
.
.
.
.
.
.
.
.
.
Una risposta a caldo da forzabrutista (poi ci penso ancora nel weekend):
1) la soluzione per n=13 e' alla portata del forzabrutista: l'insieme
cercato e' contenuto nell'insieme delle 13! permutazioni. Se impieghiamo
1 millisec ad eseguire una permutazione e la sua analisi se scartarla o
no, ce la caviamo con 72 giorni di tempo macchina.
2) La soluzione per n=25 no. Se usiamo un parallelo di 1.000.000 di PC
che facciano quell'operazione in un nanosec, impiegheremo mezzo
millennio e sapere che un millennio << infinito non mi aiuta.
A volte sapere che la soluzione esiste aiuta molto il solutore. Se fossi
sicuro che Dudeney non mente, cercherei una soluzione analitica od un
algoritmo empirico per trovare le soluzioni.
Ciao
Livio
-- 
Posted from 
mta04-acc.tin.it
 [212.216.176.35] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 conoscere vostre idee a tal proposito.
Ci vogliamo provare noi....?
CiaO,
Massimo
PS....a questo punto i programmatori possono rapidamente
      dirci se ho detto una cavolata !!!

 > Una sol. per n=5 con 6 incontri:
1 4 2 3 5
1 5 2 4 3
1 3 2 5 4
1 2 3 4 5
1 2 5 3 4
1 2 4 5 3
 
Ovvio che la 5° riga si puo leggere anche in questo modo:
1 4 3 5 2
CiaO,
Massimo

 
Mi sono complicato le cose....in quanto per valori bassi di n si ha
un beneficio con questo approccio rispetto alla totale "brute force"
rappresentata da n!.
Cmq l'approccio e' "reversibile" nel senso che ovviamente posso
usare il seguente schema:
12P3
12P4
12P.
12Pn
13P4
13P.
13Pn
...che sono le sedute (n-1)(n-2)/2 obbligatorie della prima persona 
e dove P rappresenta le possibili Permutazioni dei restanti.
Il numero dei cicli di verifica diminuisce sensibilmente, infatti
ne abbiamo solo: (n-1)(n-2)/2 * (n-3)!
che vale esattamente: n!/2n
CiaO,
Massimo

 
 
 


le possibili coppie ottenibili con le altre n-1 persone.
[omissis]
.
.
.
Non mi sono dimenticato del tuo problema, Dario.
Solo che mi appare molto piu' complicato del previsto,
secondo la solita legge di Morphy.
Se, alla luce delle mie ultime riflessioni, la seconda parte del mio
primo intervento continua sembrarmi valida, cioe' dubito dell'esistenza
di soluzioni per N=25, la prima parte invece vacilla, cioe' comincio ad
avere dubbi di saper trovare una soluzione N=13, almeno in questa vita.
Credevo di poter passare in rassegna le N! permutazioni, potendo trovare
un criterio sequenziale se accettare o no quella in esame.
Non ho trovato nulla di tutto cio', i tentativi sono stati pietosi.
Allora ho abbassato le pretese e mi sono messo a cercare un crivello per
N=6. (Buuuuu!)
Poiche' tutto si risolve in (N-1)*(N-2)/2 tavolate, tutti stanno tra una
specifica coppia una volta sola e quindi questo numero e' il minimo per
soddisfare ogni singolo cavaliere. Esiste quindi una soluzione del
genere:
A B C D E F
A B D . . .      (CEF)
A B E . . .      (CDF)
A B F . . .      (CDE)
C B D . . .      (AEF)
C B E . . .      (ADF)
C B F . . .      (ADE)
D B E . . .      (BDE)
D B F . . .      (BDF)
E B F . . .      (BEF)
Dove la prima riga e' arbitraria e nelle altre B fa da pivot per tutte
le pssibili coppie.
Ora non resta che mettere dentro le 27 lettere, dove ogni gruppo ha 6
possibili permutazioni. Le combinazioni sono quindi 6^9= 10.077.696.
Tagliando qualche ramo secco (CEF ad esempio si puo' subito scartare
perche' genera le sequenze EFA e FAB gia' presenti nella prima) si
arriva a 648.000 combinazioni. Un programmino trova la soluzione in 184
secondi su un modesto Pentium 120:
A B C D E F
A B D C F E
A B E F D C
A B F C E D
C B D E A F
C B E D F A
C B F D A E
D B E A C F
D B F E C A
E B F A D C
Con un metodo del genere, che per ora e' l'unico che conosco
funzionante, per N=13 i tempi diventano biblici.
Se qualcuno ha verifiche migliori, me lo faccia sapere.  
Se no, bisogna cercare altri rami secchi.
Attenzione alle false soluzioni: occorre verificare che ogni cavaliere
stia fra tutte le coppie possibili.
Ciao a tutti
Livio
-- 
Posted from 
mta01-acc.tin.it
 [212.216.176.32] 



Purtroppo non ho molto tempo libero per seguire il newsgroup, ma con
le feste di Natale mi sono dato da fare.
Mi piace programmare e ho provato a calcolare alcune di queste
soluzioni sfuttando il suggerimento di Livio Zucca e cercando di
ottimizzare al massimo il programma tagliando tutti i rami secchi
possibili.
Le soluzioni per n=4,5,6,7 sono facili (meno di un secondo di tempo),
un po' piu' difficile per n=8 (24 secondi), qualche problema per n= 9
(31 minuti). Le difficolta' cominciano per n=10 che ho sospeso dopo
alcuni giorni di calcolo senza risultato.  
Ma veramente Dudeney ha trovato le soluzioni fino a n=12? Mi sembra un
compito immane; quale metodo ha utilizzato? La forza bruta senza
qualche altro appiglio ha poche possibilita'
Ho fatto una piccola ricerca su Internet (basta cercare Dudeney round
table) e sembra che ci siano novità sull'argomento come infatti potete
leggere:
-----------------------------------------------------------------
25th Australasian Conference on Combinatorial Mathematics and
Combinatorial Computing 
December 4 - 8, 2000 
University of Canterbury Christchurch, New Zealand 	
Conference Organizers Charles Semple and Mike Steel 
Dudeney's Round Table Problem
presented by Midori Kobayashi
University of Shizuoka, Japan 
joint research with Kiyasu-Zen'iti (Semiconductor Research Institute)
and Gisaku Nakamura (Tokai University) 
A Dudeney set in Kn is a set of Hamilton cycles with the property that
every path of length two lies on exactly one of the cycles. We call
the problem of construction a Dudeney set ``Dudeney's round table
problem''. It has been solved when n is even, but the problem when n
is odd is still open. In this talk we show some new series of Dudeney
sets and some results about double Dudeney sets. 
-----------------------------------------------------------------
Sembrerebbe che il problema sia stato risolto per n pari; qualcuno ha
maggiori informazioni?
Comunque invio le soluzioni da me trovate.
n = 7
  7  1  2  3  4  5  6
  6  1  2  4  3  5  7
  5  1  2  6  4  3  7
  4  1  2  7  3  5  6
  3  1  2  5  4  6  7
  7  1  3  6  4  2  5
  6  1  3  2  4  7  5
  5  1  3  4  7  2  6
  4  1  3  5  2  6  7
  7  1  4  3  6  5  2
  6  1  4  5  7  2  3
  5  1  4  2  7  6  3
  7  1  5  4  2  6  3
  6  1  5  2  3  7  4
  7  1  6  2  3  5  4
n = 8
  8  1  2  3  4  5  6  7
  7  1  2  4  3  5  6  8
  6  1  2  5  3  7  4  8
  5  1  2  6  3  4  7  8
  4  1  2  7  3  6  5  8
  3  1  2  8  4  6  5  7
  8  1  3  2  4  5  7  6
  7  1  3  4  6  2  8  5
  6  1  3  8  2  5  4  7
  5  1  3  6  4  2  8  7
  4  1  3  5  7  2  8  6
  8  1  4  2  7  6  3  5
  7  1  4  5  8  6  3  2
  6  1  4  3  8  7  2  5
  5  1  4  7  2  6  8  3
  8  1  5  2  6  7  3  4
  7  1  5  6  2  4  8  3
  6  1  5  4  8  7  3  2
  8  1  6  4  7  5  2  3
  7  1  6  3  8  5  2  4
  8  1  7  6  4  5  3  2
n = 9
  9  1  2  3  4  5  6  7  8
  8  1  2  4  3  5  6  9  7
  7  1  2  5  3  6  4  8  9
  6  1  2  7  3  4  8  5  9
  5  1  2  6  3  7  4  9  8
  4  1  2  8  3  5  7  6  9
  3  1  2  9  4  5  7  8  6
  9  1  3  2  4  5  8  6  7
  8  1  3  4  6  2  7  5  9
  7  1  3  5  4  6  8  9  2
  6  1  3  9  8  2  4  7  5
  5  1  3  8  6  2  4  9  7
  4  1  3  7  5  8  2  9  6
  9  1  4  2  7  8  5  6  3
  8  1  4  3  9  7  2  5  6
  7  1  4  5  2  6  9  8  3
  6  1  4  7  9  5  3  2  8
  5  1  4  8  2  6  7  3  9
  9  1  5  6  2  3  7  8  4
  8  1  5  3  9  4  6  7  2
  7  1  5  2  3  9  6  8  4
  6  1  5  4  7  8  3  9  2
  9  1  6  7  4  3  8  5  2
  8  1  6  4  2  9  7  3  5
  7  1  6  3  4  9  5  2  8
  9  1  7  5  2  4  8  3  6
  8  1  7  6  3  2  9  5  4
  9  1  8  3  2  7  4  6  5
Buon 2001, Buon XXI secolo e Buon III Millennio!
-- 
Ciao, Damiano Scapeccia