Informácie

Krištáľová guľa

Krištáľová guľa

Hovorí sa, že keď skvelý veštec, keď staval svoju novú krištáľovú guľu, chcel poznať jej odolnosť voči pádom. Urobil tak tri rovnaké lopty, jeden si pre neho nechal a ďalšie dva odovzdal svojmu učňovi, ktorému zveril úlohu kontrolovať ich odpor. Za týmto účelom mu nariadil, aby išiel do najvyššej budovy v meste s vysokými 117 poschodiami a povedal: Musíte ísť do prvého poschodia budovy a hodiť loptu oknom. Ak sa lopta nerozbije, choďte dolu a zdvihnite ju a opakujte test na druhom poschodí. To isté urobte pre každé poschodie budovy, kým nezistíte, ako vysoko je lopta schopná odolávať bez zlomenia. Dávajte pozor, aby ste mali iba dve gule a keď prelomíte druhú, nebudete môcť robiť žiadne ďalšie testy.

Kúzelnícky učeň, ktorý nebol príliš pracovitý, premýšľal o tom, ako kúzelník vykonal kontrolu s čo najmenším počtom testov, pretože sa zdalo byť veľmi náročnou úlohou ísť hore a dole po schodoch toľkokrát av najhoršom prípade. prípady by museli urobiť 117 testov!

Dokážete vymyslieť nejaký efektívnejší spôsob, ako nájsť podlahu, kde by sa gule rozbili, bez toho, aby ste museli vyskúšať všetky poschodia jeden po druhom?

Extrahované zo stránky Zurditorium.com

Riešenie

Je možné skontrolovať hádzaním lopty až 15-krát.

Stratégiou bude urobiť test na konkrétnom podlaží tak, aby v prípade rozbitia prvého lopty bolo možné obmedziť počet pokusov s druhým lopty na spodných podlažiach. Zavoláme X maximálny počet kontrol, ktoré chceme vykonať. Takže vieme, že ak vyhodíme prvú guľu z podlahy X a tá sa zlomí, budeme musieť otestovať všetky spodné podlahy od 1 do X-1, čo vykoná maximum X testov.

Ak sa na podlahe X lopta nezlomí, budeme mať kontroly X-1, aby sme mohli testovať na podlahe X + (X-1). Ak je prvá guľa zlomená, budeme musieť testovať všetky podlahy jeden po druhom od X + 1 do X + (X-1) - 1, až kým sa druhá guľa nerozbije, čo znova vykoná maximum X testov.

Podľa toho istého postupu by nasledujúcim poschodím, ktoré sa má testovať, boli X + (X-1) + (X-2). Opäť, ak sa prvá guľa zlomí na tomto poschodí, budeme musieť testovať všetky podlahy jeden po druhom od X + (X-1) + 1 do X + (X-1) + (X-2) - 1 pomocou druhá lopta, kým sa nerozbije.

Ak sa pozriete, vytvárame rovnicu X + (X-1) + (X-2) + (X-3) +… + (X- (X-1)), ktorej súčet musí byť väčší alebo rovný celkovému počtu poschodí ,

Napríklad, ak vezmeme X = 14, mali by sme 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 105, takže v najhoršom prípade by sme neprišli v celkovej výške budovy a ak vezmeme X = 15, mali by sme 15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 120, takže by sme mali dosť vyskúšajte všetky potrebné podlahy podľa opísaného systému.

Stratégia by teda bola takáto:

Prvý test robíme v 15. poschodí. Ak sa lopta rozbije, potom spolu s druhou loptičkou jeden po druhom skúšame všetky podlahy od 1 do 14, až kým sa druhá guľa nerozbije, a to bude maximálna výška, ktorá odoláva ball.

Ak sa prvá loptička nerozbije v 15. poschodí, pri druhom pokuse ju hodíme z 15. poschodia + 14 = 29.
Ak je prvá guľa zlomená, budeme skúšať s druhou guľou jeden po druhom všetky poschodia od 16. do 28. (13 poschodí), až kým sa nerozbije.

Ak by sa prvá guľa nerozbila na 29. poschodí, testovali by sme teraz na poschodí 15 + 14 + 13 = 42, ak by sa rozbila, museli by sme testovať všetky poschodia jeden po druhom od 30 do 41, až kým nenájdeme podlahu v Že druhá lopta je zlomená.

V tomto postupe by sme pokračovali, až kým nedosiahneme 117. poschodie. Je zrejmé, že týmto spôsobom nájdeme najvyššie poschodie, z ktorého môžeme hádzať loptu bez toho, aby sme pri 15 pokusoch prerušili najviac.

Podrobnejšie riešenie nájdete na stránke Zurditorium.com