Uova e palazzi [L 00]

Esercizi sulla verità delle proposizioni e problemi che non sembrano rientrare in nessun'altra categoria.
Rho33
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Uova e palazzi [L 00]

Messaggio da Rho33 »

Madonna quanto mi hai fatto ridere! :lol: Ti giuro che mentre leggevo ci stavo davvero credendo, e dicevo: "ma che cavolo sta dicendo?" :lol: :lol:
MattialaRana
Messaggi: 40
Iscritto il: 17/02/2016, 17:17

Re: Uova e palazzi [L 00]

Messaggio da MattialaRana »

ok ci provo...
consideriamo la successione dei piani e scegliamo un intero positivo k. lanciamo ora il primo uovo da ogni piano multiplo di k, partendo da k e seguendo l'ordine dei piani. se dopo l'n-esimo lancio l'uovo non si è rotto, allora il piano limite non è compreso nell'intervallo tra l'(n-1)k-esimo piano e l'(nk)-esimo piano. Possiamo quindi proseguire con l'(n+1)-esimo lancio. Se invece l'uovo si rompe, allora (poiché è scontato che se abbiamo effettuato il lancio l'uovo non si era rotto nel lancio precedente) il piano limite è compreso nell'intervallo tra l'(n-1)k-esimo piano e l'(nk)-esimo piano. ora sarà sufficiente provare tutti i piani (assolutamente nell'ordine perché ci è rimasto un solo uovo) per determinare qual'è il piano limite.
il tutto sta quindi nella scelta giusta di k: se lo si sceglie troppo grande una volta intervallo in cui è compreso il piano limite saranno necessarie troppe prove per individuarlo, se lo si sceglie troppo basso saranno invece necessarie troppe prove per individuare l'intervallo giusto.
se k è un divisore di 100, allora saranno necessari non più di(100/k)-1 lanci per individuare l'intervallo ( se k divide 100 non proveremo di certo a lanciare l'uovo dal centesimo piano), e al massimo k-1 lanci per individuare il piano limite. se k non divide 100 ci vorranno al massimo 100/k lanci (approssimato per difetto) per individuare l'intervallo e non più di k-1 per trovare il piano.
determiniamo il k per cui il numero di lanci è minimo. consideriamo k=10: saranno necessari al massimo 9+9=18 lanci.
ora non sto a dimostrare che è il minimo possibile (sarebbe un pò lungo) ma se non sbaglio si dovrebbe poter fare sul caso generale supponendo m piani, k radice quadrata di m e ipotizzando di scegliere un k diverso dalla radice di m, mostrando poi che il numero di lanci necessari sarebbe superiore a quello di lanci con k= radice di m ( che non è difficile dimostrare essere 2(k-1)) .
spero di non aver sparato grandi cavolate... :lol:
che dici è giusto?? :)
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Uova e palazzi [L 00]

Messaggio da Gizeta »

Non è la strategia ottimale, ma sei su una strada funzionante :D
MattialaRana
Messaggi: 40
Iscritto il: 17/02/2016, 17:17

Re: Uova e palazzi [L 00]

Messaggio da MattialaRana »

Quindi c'è un modo per farlo con meno di 18 lanci??
MattialaRana
Messaggi: 40
Iscritto il: 17/02/2016, 17:17

Re: Uova e palazzi [L 00]

Messaggio da MattialaRana »

Una volta che si è rotto il primo uovo, per esempio dall'n-esimo piano, per individuare il piano limite è necessario lanciare l'uovo da tutti i piani da m+1 a n-1, dove m è il piano più alto da cui il primo uovo è stato lanciato senza rompersi (se non ce ne è uno allora m=0). Ora si tratta di trovare il modo per cui sono necessari meno lanci, che credo sia appunto lanciarlo da tutti i piani multipli di un certo k... è qui che sbaglio??
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Uova e palazzi [L 00]

Messaggio da Gizeta »

Cerca di ragionare al contrario tenendo conto del fatto che la tua idea è buona!
Testo nascosto:
Considera, ad esempio, un certo insieme di piani [tex]\{\alpha_1,...,\alpha_n\}[/tex] e diciamo che il minimo cercato è [tex]\alpha[/tex], allora deve risultare [tex](\forall i)(i \in \{1,2,...,n\})[/tex], ponendo [tex]\alpha_0=0[/tex], che [tex]i+(\alpha_i-\alpha_{i-1}-1)=\alpha[/tex]
Newton
Messaggi: 56
Iscritto il: 07/09/2014, 21:48

Re: Uova e palazzi [L 00]

Messaggio da Newton »

La risposta dovrebbe essere [tex]14[/tex] lanci.
Se abbiamo a disposizione [tex]n[/tex] lanci, sappiamo che dal piano [tex]m-1[/tex] in giù le uova lanciate non si rompono e abbiamo ancora a disposizione entrambe le uova, allora il piano più alto (e quindi il migliore al nostro scopo) da cui possiamo effettuare il prossimo lancio è il piano [tex]m+n[/tex]. Infatti, se tirassimo dal piano [tex]m+n+p[/tex] e l'uovo si rompesse, allora con l'altro uovo dovremmo effettuare lanci dal piano [tex]m[/tex] in su fino a che abbiamo lanci a disposizione, ma se arrivati all'[tex]n[/tex]-simo lancio, e cioè quello dal piano [tex]n+m-1[/tex], il secondo uovo non si fosse ancora rotto allora sapremmo solo che il piano limite si trova tra il piano [tex]m+n[/tex] e il piano [tex]m+n+p[/tex] ma non l'avremo ancora individuato, a meno che [tex]p=0[/tex]. Quindi, con [tex]14[/tex] lanci a disposizione, effettuiamo il primo lancio al piano [tex]14[/tex] (considerando il piano terra come piano [tex]0[/tex]. Se l'uovo si rompe allora ci bastano i [tex]13[/tex] lanci rimasti per trovare il piano limite, altrimenti saliamo fino al piano [tex]14+13=27[/tex], e poi se necessario ai piani [tex]39[/tex], [tex]50[/tex], [tex]60[/tex], [tex]69[/tex], [tex]77[/tex],[tex]84[/tex], [tex]90[/tex], [tex]95[/tex], [tex]99[/tex] e infine [tex]100[/tex].
Con [tex]13[/tex] lanci invece potremmo raggiungere al massimo il piano [tex]13+12+11+...+1=\frac{n(n+1)}{2}=\frac{13\cdot14}{2}=91[/tex].
Generalizzando, otteniamo che per [tex]k[/tex] piani la soluzione è [tex]\left\lceil \frac{\sqrt{8k+1}-1}{2} \right\rceil[/tex].
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Uova e palazzi [L 00]

Messaggio da Gizeta »

Bene :D
CosecantofPi
Messaggi: 41
Iscritto il: 15/04/2017, 13:34

Re: Uova e palazzi [L 00]

Messaggio da CosecantofPi »

Una startegia potrebbe essere la seguente, ma funziona solo con palazzi il cui numero di piani e' un quadrato perfetto:
Sia $A$ il numero dei piani del palazzo, allora, avendo a disposizione due uova, il massimo numero di tentativi con la strategia migliore potrebbe essere data da:
$$\frac{A}{\sqrt{A}}+(\sqrt{A}-1)$$
In questo caso, avendo 100 piani, il numero massimo di mosse eseguite con la strategia migliore (ossia che minimizza questo massimo) e':
$$\frac{100}{10} + 9 = 19$$
Probabilmente puo' essere migliorata e generalizzata, ma in generale, credo che le uova debbano essere lanciati ogni $n-esimo$ piano, con $n$ che corrisponde al divisore di $A$ (Numero dei piani del palazzo) minore o uguale alla sua radice.
Rispondi