Newsgroup: it.hobby.enigmi
Titolo: Semafori

  Ci sono n semafori, n>0, che possono essere rossi, verdi o arancioni;
 presi i semafori distinti p e q qualunque, se sono dello stesso colore,
 allora il semaforo p+q è di colore diverso; si suppone che ogni
semaforo
 non cambi mai colore.
 Quanto vale n al massimo?
Ciao
Andrea
--
Posted from 
mta09-acc.tin.it
 [212.216.176.40]
via Mailgate.ORG Server - 
http://www.mailgate.org

  Quanto vale n al massimo?
23.
Colore A = 1,2,4,8,11,22.
Colore B = 3,5,6,7,19,21,23.
Colore C = 9,10,12,13,14,15,16,17,18,20.
Ci sono 2 varianti, i numeri 16 o 17, ma non entrambi possono essere
spostati da C ad A.
Con 4 colori si puo' arrivare a 66.
ciao :) dario

Ai 4 angoli di una stanza quadrata vi sono 4 ragazzi che indossano un
 impermeabile double-face, bianco da una parte e nero dall'altra. 
  Esiste una formula generale?
Non credo. Gia' per n=5 non esiste una procedura sicura, neppure per una
versione piu' semplice che ti descrivo, presentata da Gardner nel
febbraio 1979 in Scientific American, forse di origine russa:
< Immagina un tavolo quadrato ruotante sul suo centro. Ad ogni angolo vi
e' una scatola contenente un bicchiere ritto o capovolto. Non e'
possibile vedere i bicchieri, ma e' possibile infilare una mano in
ciascuna scatola per verificare l'orientamento del bicchiere in essa
contenuto ed eventualmente cambiarlo.
Un movimento e' cosi' definito: Si fa ruotare il tavolo, e quando si
ferma puoi infilare le mani in 2 differenti scatole ed eventualmente
aggiustarne l'orientamento a piacere. Quando il tavolo si ferma non c'e'
modo di distinguerne i suoi angoli, cosi' ci sono solo 2 possibilita',
infilare le mani in 2 scatole adiacenti o in due scatole diagonali. Lo
scopo e' orientare i 4 bicchieri nello stesso senso, a quel punto suona
un campanello che avvisa il conseguimento del risultato>
Gardner chiedeva di trovare una procedura che risolvesse per 4 bicchieri
in 5 mosse.
Nel marzo 1979 presento' 2 generalizzazioni di Ronald Graham e Persi
Diaconis.
Graham propose un tavolo a forma di n-agono ed il solutore con k-mani.
Diaconis propose di sostituire i bicchieri con oggetti con piu' di 2
orientamenti. Piu' tardi Scott Kim considero' un tavolo con maggiori
simmetrie, cubo o simili.
In un capitolo di "The Mathematical Gardner" 1981, W.Laaser e L.Ramshaw
hanno ottenuto il seguente risultato nella variante proposta da Graham,
una procedura esiste IFF i parametri k ed n soddisfano:
k>= (1-1/p)n dove p e' il maggior fattore primo di n. 
ciao :)dario

Come sempre molto interessante l'excursus Dario.
Ho spedito le tue note all'amico che mi ha proposto l'idea,
e sono convinto ne rimarra' impressionato. Ovviamente ti
ho attribuito la paternita'.
Vedo anche da dove e' stato tratto lo spunto per questo problema.
Devo dire che per quanto riguarda la generalizzazione,
abbiamo stabilito che le girate devono poter essere almeno N/2.
Devo anche dire che per N dispari non si ha soluzione,
infatti non esiste una combinazione dalla quale con una mossa
vinco sicuramente. Invece per N pari la combinazione alternata
xyxyxy porta alla vittoria girando n/2 impermeabili alternati.
Direi che alternando girature consecutive a girature alternate si
dovrebbe
arrivare ad una soluzione, ma devo pensarci su per dimostrarlo.
