Ascensori

[axpgn]

In un palazzo ci sono sette ascensori, ognuno di questi ha al massimo sei fermate (sei piani, sei pulsanti).

Se è possibile andare da un piano qualsiasi ad un altro piano qualsiasi senza cambiare ascensore, qual è il massimo numero di piani che può avere il palazzo?



Cordialmente, Alex

[Quinzio]

Spero che mi vada bene...

15 ?

[axpgn]

No.

[Quinzio]

"axpgn":No.

Pero'....

sono meno di 15 ? Giusto ?
Come ultimo tentativo senza troppa convinzione dico 12.

[axpgn]

Giusto ma non sono quelli.

[Drazen77]

Credo $14$
Ma... boh?! penso di aver fatto una gran confusione, quini non sono sicuro

[gabriella127]

Con una soluzione semplice e elegante me ne vengono $11$,
(compreso il primo livello, il pianterreno).

[axpgn]

@Drazen77
Il numero è quello ma senza né una dimostrazione né una soluzione funzionante è un po' tirare a caso

[Umby2]

"Drazen77":

Credo $14$
Ma... boh?! penso di aver fatto una gran confusione, quini non sono sicuro

Interessante.
Concordo, e provo a dare una spiegazione.

[Umby2]

Per rendere più semplice la soluzione, semplifichiamo,
assegnando ad ogni coppia di piani una lettera.

A = Piano 1 e 2
B = Piano 3 e 4
C = Piano 5 e 6
D = Piano 7 e 8
E = Piano 9 e 10
F = Piano 11 e 12
G = Piano 13 e 14

..... continua .....

[Quinzio]

"axpgn":@Drazen77
Il numero è quello ma senza né una dimostrazione né una soluzione funzionante è un po' tirare a caso

Una soluzione con 11 piani e' questa:

Ascensore - > piani
A -> 1  2  3  4  5  6
B -> 1  7  8  9  10 11
C -> 2  7  8  9  10 11
D -> 3  7  8  9  10 11
E -> 4  7  8  9  10 11
F -> 5  7  8  9  10 11
G -> 6  7  8  9  10 11

Un limite massimo al numero di piani e' dato dalla formula:
$(P(P-1))/2 = N_A(P_A(P_A-1))/2$
dove
$P$: numero di piani
$N_A = 7$: numero di ascensori
$P_A = 6$: piani per ascensore
ovvero si calcola quanti piani si potrebbero collegare ipotizzando che non ci siano ridondanze di coppie di piani tra gli ascensori.
Viene $P = 15$, quindi un limite massimo alla soluzione e' 15.
Ad es. nella soluzione data prima con 11 piani, i piani 7 e 8 sono serviti da piu' ascensori, questa e' una ridondanza.
Quindi, una soluzione esiste per 11 piani, un limite massimo e' 15, quindi la soluzione e' sicuramente compresa tra 11 e 15.

[Umby2]

"Quinzio":
Quindi, una soluzione esiste per 11 piani, un limite massimo e' 15, quindi la soluzione e' sicuramente compresa tra 11 e 15.

Il ragionamento mi piace, la soluzione un po meno,
nel senso che la disposizione dei tasti non è molto efficiente !!!
Ad esempio: chi abita al piano 10 e deve scendere al piano 9,
può prendere indifferentemente l'ascensore B, C, D, E, F, G
che fanno praticamente la stessa cosa, e quindi ci sono molte "ripetizioni"

[Umby2]

"Umby":

Per rendere più semplice la soluzione, semplifichiamo,
assegnando ad ogni coppia di piani una lettera.

A = Piano 1 e 2
B = Piano 3 e 4
C = Piano 5 e 6
D = Piano 7 e 8
E = Piano 9 e 10
F = Piano 11 e 12
G = Piano 13 e 14

..... continua .....

A questo punto, assegno ad ogni ascensore 3 lettere
(è praticamente la stessa cosa, di dire 6 piani !!!)

Esempio: Ascensore 1: A B C

E' evidente, che la lettera A accompagna, altre 2 lettere (B e C),
e siccome le lettere ne sono 6 (7-1), ho bisogno che almeno 3 ascensori, abbiano la lettera A,
e che i suoi "gemelli" siano le altre 6 lettere

... continua ...

[hydro1]

Un bound ovvio è 14: se ci sono almeno 11 piani, ogni tasto dev'essere su almeno 3 ascensori perchè fissato quello si possono raggiungere altri 5 piani, quindi se il tasto del piano $X$ fosse solo su due ascensori dal piano $X$ se ne potrebbero raggiungere al massimo $10$. Siccome i tasti totali sono $42$, i piani possono essere al più $42/3=14$. Questa è una soluzione che funziona con 13:

A: 1,2,5,8,11,12
B: 1,3,6,9,11,12
C: 1,4,7,10,11,13
D: 2,3,7,10,12,13
E: 2,4,6,9,12,13
F: 3,4,5,8,11,13
G: 5,6,7,8,9,10

[axpgn]

@hydro
Corretto, adesso manca trovare la soluzione massimale

Se anche ad un solo piano ci sono solo due ascensori, non è possibile superare gli $11$ piani (con $7$ ascensori).
D'altro canto con tre ascensori per piano avremo $7$ ascensori per $6$ fermate per un totale di $42$ tasti disponibili; avendone tre per piano, al massimo potremo avere $14$ piani.
Una soluzione con $14$ piani esiste

[Umby2]

"Umby":

Per rendere più semplice la soluzione, semplifichiamo,
assegnando ad ogni coppia di piani una lettera.

A = Piano 1 e 2
B = Piano 3 e 4
C = Piano 5 e 6
D = Piano 7 e 8
E = Piano 9 e 10
F = Piano 11 e 12
G = Piano 13 e 14

..... continua .....

A questo punto, assegno ad ogni ascensore 3 lettere
(è praticamente la stessa cosa, di dire 6 piani !!!)

Esempio: Ascensore 1: A B C

E' evidente, che la lettera A accompagna, altre 2 lettere (B e C),
e siccome le lettere ne sono 6 (7-1), ho bisogno che almeno 3 ascensori, abbiano la lettera A,
e che i suoi "gemelli" siano le altre 6 lettere

... continua ...

Vediamo se quadra:
Ogni lettera deve apparire 3 volte, essendo 7 lettere abbiamo 21 "presenze".
allo stesso tempo, abbiamo,
7 ascensori, ed ognuno di essi abbiamo 3 lettere (... i 6 piani...), e quindi anche qui 21 "presenze"

Sembra che quadri, tutto,
dobbiamo ora solo disporre le lettere in modo appropriato ai 7 ascensori.

... continua ...

[Umby2]

Soluzione:

Di soluzioni, ce ne sono diverse.... (quante ?? )
Propongo la mia.

[axpgn]

Giusto!


Ma non penso ci siano molte soluzioni diverse anzi penso che la soluzione sia sostanzialmente unica (a meno di permutazioni e simili).

[Umby2]

"axpgn":Giusto!


Ma non penso ci siano molte soluzioni diverse anzi penso che la soluzione sia sostanzialmente unica (a meno di permutazioni e simili).

Ci sono.

[Umby2]

"Quinzio":
Quindi, una soluzione esiste per 11 piani, un limite massimo e' 15, quindi la soluzione e' sicuramente compresa tra 11 e 15.

Tu dai come soluzione massima 15, io ho trovato come soluzione massima 14 (vedi sopra),
ritengo che il 15 sia impossibile.... ti spiego...

se ci sono 15 piani, ogni piano dovrà essere presente in almeno 3 ascensori
Esempio: (Per il piano 1): [1-2-3-4-5-6] [1-7-8-9-10-11] [1-12-13-14-15-??]
questo perchè ogni piano potrà "accompagnare" il piano stesso ad altri 5 piani, 14 / 5 = meno di 3

Si deduce che se ogni piano dovrà essere presente almeno 3 volte,
per i ns. 15 piani, abbiamo bisogno di almeno 45 presenze. (sarebbero il numero totale dei bottoni presenti in tutti gli ascensori)
Ci siamo ?
Ma abbiamo solo 7 ascensori, ed ognuno dei 7 solo 6 piani (6 x 7 = 42)
Insufficienti !!!