Lanciando stoviglie giù dalla finestra

[rand]

Siete stati ingaggiati da una fabbrica di bicchieri che vi affida il seguente strano incarico. C'è un grattacielo di n piani e dovete scoprire qual è il piano più basso per il quale lanciando giù dalla finestra un bicchiere del tipo prodotto dalla fabbrica questo si distrugge quando sbatte a terra. Per svolgere il vostro lavoro la fabbrica vi mette a disposizione solamente due esemplari assolutamente identici di bicchiere. Voi potete usarli per i vostri test e quando un bicchiere lanciato arriva a terra e non si rompe potete recuperarlo e riutilizzarlo. La domada è: qual è in funzione di n la strategia che minimizza al caso pessimo il numero di lanci necessario per determinare il piano in questione?

[ipparco]

Una soluzione può essere questa: si fanno i tentativi partendo dal primo piano e si sale di due piani alla volta (quindi, si prova al primo piano, al terzo piano, al quinto piano, ecc...). Quando il bicchiere si rompe, se si rompe, si scende di un piano e si prova per l'ultima volta.
Il caso pessimo è $ (n / 2) + 1 $
La "ricerca binaria" nel caso pessimo dà lo stesso risultato, perchè se i piani sono dispari e il piano giusto è quello appena sotto la metà, succede che si lancia il bicchiere al piano di mezzo, si rompe e poi tocca fare i tentativi partendo dal primo piano, salendo di un piano alla volta. Anche in questo caso il caso pessimo risulta $ (n / 2) + 1 $

[fph]

Hint: se invece di ogni due piani lanci il primo bicchiere a intervalli di k piani, qual è la formula per il caso pessimo? Qual è il valore di k che la rende minima?

[Alex89]

Mi ricorda qualcosa...

[darkcrystal]

E' facile vedere che la formula è $ \lceil n/k \rceil + (k-1) $, che possiamo riscrivere come $ n/k+1+k-1 $ tranne i casi antipatici, cioè $ n/k+k $

Per AM-GM, viene $ \frac{n}{k}+k \geq 2 \sqrt{n} $, e il caso minimo è il solito $ \frac{n}{k}=k $, quindi $ k=\sqrt{n} $

Bisognerebbe poi dare un senso a 'sta cosa come numero intero e dimostrare che è la strategia ottima, ma ora non ho proprio tempo...
Ciao