Самые интересные задачи на логику

Дав­но не было зада­чек! Вот под­бор­ка логи­че­ских задач, кото­рые ста­вят в тупик боль­шин­ство взрос­лых, обра­зо­ван­ных людей.

Задача про хитрого электрика

Одна­жды в сек­рет­ном каби­не­те что-то слу­чи­лось с про­вод­кой, и охра­на вызва­ла элек­три­ка, что­бы он всё почи­нил. Ему ска­за­ли, что три выклю­ча­те­ля нахо­дят­ся сна­ру­жи, а три лам­поч­ки — внут­ри. Лам­поч­ки сей­час не горят. Каж­дый выклю­ча­тель отве­ча­ет толь­ко за свою лам­поч­ку, но точ­ной схе­мы не зна­ет никто.

Элек­три­ку ска­за­ли как угод­но щёл­кать выклю­ча­те­ля­ми сна­ру­жи, но внутрь зай­ти раз­ре­ши­ли толь­ко один раз. Внут­ри с лам­поч­ка­ми тоже мож­но было делать что угод­но, но по сооб­ра­же­ни­ям сек­рет­но­сти воз­вра­щать­ся к выклю­ча­те­лям уже нель­зя. Элек­трик ухмыль­нул­ся, пощёл­кал выклю­ча­те­ля­ми, зашёл в ком­на­ту и сра­зу ска­зал, какой выклю­ча­тель отве­ча­ет за каж­дую лам­поч­ку. Как он это сделал?

Решение

Если решать зада­чу в лоб, то сра­зу напра­ши­ва­ет­ся такое реше­ние: вклю­чить одну лам­пу и выклю­чить дру­гую. В ито­ге, когда мы зай­дём в ком­на­ту, одна будет гореть, а дру­гая — нет, и мы пой­мём, какой выклю­ча­тель за что отвечает.

Но что делать с тре­тьей лам­пой? Если мы вклю­чим и её, то как отли­чим от такой же пер­вой? А если выклю­чим, то как отли­чим от нера­бо­та­ю­щей вто­рой? Нуж­но научить­ся раз­ли­чать две оди­на­ко­вые рабо­та­ю­щие или нера­бо­та­ю­щие лампы.

Самый про­стой спо­соб это сде­лать — раз­де­лить сами лам­пы допол­ни­тель­но на тёп­лые и холод­ные. Лам­па ста­но­вит­ся тёп­лой, когда пора­бо­та­ет, и даже если её выклю­чить, она всё рав­но какое-то вре­мя оста­нет­ся тёплой.

По усло­вию мы зна­ем, что все три лам­пы выклю­че­ны. Но вдруг они недав­но вклю­ча­лись и ещё не успе­ли остыть? Зна­чит, пер­вое, что мы дела­ем, — ждём неко­то­рое вре­мя, что­бы все лам­пы остыли.

Теперь щёл­ка­ем любым выклю­ча­те­лем и нагре­ва­ем одну лам­пу. После того, как она пора­бо­та­ла доста­точ­но вре­ме­ни, что­бы нагреть­ся, мы её выклю­ча­ем. Полу­ча­ет­ся, что у нас все три лам­пы выклю­че­ны, но две из них холод­ные, а одна — тёплая.

Затем, что­бы раз­ли­чить две холод­ные лам­пы, щёл­ка­ем любым дру­гим выклю­ча­те­лем и захо­дим в ком­на­ту. В ито­ге мы увидим:

  • одну рабо­та­ю­щую лам­поч­ку, кото­рую мы вклю­чи­ли толь­ко что;
  • одну нера­бо­та­ю­щую, но тёп­лую лам­поч­ку, кото­рую мы нагре­ли до этого;
  • и одну нера­бо­та­ю­щую и холод­ную лам­поч­ку, выклю­ча­тель от кото­рой мы ни разу не трогали.

Теп­ло и логика!

Новые приключения хитрого электрика

Один про­вай­дер решил про­ве­сти интер­нет через реку — от лево­го бере­га до пра­во­го. Для это­го он под водой про­ло­жил 49 про­во­дов, по кото­рым пере­да­ют­ся сиг­на­лы и элек­три­че­ский ток.

Все про­во­да ока­за­лись оди­на­ко­во­го цве­та, а под­ряд­чик забыл про­мар­ки­ро­вать их, что­бы понять, где какие кон­цы про­во­дов на обо­их берегах.

Что­бы выяс­нить, где что, позва­ли элек­три­ка и ска­за­ли ему под­пи­сать все про­во­да чис­ла­ми от 1 до 49 с каж­дой сто­ро­ны. Его зада­ча — про­ну­ме­ро­вать про­во­да на левом бере­гу и на пра­вом, разу­ме­ет­ся, что­бы чис­ла совпали.

Ему предо­ста­ви­ли катер, кото­рый может возить его сколь­ко угод­но раз с одно­го бере­га на дру­гой, линию с током на исход­ном бере­гу и муль­ти­метр, кото­рый пока­зы­ва­ет напря­же­ние в проводе.

Все дума­ли, что элек­трик пере­се­чёт реку как мини­мум 49 раз, но ему хва­ти­ло все­го двух раз — туда и обрат­но. Потом он про­сто сидел на бере­гу и задум­чи­во смот­рел на воду. Как ему это удалось?

Решение

На исход­ном бере­гу элек­трик пода­ёт напря­же­ние на любой про­вод и поме­ча­ет его как № 1. Все осталь­ные 48 он попар­но соеди­ня­ет меж­ду собой, что­бы на этой сто­роне полу­чил­ся один про­вод под напря­же­ни­ем и 24 пары. Как он это дела­ет — вооб­ще не важ­но, поря­док пар сей­час роли не игра­ет. После это­го элек­трик отправ­ля­ет­ся на пра­вый берег (пер­вая поездка).

При­плыв на место, он нахо­дит про­вод под напря­же­ни­ем с помо­щью тесте­ра — это про­вод № 1, он его так и поме­ча­ет. А даль­ше начи­на­ет­ся элек­три­че­ская магия.

Элек­трик берёт про­вод № 1 под напря­же­ни­ем, соеди­ня­ет его с любым дру­гим про­во­дом и под­пи­сы­ва­ет его как № 2. Но мы пом­ним, что на левом бере­гу все про­во­да соеди­не­ны попар­но, зна­чит, про­вод № 2 с той сто­ро­ны тоже с чем-то соеди­нён, а зна­чит, ток вер­нёт­ся обрат­но и появит­ся в новом про­во­де, кото­рый элек­трик под­пи­шет как № 3.

Даль­ше всё то же самое: он берёт про­вод с током № 3, соеди­ня­ет его с любым остав­шим­ся про­во­дом и под­пи­сы­ва­ет новый про­вод как № 4. А ещё он пом­нит про пары на том бере­гу, поэто­му ищет про­вод, в кото­ром сно­ва появил­ся ток и под­пи­сы­ва­ет его как № 5. Таким же обра­зом он соеди­ня­ет остав­ши­е­ся про­во­да и нуме­ру­ет все жилы на пра­вой сто­роне от 1 до 49. Сде­лав это, элек­трик воз­вра­ща­ет­ся на левый берег (вто­рая поездка).

Оста­лось самое инте­рес­ное: как на этом бере­гу про­ста­вить те же самые чис­ла на про­во­дах. Элек­трик зна­ет, как выгля­дит про­вод № 1, пото­му что он его под­пи­сал, но не зна­ет, как выгля­дит про­вод № 2.

Но он пом­нит, что про­вод № 1 соеди­нён на том бере­гу с про­во­дом № 2, кото­рый на этом бере­гу соеди­нён с про­во­дом № 3. Зна­чит, зада­ча элек­три­ка в том, что­бы най­ти это соеди­не­ние на левом бере­гу, где он нахо­дит­ся. Для это­го он разъ­еди­ня­ет по оче­ре­ди все соеди­не­ния и смот­рит, про­пал ли ток во всех осталь­ных про­во­дах. Если не про­пал во всех осталь­ных — зна­чит, разъ­еди­нил не ту пару и воз­вра­ща­ет её на место. А если про­пал — зна­чит, элек­трик нашёл соеди­не­ние про­во­дов № 2 и № 3. При этом тот неиз­вест­ный про­вод, кото­рый остал­ся под напря­же­ни­ем, будет про­вод № 2, а тот, с кото­рым он соеди­нял­ся, будет № 3.

После это­го элек­трик соеди­ня­ет под­пи­сан­ную пару обрат­но и начи­на­ет искать сле­ду­ю­щую точ­ку, кото­рая отклю­ча­ет все осталь­ные жилы — это будут про­во­да № 4 и № 5. Дей­ствуя по этой схе­ме, хит­рый элек­трик под­пи­шет все остав­ши­е­ся про­во­да. Про­вай­де­ру оста­нет­ся толь­ко разъ­еди­нить пары на каж­дом берегу.

Как перевезти гопников и философов с одного берега на другой

На одном бере­гу реки нахо­дят­ся шесть чело­век: три гоп­ни­ка и три фило­со­фа. Пока что они ведут непри­нуж­дён­ные бесе­ды об экзи­стен­ци­аль­ном, но все долж­ны будут рано или позд­но ока­зать­ся на дру­гом берегу.

Есть одна лод­ка, в кото­рую могут поме­стить­ся толь­ко два чело­ве­ка, но фило­со­фы управ­лять лод­кой не уме­ют, а гоп­ни­ки уме­ют. Так­же нель­зя остав­лять на одном бере­гу фило­со­фов боль­ше, чем гоп­ни­ков, пото­му что тогда фило­со­фы взо­рвут мозг гоп­ни­кам раз­го­во­ра­ми о при­ро­де вещей. Как пере­пра­вить всех через реку?

Решение

Для пер­вой поезд­ки есть пять вариантов: 

  • один гоп­ник — не под­хо­дит, пото­му что на бере­гу фило­со­фов ста­но­вит­ся боль­ше и они взо­рвут мозг;
  • два гоп­ни­ка — не под­хо­дит по той же причине;
  • один или два фило­со­фа — тоже нет, пото­му что они не уме­ют управ­лять лодкой;
  • фило­соф и гоп­ник — един­ствен­ный вари­ант, кото­рый остаётся.

Зна­чит, пер­вым рей­сом пара «философ-гопник» отправ­ля­ет­ся на дру­гой берег:

Алгоритмика в деле: как перевезти гопников и философов с одного берега на другой

Теперь лод­ку надо как-то отпра­вить назад. Но так как фило­соф не уме­ет ей управ­лять, то он оста­ёт­ся на бере­гу, а гоп­ник — воз­вра­ща­ет­ся. Фило­со­фы не взры­ва­ют нико­му мозг:

Алгоритмика в деле: философ остаётся на берегу, а гопник — возвращается

Теперь при­ки­нем вари­ан­ты сле­ду­ю­ще­го рей­са. Мы не можем отпра­вить двух гоп­ни­ков, ина­че фило­со­фы оста­нут­ся в боль­шин­стве, и наста­нет на левом бере­гу пол­ный экзистенциализм.

Поэто­му сно­ва на тот берег уплы­ва­ют фило­соф с гоп­ни­ком. При­чём гоп­ник выса­жи­ва­ет фило­со­фа, но сам из лод­ки не выле­за­ет — если так не сде­лать, то он оста­нет­ся с дву­мя фило­со­фа­ми на том бере­гу и они увле­кут раз­го­во­ра­ми об иде­ях вещей:

Алгоритмика в деле: гопник высаживает философа, но сам из лодки не вылезает

Таким обра­зом, у нас на том бере­гу сидят два фило­со­фа, а на этом — один фило­соф и три гоп­ни­ка, на кото­рых он вряд ли смо­жет воз­дей­ство­вать силой дискурса:

Алгоритмика в деле: на том берегу сидят два философа, а на этом — один философ и три гопника

Теперь нам нуж­но сде­лать выбор, кто поедет на этот раз. Мож­но отпра­вить сно­ва фило­со­фа и гоп­ни­ка, но тогда на том бере­гу ока­жут­ся три фило­со­фа. И без­опас­но пере­вез­ти осталь­ных гоп­ни­ков пооди­ноч­ке уже не полу­чит­ся — фило­со­фы все­гда будут в большинстве.

Зна­чит, оста­ёт­ся толь­ко один вари­ант: отпра­вить в путь двух гоп­ни­ков. В ито­ге на том бере­гу всех будет поров­ну и всё прой­дёт спокойно:

Алгоритмика в деле: в итоге на том берегу всех будет поровну и всё пройдёт спокойно

Но лод­ку надо как-то отпра­вить на дру­гой берег. Нель­зя раз­ме­стить на ней одно­го гоп­ни­ка, пото­му что вто­рой оста­нет­ся в мень­шин­стве сре­ди фило­со­фов. Двум гоп­ни­кам ехать обрат­но тоже не вари­ант, пото­му что они толь­ко что прибыли.

Поэто­му назад отправ­ля­ют­ся фило­соф и гопник:

Алгоритмика в деле: назад отправляются философ и гопник

Теперь един­ствен­ный без­опас­ный вари­ант — отпра­вить на тот берег двух гопников:

Алгоритмика в деле: теперь единственный безопасный вариант — отправить на тот берег двух гопников

Назад отпра­вим одно­го гоп­ни­ка. Что­бы не выхо­дить из лод­ки, он позо­вёт в неё фило­со­фа (напри­мер, фра­зой «Что вы дума­е­те о солип­сиз­ме?») и вер­нёт­ся с ним обрат­но на тот берег:

Алгоритмика в деле: назад отправим одного гопника, который позовёт в лодку философа

Точ­но так же заби­ра­ем остав­ше­го­ся философа:

Алгоритмика в деле: точно так же забираем оставшегося философа

И в ито­ге вся ком­па­ния ока­зы­ва­ет­ся на том бере­гу, без­дон­ное небо — над голо­вой, а нрав­ствен­ный закон — внутри:

Алгоритмика в деле: в итоге вся компания оказывается на том берегу

Как рассадить интровертов в баре

А вот задач­ка на струк­ту­ры дан­ных, сор­ти­ров­ку и алго­рит­ми­ку, кото­рая воз­мож­на толь­ко в нашей стране.

В Петер­бур­ге на ули­це Рубин­штей­на есть один бар, в кото­рый ходят лишь необ­щи­тель­ные люди, назо­вём их интро­вер­та­ми. (На самом деле интро­вер­ты общи­тель­ные, необ­щи­тель­ность — это миф. Но это задач­ка, поэто­му упростим.)

Интро­вер­ты садят­ся вдоль бар­ной стой­ки, где есть 25 мест. Когда вхо­дит новый посе­ти­тель, он все­гда садит­ся у стой­ки как мож­но даль­ше от осталь­ных гостей. Никто не садит­ся на сосед­нее место рядом с дру­гим интро­вер­том: если кто-то вхо­дит и видит, что сво­бод­ных мест мало и надо сесть рядом с кем-то, то он уходит.

Бар­мен хочет полу­чить как мож­но боль­ше кли­ен­тов. У него есть пра­во поса­дить само­го пер­во­го посе­ти­те­ля на любое место у стой­ки. Куда выгод­нее поса­дить пер­во­го интро­вер­та с точ­ки зре­ния бармена?

Решение

Для нача­ла най­дём иде­аль­ный вари­ант, кото­рый устро­ил бы бар­ме­на. Для это­го нари­су­ем 25 квад­ра­тов в ряд и закра­сим те, на кото­рых кто-то сидит. Помни­те, что ни один интро­верт по зада­че не сядет на сосед­нее место к другому.

Полу­ча­ет­ся, что это самая плот­ная рас­сад­ка, кото­рая воз­мож­на в этом баре. Так у стой­ки сидят 13 чело­век. Оста­лось толь­ко най­ти место для само­го пер­во­го посетителя.

Для нача­ла попро­бу­ем решить эту зада­чу в лоб и поса­дим пер­во­го посе­ти­те­ля на пер­вый стул:

Теперь вто­рой посе­ти­тель дол­жен сесть на сво­бод­ное место как мож­но даль­ше от него, то есть занять стул № 25:

Тре­тье­му доста­ёт­ся стул № 13, так как он ров­но посе­ре­дине меж­ду эти­ми двумя:

Два сле­ду­ю­щих зай­мут сво­бод­ные места точ­но посе­ре­дине меж­ду цен­траль­ным и боковыми:

И вот тут наста­ёт момент исти­ны: четы­ре сле­ду­ю­щих посе­ти­те­ля тоже сядут точ­но посе­ре­дине меж­ду заня­ты­ми места­ми. Это зна­чит, что меж­ду каж­дым будет по 2 пустых места:

В ито­ге у нас заня­то все­го 9 мест, но сесть боль­ше нику­да нель­зя: у каж­до­го сво­бод­но­го сту­ла есть как мини­мум один заня­тый сосед. Зна­чит, этот вари­ант не под­хо­дит. Нужен другой.

Что­бы прий­ти к пра­виль­но­му отве­ту, попро­бу­ем решать зада­чу с конца.

Вспом­ним иде­аль­ную рассадку:

Здесь сидит мак­си­маль­ное коли­че­ство гостей — 13, и меж­ду каж­дым из них есть сво­бод­ное место. Отмо­та­ем на шаг назад и посмот­рим, как мог­ли бы сидеть интро­вер­ты, что­бы новые гости сели точ­но меж­ду ними:

В этом слу­чае 6 новых гостей садят­ся точ­но посе­ре­дине меж­ду заня­ты­ми сту­лья­ми и иде­аль­но запол­ня­ют все места.

Теперь сде­ла­ем ещё шаг назад и посмот­рим, как долж­ны сидеть гости, что­бы новые кли­ен­ты сели на нуж­ные стулья:

Полу­ча­ет­ся, что если мы поса­дим пер­вых четы­рёх гостей так, как на рисун­ке выше, то даль­ше всё будет хоро­шо. Сде­ла­ем ещё шаг назад, что­бы понять, как они смог­ли так сесть:

Из рисун­ка вид­но, что два новых посе­ти­те­ля долж­ны сесть как мож­но даль­ше от заня­тых мест. Для это­го один садит­ся ров­но посе­ре­дине меж­ду дву­мя заня­ты­ми, а вто­рой — с само­го края, на пер­вое место. Таким обра­зом, меж­ду все­ми ними будет мак­си­маль­но воз­мож­ное рас­сто­я­ние. Оста­лось понять, как сели эти пер­вые два интроверта.

Если бы пер­вый гость сел с краю на стул № 25, вто­ро­му бы при­шлось сесть с про­ти­во­по­лож­но­го края на стул № 1 (мы это разо­бра­ли в самом нача­ле, в непра­виль­ном вари­ан­те). Зна­чит, пер­вый гость сел на стул № 9, а вто­ро­му при­шлось сесть мак­си­маль­но дале­ко от него — на самый послед­ний стул:

Полу­ча­ет­ся, само­го пер­во­го гостя бар­мен дол­жен поса­дить на стул № 9.

Как так вышло? Про­сто посчи­та­ли от обрат­но­го. Про­грам­ми­сты назы­ва­ют это Test-First Development, хех. 

Логическая задача про лифт

Одна­жды в 20-этажном доме вандалы-математики раз­би­ли почти все кноп­ки в лиф­те, сохра­нив толь­ко две. От корот­ко­го замы­ка­ния послед­ние ста­ли рабо­тать так: одна под­ни­ма­ет лифт на 13 эта­жей, а вто­рая опус­ка­ет на 8.

Как жиль­цам попасть с 13-го эта­жа на 8-й?

Классическое решение

В этой зада­че есть момент из реаль­ной жиз­ни, кото­рый суще­ствен­но упро­ща­ет реше­ние. Но нач­нём с клас­си­че­ско­го ответа.

Суть в том, что лифт не может выез­жать за гра­ни­цы эта­жей. То есть если на 13 эта­же мы нажмём кноп­ку «вверх», кото­рая долж­на под­нять лифт на 13 эта­жей, то он нику­да не поедет, пото­му что 13 + 13 = 26, а в доме столь­ко эта­жей нет. Зна­чит, един­ствен­ное, что нам оста­ёт­ся на пер­вом шаге — нажать «вниз»:

Вниз → 5 (13 - 8).

Здесь 5 — это номер эта­жа, на кото­рый при­е­хал лифт, а циф­ры в скоб­ках пока­зы­ва­ют начальный.

С 5 эта­жа мы можем уехать толь­ко вверх. Полу­ча­ет­ся, что каж­дый раз у нас есть толь­ко один вари­ант, на какую кноп­ку нажи­мать. Давай­те попро­бу­ем при­ме­нить этот прин­цип и посмот­реть, что получится:

Вниз → 5 (13 - 8).

Вверх → 18 (5 + 13).

Вниз → 10 (18 - 8).

Вниз → 2 (10 - 8).

Вверх → 15 (2 + 13).

Вниз → 7 (15 - 8).

Вверх → 20 (7 + 13).

Вниз → 12 (20 - 8).

Вниз → 4 (12 - 8).

Вверх → 17 (4 + 13).

Вниз → 9 (17 - 8).

Вниз → 1 (9 - 8).

Вверх → 14 (1 + 13).

Вниз → 6 (14 - 8).

Вверх → 19 (6 + 13).

Вниз → 11 (19 - 8).

Вниз → 3 (11 - 8).

Вверх → 16 (3 + 13).

Вниз → 8 (16 - 8).

В ито­ге за 19 поез­док мы добра­лись до нуж­но­го эта­жа. Самое инте­рес­ное, что по этим пра­ви­лам лифт даль­ше нику­да поехать не может: 8 + 13 = 21, а 8 - 8 = 0, что выхо­дит за гра­ни­цы эта­жей. При­дёт­ся всё-таки вызы­вать масте­ра и делать ремонт.

Хитроумное решение

Но есть и вто­рое реше­ние. Чаще все­го в жиз­ни быва­ет так: как толь­ко лифт доез­жа­ет до само­го верх­не­го или ниж­не­го эта­жа, он оста­нав­ли­ва­ет­ся, неза­ви­си­мо от того, сколь­ко ещё ему оста­ва­лось про­ехать. Это логич­но: дошли до гра­нич­ных зна­че­ний и оста­но­ви­лись. Вос­поль­зу­ем­ся этим и попро­бу­ем решить нашу зада­чу быстрее:

Вниз→ 5 (13 - 8).

Вниз → 1 (5 - 8) → дое­ха­ли до пер­во­го эта­жа и остановились.

А как добрать­ся с 1 эта­жа на 13 мы уже зна­ем из про­шло­го решения:

Вверх → 14 (1 + 13).

Вниз → 6 (14 - 8).

Вверх → 19 (6 + 13).

Вниз → 11 (19 - 8).

Вниз → 3 (11 - 8).

Вверх → 16 (3 + 13).

Вниз → 8 (16 - 8).

Ито­го 9 поез­док. В два раза мень­ше, чем пер­вым способом!

Граж­дане, бере­ги­те лифт!

Находчивый инженер в кафе

В кафе поста­ви­ли 3 раз­ных авто­ма­та, кото­рые нали­ва­ют напит­ки. В пер­вом – кофе, во вто­ром – чай, а в тре­тий выда­ёт слу­чай­ным обра­зом то кофе, то чай (пото­му что в жиз­ни все­гда долж­но быть место экс­пе­ри­мен­ту). Для каж­до­го из авто­ма­тов нуж­на 1 моне­та, что­бы полу­чить напиток.

На заво­де пере­пу­та­ли мар­ки­ров­ку авто­ма­тов, поэто­му на каж­дом из них ока­за­лась непра­виль­ная наклей­ка. Сколь­ко монет пона­до­бит­ся наход­чи­во­му инже­не­ру, что­бы понять, где какой автомат?

Решение

Несмот­ря на то что зада­ча кажет­ся запу­тан­ной, у неё доволь­но изящ­ное реше­ние. Сле­ди­те за рука­ми наход­чи­во­го инженера.

Кида­ем моне­ту в авто­мат с наклей­кой «Чай-кофе». Мы зна­ем, что на нём непра­виль­ная наклей­ка, как и на всех, поэто­му пра­виль­ная будет либо «Чай», либо «Кофе». Теперь смот­рим, что нам выдаст этот автомат.

Напри­мер, он выдал чай. Зна­чит, пра­виль­ная наклей­ка для это­го авто­ма­та — «Чай». Теперь нам нуж­но най­ти кофей­ный авто­мат сре­ди двух оставшихся.

Мы пом­ним, что все наклей­ки пере­пу­та­ны, поэто­му там, где будет напи­са­но «Кофе», на самом деле не кофей­ный авто­мат. Чай тоже уже занят. Поэто­му под над­пи­сью «Кофе» скры­ва­ет­ся авто­мат, кото­рый выда­ёт и кофе, и чай.

Зна­чит, с наклей­кой «Чай» будет авто­мат, кото­рый выда­ёт кофе.

О чудо! Что­бы разо­брать­ся с наклей­ка­ми, доста­точ­но все­го одной монеты!

Как успеть на презентацию

Илон Маск, Билл Гейтс, Тим Кук и Марк Цукер­берг хотят пер­вы­ми попасть на пре­зен­та­цию Xiaomi, поэто­му реши­ли вый­ти ночью, что­бы к утру быть уже на месте. Кру­гом тем­но­та, без фона­ри­ка нико­му идти нель­зя, но он один на всех. Пре­зен­та­ция — на дру­гом бере­гу вели­кой реки Янц­зы. Мост через реку хлип­кий и может выдер­жать одно­вре­мен­но мак­си­мум дво­их. Как всем пере­брать­ся на дру­гой берег как мож­но скорее?

Ско­рость пере­хо­да моста у каж­до­го своя: про­вор­ный Илон Маск пере­хо­дит его за 1 мину­ту, бод­ря­щий­ся Билл Гейтс — за 2, спо­кой­ный Тим Кук — за 5. Марк Цукер­берг после слу­ша­ний в Кон­грес­се быст­ро ходить не может, поэто­му тра­тит на мост 10 минут. Когда мост пере­хо­дят два чело­ве­ка, их ско­рость рав­на ско­ро­сти само­го мед­лен­но­го из пары.

Зада­ча — пере­ве­сти геро­ев на дру­гой берег как мож­но ско­рее, ведь места в оче­ре­ди у конгресс-центра уже зани­ма­ют мест­ные жители.

Решение

Самая ско­рост­ная пара у нас — Маск и Гейтс, поэто­му они с фона­ри­ком пере­хо­дят на дру­гой берег за 2 мину­ты (ско­рость Гейтса):

Илон Маск (1) и Билл Гейтс (2) → пере­шли на тот берег за 2 минуты.

Отправ­ля­ем с фона­рём назад само­го быст­ро­го из них:

Илон Маск (1) → вер­нул­ся обрат­но с фона­рём за 1 минуту.

Теперь нуж­но решить, какая пара пой­дёт сле­ду­ю­щей. Так как нам в любом слу­чае нуж­но отправ­лять Цукер­бер­га на тот берег, то это гаран­ти­ро­ван­но зай­мёт дол­гих 10 минут. Что­бы исполь­зо­вать это вре­мя опти­маль­но, отпра­вим с ним Тима Кука, кото­рый тоже не самый быст­рый из всех:

Тим Кук (5) и Марк Цукер­берг (10) → пере­шли на тот берег за 10 минут.

Оста­лось забрать Ило­на Мас­ка с того бере­га, зна­чит посы­ла­ем за ним само­го быст­ро­го из доступ­ных — Бил­ла Гейтса:

Билл Гейтс (2) → вер­нул­ся обрат­но с фона­рём за 2 минуты.

И они вдво­ём с Мас­ком отправ­ля­ют­ся на тот берег:

Илон Маск (1) и Билл Гейтс (2) → пере­шли на тот берег за 2 минуты.

Скла­ды­ва­ем все мину­ты на мосту: 2 + 1 + 10 + 2 + 2 = 17 минут. Зна­чит, все­го 17 минут им потре­бу­ет­ся, что­бы перей­ти вели­кую реку Янц­зы и занять места в зале рань­ше всех.

Находчивый альпинист

Один аль­пи­нист неудач­но спу­стил­ся с горы и насту­пил сра­зу на двух змей — коб­ру и гадю­ку. Одна из них его уку­си­ла, какая — неиз­вест­но. У него были с собой про­ти­во­ядия, по две таб­лет­ки каж­до­го вида: про­тив коб­ры и про­тив гадю­ки. Одну таб­лет­ку нуж­но при­нять сра­зу после уку­са, а дру­гую — на сле­ду­ю­щий день.

Аль­пи­нист вытрях­нул из упа­ков­ки на ладонь одну таб­лет­ку от коб­ры (K), стал вытря­хи­вать таб­лет­ку от гадю­ки (Г), но рука дрог­ну­ла и из упа­ков­ки Г выпа­ли обе таб­лет­ки. Теперь у него в руке три абсо­лют­но оди­на­ко­вые таб­лет­ки: одна K, две Г. А ему нуж­но немед­лен­но при­нять одну K и одну Г, оста­вив по вто­рой таб­лет­ке каж­до­го про­ти­во­ядия на зав­тра. Что ему делать?

Решение

Если таб­лет­ки никак нель­зя отли­чить друг от дру­га, зна­чит, надо при­ду­мать такое реше­ние, кото­рое не потре­бу­ет ана­ли­за всех таблеток.

Зада­ча аль­пи­ни­ста — при­нять одну таб­лет­ку от уку­са коб­ры и одну от уку­са гадю­ки. На ладо­ни лежат три таб­лет­ки, и если мы возь­мём любые две, то есть веро­ят­ность, что нам попа­дут­ся две таб­лет­ки от гадю­ки и тогда про­ти­во­ядие от коб­ры не сра­бо­та­ет (аль­пи­нист же не зна­ет, какая имен­но змея его уку­си­ла). Зна­чит, нам такой вари­ант не подходит.

Что­бы сего­дня и зав­тра при­нять оди­на­ко­вые пор­ции, аль­пи­ни­сту нуж­но к этим трём таб­лет­кам доба­вить чет­вёр­тую, раз­ло­мать их все попо­лам и раз­не­сти эти поло­вин­ки по двум раз­ным куч­кам. Смысл в том, что­бы в каж­дой куч­ке лежа­ло по одной поло­вин­ке от каж­дой таб­лет­ки. Тогда в обе­их будет по две поло­вин­ки таб­лет­ки от коб­ры и по две поло­вин­ки таб­лет­ки от гадю­ки, а две поло­ви­ны дают как раз целую таблетку.

Полу­ча­ет­ся, что ему сего­дня и зав­тра нуж­но съесть по 4 поло­вин­ки, по одной от каж­дой таблетки. 

Любите логику? На этом можно заработать
В ИТ сей­час одни из самых высо­ких зар­плат. Осва­и­вай­те любую ИТ-специальность, кото­рая вам по душе, и ста­но­ви­тесь бога­че. В «Прак­ти­ку­ме» — билет в про­фес­сию айтиш­ни­ка, приходите.