Torneo particolare

[fma...@gmail.com]

Salve NG,
questa è una domanda nata su it.comp.www.php, mi permetto di girarla io anche qui visto che la soluzione informatica (leggi brute-force) è abbastanza facile e veloce, e sono abbastanza sicuro che né l'OP né altri avranno voglia di generalizzare ;-)
C'è un torneo con N concorrenti, dove ognuno si scontra con tutti gli altri una sola volta (quindi N(N-1)/2 incontri). Occorre trovare per un determinato N l'elenco degli incontri tale che ogni concorrente non faccia due incontri consecutivi.
Questo è a volte possibile (banale, N=2) a volte no (banale, N=3 o N=4), ma come fare a capirlo senza provare tutte le possibili permutazioni?
Ciao!

[Nino]

<fma...@gmail.com> ha scritto nel messaggio
news:edad38b1-b13b-4323...@googlegroups.com...

C'è un torneo con N concorrenti, dove ognuno si scontra con tutti gli altri
una sola volta (quindi N(N-1)/2 incontri). Occorre trovare per un
determinato N l'elenco degli incontri tale che ogni concorrente non faccia
due incontri consecutivi.
Questo è a volte possibile (banale, N=2) a volte no (banale, N=3 o N=4), ma
come fare a capirlo senza provare tutte le possibili permutazioni?
Ciao!

----------------

Per N>4 penso sia sempre possibile.

Metodo:

- N dispari: occorre far incontrare N volte, (N-1) concorrenti a gruppi
successivi di (N-1)/2 partite.
Esempio N=5
2-4 ; 3-5 ; (non gioca 1)
1-2 ; 3-4 ; (non gioca 5)
1-5 ; 2-3 ; (non gioca 4)
1-4 ; 2-5 ; (non gioca 3)
1-3 ; 4-5 ; (non gioca 2)
N=7
1-2 ; 3-4 ; 5-6 ;
1-3 ; 4-7 ; 2-5 ;
1-4 ; 2-3 ; 6-7 ;
1-5 ; 2-6 ; 3-7 ;
1-6 ; 2-7 ; 4-5 ;
1-7 ; 4-6 ; 3-5 ;
2-4 ; 3-6 ; 5-7;

-N pari: occorre far incontrare N-1 volte gli N concorrenti a gruppi di N/2
partite.
Esempio N=6
1-2 ; 3-4 ; 5-6 ;
1-3 ; 4-6 ; 2-5 ;
1-4 ; 3-5 ; 2-6;
1-5 ; 3-6 ; 2-4 ;
1-6 ; 2-3 ; 4-5 ;

[fma...@gmail.com]

OK, io l'avevo vista come se non si potessero fare più incontri in contemporanea (diciamo che c'è solo un "campo da gioco" disponibile).
Leggendo i tuoi risultati in sequenza vengono ancora rispettate le condizioni, ma invertendo ad esempio qualche riga non funzionerebbe più! C'è un metodo per questo?
Ciao!

[frengo]

Non e' un torneo particolare, e' il classico Round Robin (girone
all'italiana da noi)
C'e' un semplice metodo che funziona tranquillamente (lascio a te la
dimostrazione).
Te lo faccio vedere per n=6
Disponi i giuocatori su due file:
D E F
A B C
e quelli sulla stessa colonna sono un accoppiamento.
Dopo di che diciamo A oscilla da una riga all'altra, gli altri "ruotano".
A D E
B C F
Nota che quando A ritorna "indietro", lo devono scavalcare in 2.
C B D
A F E

A C B
F E D

E F C
A D B

Ovviamente se N e' dispari, ad ogni turno un giuocatore deve riposare.
Quindi e' come se ci fossero N+1 giocatori, di cui uno in realta' e' il
"bye".

frengo

[frengo]

Leggendo meglio il tuo post mi rendo conto che non avevo compreso
appieno il tuo problema (non e' il classico round robin ma ha una
condizione in piu), ma e' facile vedere che il metodo proposto soddisfa
anche la tua richiesta :)

frengo