Newsgroup: it.hobby.enigmi
Titolo: L'ascensore

In un palazzo di 66 piani c'e' uno strano ascensore; e' dotato di soli 2 
pulsanti SU e GIU'.
Premendo SU, l'ascensore si alza di 8 piani. (resta immobile se non ci sono 
8 piani disponibili)
Premendo GIU', l'ascensore si abbassa di 11 piani. (resta immobile se non 
ci sono 11 piani disponibili)
Con un siffatto ascensore e' possibile andare da un qualunque piano ad 
un'altro?

 ha scritto nel messaggio
news:3E207E4...@uriland.it...

e tu questo me lo chiami enigma? certo che è possibile!


Sembrerebbe di si'.
Piazziamo all'estremo in alto a sinistra di una tabella il numero 1.
Cominciamo a disporre nelle celle a destra la progressione dei piani
raggiungibili col pulsante SU.
1  9  17  25  33  41  49  57  65
Fermandoci ovviamente a 65.
Poi cominciamo a disporre verticalmente i piani raggiungibili con il
pulsante GIU'.
1  9  17  25  33  41  49  57  65
       6  14  22  30  38  46  54
           3  11  19  27  35  43
                   8  16  24  32
                       5  13  21
                           2  10
Fatto questo continuiamo la successione del SU per le righe
successive.  
1  9  17  25  33  41  49  57  65
       6  14  22  30  38  46  54  62   
           3  11  19  27  35  43  51  59
                   8  16  24  32  40  48  56  64
                       5  13  21  29  37  45  53  61   
                           2  10  18  26  34  42  50  58  66
Infine completiamo il tutto andando ancora GIU e SU ove e' possibile.
1  9  17  25  33  41  49  57  65
       6  14  22  30  38  46  54  62   
           3  11  19  27  35  43  51  59
                   8  16  24  32  40  48  56  64
                       5  13  21  29  37  45  53  61   
                           2  10  18  26  34  42  50  58  66
                                   7  15  23  31  39  47  55  63
                                       4  12  20  28  36  44  52  60
                                          (1   9  ......) 
Se ne ricava una tabella a forma di losanga, nella quale sono compresi
una e una sola volta tutti i numeri da 1 a 66.
Per scoprire il percorso tra un piano e l'altro, si vada dal piano di
partenza _sempre_ a destra o in basso fino a raggiungere il piano
scelto.
L'accessibilità di tutti i piani e' garantita dalla ciclicita' della
tabella, che si ripete uguale all'infinito piazzando l'1 sotto il 12
inferiore. Quindi da ogni piano si può raggiungere qualsiasi piano.
Per tornare a un piano dopo essersi spostati dal piano stesso servono
necessariamente 11+8=19 pressioni del pulsante, o un numero multiplo
di 19.
Il fatto che tutti i piani compaiano una volta sola nel grafico fa si'
che non esistano percorsi 'migliori' o 'peggiori' per andare da un
piano all'altro. Per andare dal piano x al piano y occorre sempre un
numero prefissato di spostamenti, o un numero pari all'incremento di
19 (o un suo multiplo) del percorso ottimale. 
Dal grafico si evince che i percorsi piu' 'problematici' sono quelli
che portano dall'ultimo piano di una riga della tabella (es. 65) al
primo di quella immediatamente successiva (es. 6). Essi richiedono non
meno di 24 pressioni del pulsante.
ciao
Stark

primo di quella immediatamente successiva (es. 6).
Ovviamente e' il contrario.
ciao
Stark

 wrote in message
r5512vk9fq4pa8tsd...@4ax.com...

ma questa non è brute force? e se i piani fossero 101? e se fossero n? per
quali n è non possibile raggiungere tutti i piani?
con la brute force l'avevo trovato anche io:-)

 poteva accedere a tutti i piani? Non credo a tutti
E' proprio quello che chiedevo, ma come hai potuto vedere , la soluzione 
esiste.
tante belle fusa.
dario

 con la brute force l'avevo trovato anche io:-)
Certo che in questo genere di problema e' auspicabile trovare una soluzione 
generale.
Allora ecco un'altra domanda (derivata dalla tua quarta) : Sempre con lo 
stesso ascensore, qual e' il palazzo piu' basso dove sia possibile andare 
da un qualunque piano ad un qualsiasi altro?
(Trovato questo, non e' difficile dimostrare che per palazzi piu' alti e' 
sempre possibile accedere a tutti i piani).

da un qualunque piano ad un qualsiasi altro?
Ha 19 piani. Soluzione immediata guardando la tabella, 19 è il più
alto dei numeri-ponte (quelli che consentono il passaggio da una riga
all'altra.
ciao
Stark