Newsgroup: it.hobby.enigmi
Titolo: [MA] Minicampionato

Otto squadre di calcio (0,1,2...,6,7) sono le protagoniste 
di un minicampionato. Si desidera che ogni squadra disputi 
un incontro con ciascuna altra esattamente una volta, cosi' 
ci saranno  7*8/2 = 28 partite in tutto. Sappiamo cosi' che 
il torneo durera' sette giornate.
  Ci sono a disposizione 7 campi di gioco (a,b,...f,g) e per 
non favorire nessuno col fattore campo, si chiede che ogni 
squadra giochi in ciascun campo esattamente una volta.
Il povero Mario, che deve redigere il calendario degli 
incontri, sono 3 notti che non dorme.
Possiamo aiutarlo ??
:) dario

Basta redigere una tabella 4 X 7.
Si procede molto velocemente scrivendo nella prima riga in tutte le colonne
la squadra 0 (visto che ogni squadra dovrà disputare 7 partite) in modo da
riempire tutta la prima riga.
In ogni casella della prima riga, accanto alla squadra 0 si scriverà
l'avversario di ognuna delle sette giornate, e cioè :
01    02    03    04    05    06    07
Poi nella seconda riga si andrà a scrivere la squadra 1 facendo attenzione a
non scriverla nella stessa colonna dove già figura (in tal caso la prima
colonna dove ha già giocato con la squadra 0), e si scriverà l'avversario
procedendo come sopra ma facendo attenzione a non far tapparire nella stessa
colonna(che indica i diversi campi di calcio) lo stessa squadra,avrò :
--    17    12    13    14    15    16
procedendo di questo passo (ma senza superare le righe 4,in quanto ogni riga
rappresenta una partita, ed in ognuna delle 7 giornate si disputeranno 4
partite) fino ad arrivare alla squadra 3 e poi tornare nella tabella con le
squadre 4,5,6,7 e riempire le caselle rimaste vuote !
Otterremo (MOLTO FACILMENTE E RAPIDAMENTE) :
01    02    03    04    05    06    07
45    17    12    13    14    15    16
23    46    56    26    27    24    25
67    35    47    57    36    37    34
(sicuramente c'è un modo molto più rapido ....ma vado di fretta e quindi per
il momento va bene questo (PER ME!) )
;)
***********************************************************************
ciao  a tuttE/i    ;)
RISPETTO PER TUTTI E TUTTO!
1) TUTTO E' RELATIVO ;
2) HO FIDUCIA IN DIO ;
3) A TUTTO C'E' UNA SPIEGAZIONE RAZIONALE ;
4) TUTTO E' POSSIBILE ;
5) SONO COME S. TOMMASO : NON CI CREDO SE NON CI METTO IL NASO .
Marco ;)
***********************************************************************

 Possiamo aiutarlo ??
.
.
...una prima soluzione che mi viene in mente e' troppo
facile per essere 'validata' per cui mi rimetto alla vostra
clemenza.  ;-)
La posto dopo un breve spoiler per evidenti motivi.
.
.
s
p
o
i
l
e
r
.
.
Per creare il tabellone dei 28 incontri mi viene in aiuto
un vecchio metodo che permette di ottenere quanto cercato
in modo grafico.
18
27
36
45
Partendo dallo schema suindicato, in cui sono indicati i primi
4 incontri, si tiene fissa la posizione della squadra 1 e si
ruotano in senso antioriario le altre 7, in moda da avere gli
accoppiamenti per le future giornate. Segue, infatti:
 17   16   15   14   13   12
 86   75   64   53   42   38
 25   84   73   62   58   47
 34   23   82   78   67   56
A questo punto il problema diventa 'difficile per me' per cui mi
affido al mio intuito che mi dice che il modo + facile per fare
in modo che ogni squadra giochi esattamente una volta su ogni
campo e' quella di giocare in 'orari differenti' tutte e 4 gli
incontri della giornata sullo stesso campo.
Per cui avremo:
       18   17   16   15   14   13   12 
       27   86   75   64   53   42   38
       36   25   84   73   62   58   47
       45   34   23   82   78   67   56
Campo: a    b    c    d    e    f    g
Spero sia chiaro cosa intendo dire...
;-)
CiaO,
Massimo
-- 
Posted from 
net128-053.mclink.it
 [195.110.128.53] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Oppure si può procedere in altro modo :
abbiamo 8 squadre;
ogni giornata avrò 4 partite;
le prime 4 squadre dovranno scontrarsi ognuna con ognuna delle ultime 4
squadre, da cui :
0    1    2    3            0    1    2    3        0    1    2    3
0    1    2    3
4    5    6    7            7    4    5    6        6    7    4    5
5    6    7    4
Da quì ho occupato solo le prime 4 giornate
Mi restano da individuare le ultime tre giornate, come procedo ?
Innanzi tutto vedo che le squadre che ancora devono scontrarsi sono quelle
appartenenti alla stessa "RIGA" (che in tal caso ha significato opposto al
mio predente intervento).
Allora avrò :
01            02            03
ma poi anche 12,13,23 dovranno scontrarsi, quindi :
01            02            03
23            13            12
ed i 45,46,47,56,57,67?
Facile :
01        02        03
23        13        12
45        46        47
67        57        56
Che ne dite ?
Troppo lungo ?
Ditemi LA SOLUZIONE ! ;)
Grazie ;-)


 4  5  6  7 - 7  4  5  6 - 6  7  4  5 - 5  6  7  4


"Dario Uri" ha scritto

Ho trovato un metodo che sembra funzionare, ... anche se non ho capito bene
il perché.
:-)
spoiler
.
.
.
.
.
.
Numero le squadre e i campi da 0 a 7 in binario:
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
Nota: in questo modo ci sono 8 campi, ma considero il campo 000 come
virtuale (in realtà non esiste)
considero un incontro tra due squadre (per esempio 2 e 6) e scrivo i
corrispondenti valori in binario
010
110
confronto i bit corrispondenti delle due squadre, e scrivo 0 per bit uguali
ed 1 per bit differenti
100
e ottengo il numero 100 del campo in cui le due squadre si incontrano:
quindi le squadre 2 e 6 si incontrano nel campo n. 4.
nota: se una squadra gioca contro se stessa va a finire nel capo virtuale
000
:-)

Dario Uri chiede

.
.
.
.
.
.
.
.
.
.
Mi pare di capire che le 4 partite di ogni giornata vadano giocate su
campi distinti. Conoscevo il metodo grafico descritto da Marco per la
generazione del calendario (squadra 0 perno e le altre a girare), poi
per l'assegnazione dei campi gli ho dato gių di brute force.
       \campo
giornata\__a__b__c__d__e__f__g_
      1 | 01 27 36 45 -- -- --
      2 | -- 56 -- 02 31 47 --
      3 | -- 03 42 -- 67 -- 51
      4 | 62 -- 71 -- 04 53 --
      5 | -- -- 05 73 -- 12 64
      6 | 75 14 -- -- -- 06 23
      7 | 34 -- -- 16 25 -- 07
in ogni riga e colonna compaiono tutte le otto squadre una sola volta.
Ciao, Silv:o)

Paolo Licheri wrote:
  Ho trovato un metodo che sembra funzionare, ... anche se non ho capito
bene
  il perché.
  Numero le squadre e i campi da 0 a 7 in binario:
  0 000
  1 001
  2 010
  3 011
  4 100
  5 101
  6 110
  7 111
L'idea mi sembra valida, ma qualcosa mi sfugge, se ad es. utilizzo lo schema
dato da Massimo per gli incontri nelle sette giornate ottengo:
1°) 07,16,25,34
2°) 06,75,14,23
3°) 05,64,73,12
4°) 04,53,62,71
5°) 03,42,51,67
6°) 02,31,47,56
7°) 01,27,36,45
Ora se tento di abbinare questi incontri ai vari campi da gioco col metodo
che hai descritto, mi ritrovo che nella prima giornata le quattro partite
andrebbero tutte giocate nel campo num. 7.
 Le partite vengono giocate alla stessa ora, percio' ad ogni giornata devono
essere utilizzati 4 campi diversi.
 ciao dario

Ipereclettico wrote:
  Basta redigere una tabella 4 X 7.
  Otterremo (MOLTO FACILMENTE E RAPIDAMENTE) :
  01    02    03    04    05    06    07
  45    17    12    13    14    15    16
  23    46    56    26    27    24    25
  67    35    47    57    36    37    34
In questo modo mi dai gli incontri per ogni giornata, e fin qui come abbiamo
visto e' piuttosto facile, ma se come dici le colonne rappresentano anche i
campi, mi fai giocare i 4 incontri di una giornata tutti sullo stesso campo.
In realta' come gia' detto, per ciascuna giornata vanno scelti 4 campi
diversi perche' le partite si svolgono tutte nella stessa ora.
ciao :)dario

Silvio Sergio wrote:
  Mi pare di capire che le 4 partite di ogni giornata vadano giocate su
  campi distinti. Conoscevo il metodo grafico descritto da Marco per la
  generazione del calendario (squadra 0 perno e le altre a girare), poi
  per l'assegnazione dei campi gli ho dato giů di brute force.
         \campo
  giornata\__a__b__c__d__e__f__g_
        1 | 01 27 36 45 -- -- --
        2 | -- 56 -- 02 31 47 --
        3 | -- 03 42 -- 67 -- 51
        4 | 62 -- 71 -- 04 53 --
        5 | -- -- 05 73 -- 12 64
        6 | 75 14 -- -- -- 06 23
        7 | 34 -- -- 16 25 -- 07
  in ogni riga e colonna compaiono tutte le otto squadre una sola volta.
Esatto. Gli esperti di Block Design, chiamano queste configurazioni Room
Squares. Ci sono 6 distinte soluzioni per il nostro caso n=7.
Un metodo per la loro costruzione utilizza l' Hillclimbing algorithm, ma non
ne so di piu'.
ciao :) dario

 ne so di piu'.
Ma dai! solo 6 soluzioni!?
Vabbè che ci sono migliaia di soluzioni equivalenti per permutazione delle
righe e delle colonne, (tipo 7!^2), per trasposizione giornate/campi e così
via, ma credevo che ce ne fossero ben di più! Anche perché il mio
programmino col solito backtrack si è messo immediatamente a sputarne a
raffica, ed aveva un "calendario" preimpostato, quello ottenuto col metodo
grafico. Evidentemente tutti i calendari possibili sono riconducibili a
pochissimi schemi fondamentali (1, 2, 3 o 6, visto il numero di soluzioni).
Silv:o)