n021 Ascensori
Dario
In un palazzo ci sono sette ascensori,
ciascuno puo' fermarsi in sei differenti piani al massimo.
Se e' sempre possibile trasferirsi da un qualunque piano ad un
altro con un singolo ascensore, qual e' il massimo numero di
piani presente in quel palazzo ?
Paolo
14
Cominciamo con vedere che non puo' essere di piu'
Con ciascun ascensore che fa 6 fermate si possono realizzare
6*5/2=15 collegamenti tra i piani quindi con 7 ascensori 15*7=105
collegamenti
Per collegare n piani sono necessari n*(n-1)/2 collegamenti da
cui il numero max di piani potrebbe essere trovato risolvendo
n*(n-1)/2 = 105
ossia n=15
Ma n=15 sarebbe possibile solo con una disposizione delle
fermate non ridondante, cioe' ciascuna coppia di piani deve
essere collegata in uno ed un solo modo.
Cio' non e' possibile, infatti, considerato il generico piano X,
questo deve essere collegato con altri 14 piani, e quindi deve
essere servito da almeno 3 ascensori. Ma ciascuno dei tre serve
altri 5 piani, quindi X e' collegato almeno 2 volte con lo stesso
piano.
Provo ora con 14 piani, utilizzando, indovina un po', una
vecchia conoscenza:
il RCP
(Regolo Circolare
perfetto, vedi alla sezione varie-approfondimenti)
Numero i piani in questo modo
A0, A1, ...A6, B0, B1, ...B6
Con un RCP a 7 archi e 3 tacche (0,1,3), collego i piani A
0,1,3
1,2,4
ecc
ed ad ogni terna di A associo la corrispondente terna di B
quindi
A0,A1,A3,B0,B1,B3
A1,A2,A4,B1,B2,B4
A2,A3,A5,B2,B3,B5
A3,A4,A6,B3,B4,B6
A4,A5,A0,B4,B5,B0
A5,A6,A1,B5,B6,B1
A6,A0,A2,B6,B0,B2
ciascun piano e' collegato una volta a quelli con diverso numero,
e tre volte con quelli con lo stesso numero
n022 Alberi
Supponiamo di avere r1 alberi di ordine
2 con 1 foglia (" | " ), r2 alberi di ordine 3 con 2
foglie ( "/\") ed infine r3 alberi di ordine 4 con 3
foglie ("/|\").
Unendoli tutti quanti alberi si possono formare?Es:
r1=2,r2=1,r3=0 abbiamo 6 alberi.
=========================================
Silvio Sergio
Bellissimo problema, mi ha fatto impazzire!
Sono nientepopodimeno che:
(3r3+2r2+r1)!
N(r1,r2,r3) = -----------------------
r1! r2! r3! (2r3+r2+1)!
Ancora mi fuma il cervello, non credo di riuscire a
ricostruire per intero il procedimento.
Come quasi sempre mi succede la soluzione è arrivata grazie ad
un mix di tecniche, che comprendono soluzione a mano dei casi
più semplici, programmazione per riempire una tabella con
qualche risultato di ordine maggiore, molti scarabocchi, alcune
considerazioni preliminari, molte altre suggerite dall'evolversi
dei risultati, qualche chilo di semplificazioni ed un po' di
fortuna.
Alla fine sembra tutto molto semplice, ma ancora non riesco a
venirne a capo.
Per esempio, guardate questo approccio, che avevo tentano ed
abbandonato:
tramite un algoritmo di visita (ad esempio la classica visita in
profondità, prima i figli poi il padre) possiamo rappresentare
un albero tramite una stringa:
Es.:
1
|
2
/ \
1 0
|
3
/|\
1 0 2
| / \
0 0 0
01000231021
Ogni albero genera una stringa, ma non tutte le stringhe sono
sintatticamente corrette, ad esempio il parsing di
"0210" genera un errore pur essendo corretto il numero
di foglie.
Con a=r1+r2+r3 caratteri "1,2,3" e f=2*r1+r2+1 foglie
"0" quante stringhe, anche non legali, si possono
formare?
Bisogna prima provvedere ad assegnare i posti per le foglie
(es.:0x0000xxx0xx) e si può farlo in C(a+f,f) modi diversi, e
per ogni assegnamento disporre gli a nodi interni al posto delle
x (es: 123121), e questo lo si fa D(a)=a!/(r1!r2!r3!) modi
diversi (alberi dello stesso ordine non sono distinguibili). In
totale sono S=C(a+f,f)*D(a)
Poiché risulta
N = S/(a+f)
questo suggerisce che solo una percentuale di 1/(a+f) di stringhe
risutano "ben formate", nel nostro esempio 1 su 10.
Qualcuno riesce a giustificare la cosa?
Intanto un notevole risultato che si ricava dalla formula trovata
è il seguente, generalizzazione di un problema noto nel caso
degli alberi binari (numeri Catalani):
N(r,0,0) = (r)!/(r!) = 1
N(0,r,0) = (2r)!/(r!*r!)
N(0,0,r) = (3r)!/(r!*(2r)!)
Credo si possa generalizzare tranquillamente ad alberi di ordine
qualsiasi
(nr)!/(r!((n-1)r)!)
====================================
Onoff
Bravissimo!Credevo che non interessasse a nessuno,invece
immancabilmente c'è la risposta di Silv:o) !!Anche a me è
costato molto risolverlo,solo che io partivo con 100 km di
vantaggio .....conoscevo la formula risolutiva.:-}
Io ho utilizzato il lemma di Raney che recita:
data una soluzione dell'equazione x1+x2+....+xn= -1 esiste solo
uno spostamento ciclico dei numeri a1,a2,..,an (soluzioni prima
citate)per cui tutte le somme parziali x1+...+xk con k=[1..n-1]
sono non negative.Da qui si può passare alle stringhe ( oppure
multinsiemi).
n023 20 o 200
100, 200, 150, 160, 170, 180, 110, 190,
140, 120, 130, 50, 60, 70, 80, 10, 90, 40, 20, 30.
1, 2, 3, 4, 9, 5, 6, 7, 8, 10, 11, 12, 13, 14, 19, 15, 16, 17,
18, 20.
Le due serie di numeri (1, 2, ... 20) e
(10, 20, ... 200) sono state riordinate con lo stesso criterio.
Quale?
Dario
C < I < L < X
Paolo Licheri
OK
pensavo di farti sudare di piu'
Dario
Effettivamente poteva essere non facile, ho fatto parecchi tentativi prima sulle forme letterali, posizione delle vocali, numero di sillabe ecc. Per risolvere questo genere di problemi occorre un po' di esperienza, un po' di fantasia e molta fortuna (culo).
Paolo Pedron
Scusate l'intromissione ma non sono riuscito a capire nemmeno
la soluzione.
Qualcuno potrebbe darmi delle spiegazioni più umane?
Dario
Hai ragione, ma non ho dato una risposta chiara per non
togliere il gusto a chi avesse voluto provarci.
L'autore invece ha capito.
Allora, mettendo tutto in numeri romani ti accorgerai che sono in
ordine alfabetico.
C=100, I=1, L=50, X=10.
Es: 9=IX viene prima di 5=V ecc..
Un'idea molto bella.
Paolo Licheri
Semplicemente (?) ho trasformato i dati in numeri romani, e
poi li ho disposti in ordine alfabetico.
In realtà era un problema un po' sadico.
n024 Tape
Posseggo una nutrita raccolta di
videocassette che per praticita' tengo numerate, 1,2,3,4,5....
Per numerarle utilizzo le 10 etichette autoadesive che portano le
cifre da 0 a 9 in dotazione ad ogni nastro.
Conservo in un cassetto tutte le etichette non utilizzate come
scorta.
Arrivato alla cassetta 11, ad es. gia' ricorsi alla scorta per
recuperare l'uno mancante.
Oggi con mia grande sorpresa non sono riuscito a numerare il
nastro appena acquistato.
Di quante videocassette e' composta la mia nastroteca ?
Paolo
Se hai 199991 videocassette ti manca un'etichetta con la cifra
1
La raccolta mi sembra troppo nutrita c'e' una soluzione migliore?
Mithrandir
Il risultato e` : 199.991
Il procedimento usato e` il seguente (infallibile) :
1) con la cassetta 1 uso 1 "1";
2) fino alla cassetta 2 uso 1 "1";
3) fino alla cassetta 3 uso 1 "1";
...
199.990) fino alla cassetta 199.990 uso 199.99 0 "1";
Per la cassetta dopo, sorprendentemente, ho problemi a trovare
abbastanza "1"...
Dario
c'e' una soluzione migliore?
No! e' proprio quella.
La raccolta e' bella grossa, ma i nastri li vende mio cugino ed
ho lo sconto!!