Крутейшие задачи на комбинаторику

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

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

Задача про тысячу пробирок

Пред­ставь­те, что вы рабо­та­е­те в лабо­ра­то­рии, кото­рая ищет сред­ство от смер­тель­ной болез­ни. Вам на испы­та­ние при­шла пар­тия из 1 000 про­би­рок с лекар­ством, кото­рое нуж­но опро­бо­вать на людях. Про­вер­ка санк­ци­о­ни­ро­ва­на Мин­здра­вом, у вас име­ют­ся все лицен­зии, но есть про­бле­ма. Вы узна­ё­те, что одну про­бир­ку пере­пу­та­ли и по ошиб­ке отпра­ви­ли вме­сто лекар­ства ядо­ви­тый реак­тив. Внешне он ничем не отли­ча­ет­ся от меди­ка­мен­та.

Вам нуж­но как мож­но ско­рее пере­дать про­бир­ки в боль­ни­цы для запус­ка кли­ни­че­ско­го теста, но отправ­лять отрав­лен­ную про­бир­ку нель­зя: погиб­нут люди. Тесты всех про­би­рок зай­мут меся­цы, это очень дол­го. Но у вас есть лабо­ра­тор­ные мыши. Вы зна­е­те, что лекар­ство без­вред­но для них, но даже кап­ля яда убьёт мышь за сут­ки. У вас 10 мышей, а про­би­рок — 1 000.

Как вычис­лить про­бир­ку с ядом как мож­но быст­рее? За какое вре­мя мож­но гаран­ти­ро­ван­но най­ти про­бир­ку с ядом?

Само­про­вер­ка. Преж­де чем узнать реше­ние, ответь­те на такие вопро­сы:

  • Раци­о­наль­но ли выби­рать какие-то отдель­ные бутыл­ки из общей мас­сы или нуж­но про­те­сти­ро­вать всё?
  • Есть ли в усло­вии зада­чи лимит по коли­че­ству вве­дён­но­го лекар­ства?
  • Обя­за­ны ли мы тести­ро­вать одну мышь толь­ко одной про­бир­кой? Мож­но ли исполь­зо­вать одно живот­ное несколь­ко раз или дать ему лекар­ства из несколь­ких про­би­рок?
Решение

Сна­ча­ла кажет­ся, что решить зада­чу нере­аль­но — мышей в 100 раз мень­ше, чем про­би­рок. Зна­чит, нам нуж­но как-то научить­ся быст­ро сокра­щать коли­че­ство эле­мен­тов, кото­рые нуж­но про­ве­рить.

Мы зна­ем, что даже кап­ля яда убьёт мышь за сут­ки. Зна­чит, если мы сме­ша­ем эту кап­лю с насто­я­щим лекар­ством, яд тоже сра­бо­та­ет. Вос­поль­зу­ем­ся этим так:

Раз­де­лим все про­бир­ки на рав­ные груп­пы — по 100 про­би­рок в каж­дой.

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

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

Восемь групп по 11 про­би­рок и одна груп­па из 12 про­би­рок.

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

Пред­по­ло­жим самый слож­ный слу­чай — яд был в сме­си из 12 про­би­рок. У нас оста­ёт­ся восемь мышей и 12 про­би­рок. Их тоже делим на восемь групп:

Четы­ре груп­пы по две про­бир­ки и четы­ре груп­пы по одной про­бир­ке.

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

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

Ответ: мак­си­мум за четы­ре дня мы най­дём яд.

Сторож и фонарик

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

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

Решение

Назо­вём каж­дую бата­рей­ку отдель­ной бук­вой — А, Б, В, Г, Д, Е, Ж, З. Это поз­во­лит нам не пере­пу­тать бата­рей­ки, когда мы будем менять их места­ми.

Теперь разо­бьём бата­рей­ки на пары и про­ве­рим в фона­ри­ке каж­дую из них:

(А Б) (В Г) (Д Е) (Ж З) — это четы­ре пер­вые пары.

Если фона­рик зара­бо­тал на какой-то из них — отлич­но, мы нашли нуж­ную пару.

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

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

Сле­до­ва­тель­но, раз ни одна из пар не вклю­чи­ла фонарь, в любой из них есть одна рабо­чая и одна нера­бо­чая бата­рей­ка.

Теперь возь­мём любые две пары — напри­мер (А Б) и (В Г) — и поме­ня­ем в них пер­вые бата­рей­ки места­ми. Полу­чим:

(В Б) и (А Г) — в этот момент мы про­ве­ри­ли уже шесть пар.

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

Берём пару (В Б), доста­ём отту­да вто­рую бата­рей­ку Б и ста­вим её на пер­вое место в паре (А Г), полу­ча­ем (Б Г) — это седь­мая пара.

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

Полу­ча­ет­ся, что нам пона­до­бит­ся про­ве­рить мак­си­мум 7 пар.

Как надевают носки настоящие программисты

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

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

Вопрос: сколь­ко мак­си­маль­но нуж­но достать нос­ков из ящи­ка, что­бы полу­чить пару оди­на­ко­во­го цве­та? А что, если тре­бу­ет­ся взять с собой запас­ной ком­плект и он тоже дол­жен быть одно­го цве­та?

Решение

Для одной пары

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

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

Для двух пар

Две пары могут быть раз­но­го цве­та — давай­те это учтём при реше­нии.

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

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

Угон, криминал и логика

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

  • Пер­вый утвер­ждал, что это были синие «Жигу­ли».
  • Вто­рой — что это чёр­ная «Вол­га».
  • Тре­тий вооб­ще ска­зал, что это был «Мер­се­дес», но точ­но не синий.

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

Как он это сде­лал?

Решение

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

1-й вари­ант: допу­стим, пер­вый сви­де­тель ска­зал прав­ду про цвет, но наврал про мар­ку. Полу­ча­ет­ся, что цвет маши­ны — синий, и это точ­но не «Жигу­ли».

Тогда вто­рой сви­де­тель, кото­рый ска­зал про чёр­ную «Вол­гу», наврал про цвет, а это зна­чит, что про мар­ку он ска­зал прав­ду. Полу­ча­ет­ся, что маши­на была — синяя «Вол­га».

Теперь про­ве­рим пока­за­ния тре­тье­го сви­де­те­ля. Он тоже один раз ска­зал прав­ду, но его ответ был — «точ­но не синий „Мер­се­дес“». Выхо­дит, что он наврал и про цвет, и про мар­ку, а по усло­ви­ям зада­чи тако­го не может быть: каж­дый хоть раз ска­зал прав­ду.

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

2-й вари­ант: допу­стим, пер­вый сви­де­тель ска­зал прав­ду про мар­ку — «Жигу­ли», но наврал про цвет. Полу­ча­ет­ся, что у нас есть «Жигу­ли» точ­но не сине­го цве­та.

Вто­рой сви­де­тель ска­зал, что это была чёр­ная «Вол­га», но мы уже поня­ли, что это были «Жигу­ли», а зна­чит, вто­рой наврал про мар­ку и ска­зал прав­ду про цвет. А цвет у вто­ро­го сви­де­те­ля — чёр­ный. Полу­чи­лись чёр­ные «Жигу­ли». Про­ве­рим пока­за­ния тре­тье­го.

Тре­тий сви­де­тель ска­зал, что это был «точ­но не синий „Мер­се­дес“», но мы-то уже зна­ем про «Жигу­ли», поэто­му тре­тий с мар­кой тоже наврал. А про цвет он как раз ска­зал прав­ду: не синий — это тоже может быть чёр­ный.

Всё схо­дит­ся: пре­ступ­ни­ки уеха­ли на чёр­ных «Жигу­лях». Хотя луч­ше бы на «Мер­се­де­се».

Кто держит зебру? (задача Джейсона Стэйтема)

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

Зада­ча зву­чит так:

  1. На ули­це сто­ят пять домов.
  2. Англи­ча­нин живёт в крас­ном доме.
  3. У испан­ца есть соба­ка.
  4. В зелё­ном доме пьют кофе.
  5. Укра­и­нец пьёт чай.
  6. Зелё­ный дом сто­ит сра­зу спра­ва от бело­го дома.
  7. Тот, кто май­нит Bitcoin, раз­во­дит ули­ток.
  8. В жёл­том доме май­нят Ethereum.
  9. В цен­траль­ном доме пьют моло­ко.
  10. Нор­ве­жец живёт в пер­вом доме.
  11. Сосед того, кто май­нит Stellar, дер­жит лису.
  12. В доме по сосед­ству с тем, в кото­ром дер­жат лошадь, май­нят Ethereum.
  13. Тот, кто май­нит IOTA, пьёт апель­си­но­вый сок.
  14. Япо­нец май­нит Monero.
  15. Нор­ве­жец живёт рядом с синим домом.

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

Вопрос: кто пьёт воду, а кто дер­жит зеб­ру?

Что­бы не было спор­ных момен­тов, доба­вим сле­ду­ю­щее:

  • дома рас­по­ло­же­ны в ряд, друг за дру­гом;
  • один из жиль­цов точ­но пьёт воду, и кто-то из жиль­цов точ­но дер­жит зеб­ру.
Решение

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

Дом  1 2 3 4 5
Цвет жёл­тый синий ? ? ?
Наци­о­наль­ность нор­ве­жец ? ? ? ?
Напи­ток вода ? ? ? ?
Крип­то­ва­лю­та Ethereum ? ? ? ?
Живот­ное ? ? ? ? ?

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

Разбираемся с первым домом

В п. 10 явно ска­за­но, что нор­ве­жец живёт в пер­вом доме, а если доба­вить сюда п. 15 (нор­ве­жец живёт рядом с синим домом), то ста­но­вит­ся понят­но, что вто­рой дом — синий.

Теперь раз­бе­рём­ся с цве­том пер­во­го дома. Мы уже зна­ем, что рядом с пер­вым домом сто­ит синий дом, а зна­чит это един­ствен­ный дом, кото­рый сто­ит рядом с пер­вым. Из пунк­та 6 (зелё­ный дом сто­ит сра­зу спра­ва от бело­го дома) сле­ду­ет, что пер­вый дом не может быть зелё­ным или белым — зелё­ный и белый долж­ны сто­ять рядом, а у нас рядом с пер­вым домом сто­ит синий. Оста­ют­ся крас­ный или жёл­тый. Но в крас­ном доме живёт англи­ча­нин — так напи­са­но в п. 2, поэто­му оста­ёт­ся толь­ко жёл­тый. Пер­вый дом — жёл­тый.

Смот­рим, что гово­рят нам усло­вия зада­чи про жёл­тый дом:

п. 8 — в жёл­том доме май­нят Ethereum;

п. 12 — в доме по сосед­ству с тем, в кото­ром дер­жат лошадь, май­нят Ethereum.

Но у нас рядом с домом, где май­нят Ethereum, сто­ит толь­ко вто­рой дом, поэто­му лошадь дер­жат во вто­ром доме.

Пере­хо­дим к напит­кам. Мы уже зна­ем, что в пер­вом жёл­том доме живёт нор­ве­жец, кото­рый май­нит Ethereum. Вот как это вли­я­ет на усло­вия:

  • Нор­ве­жец не пьёт чай, пото­му что это дела­ет укра­и­нец в п. 5.
  • Нор­ве­жец не пьёт кофе, пото­му что по п. 4 кофе пьют в зелё­ном доме.
  • Нор­ве­жец так­же не пьёт моло­ко, пото­му что в п. 9 напи­са­но, что в цен­траль­ном доме пьют моло­ко. Но так как пер­вый дом — не цен­траль­ный, то и моло­ко в пер­вом доме не пьют.
  • Нор­ве­жец не пьёт апель­си­но­вый сок, пото­му что соглас­но п. 13 апель­си­но­вый сок пьёт тот, кто май­нит IOTA.

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

Дом  1 2 3 4 5
Цвет жёл­тый синий ? ? ?
Наци­о­наль­ность нор­ве­жец ? ? ? ?
Напи­ток вода ? моло­ко ? ?
Крип­то­ва­лю­та Ethereum ? ? ? ?
Живот­ное ? лошадь ? ? ?

Всё о втором доме

Нач­нём с крип­то­ва­лю­ты.

Мы точ­но зна­ем, что это не Ethereum, пото­му что её май­нит нор­ве­жец в пер­вом доме. А ещё, раз у жиль­ца сине­го дома есть лошадь, то он точ­но не май­нит Bitcoin — в п. 7 напи­са­но, что тот, кто май­нит Bitcoin, раз­во­дит ули­ток. Давай­те пора­бо­та­ем с пред­по­ло­же­ни­я­ми и про­ве­рим, насколь­ко вер­ное каж­дое из них.

Допу­стим, что во вто­ром доме май­нят IOTA. По п. 13 (тот, кто май­нит IOTA, пьёт апель­си­но­вый сок) жилец пьёт апель­си­но­вый сок, а это зна­чит, что тут живёт не укра­и­нец, пото­му что он пьёт чай (п. 5). Это так­же не англи­ча­нин, кото­рый живёт в крас­ном доме (п. 2), и не испа­нец, пото­му что по п. 3 у испан­ца есть соба­ка. Япо­нец тоже тут жить не может, пото­му что по п. 14 япо­нец май­нит Monero, а не IOTA. Нор­ве­жец же, напом­ним, живёт в пер­вом доме. Полу­ча­ет­ся, что во вто­ром доме никто не живёт, а тако­го не может быть, сле­до­ва­тель­но, наше пред­по­ло­же­ние, что во вто­ром доме май­нят IOTA, невер­ное.

Идём даль­ше и пред­по­ло­жим, что во вто­ром доме май­нят Monero, а зна­чит, из п. 14 вид­но, что тут живёт япо­нец (япо­нец май­нит Monero). Поэто­му во вто­ром доме не пьют чай, пото­му что чай пьёт укра­и­нец (п. 5), не пьют кофе, пото­му что кофе пьют в зелё­ном доме (п. 4). А ещё здесь не пьют моло­ко — моло­ко пьют в тре­тьем доме (п. 9), и не пьют апель­си­но­вый сок, пото­му что сок пьёт люби­тель IOTA (п. 13). А раз вода уже заня­та нор­веж­цем, то полу­ча­ет­ся, что во вто­ром доме ниче­го не пьют. Тако­го не может быть, а зна­чит, наше пред­по­ло­же­ние, что во вто­ром доме май­нят Monero, невер­ное. Мы выяс­ни­ли, что там не май­нят Ethereum, Bitcoin, IOTA и Monero. Оста­ёт­ся толь­ко Stellar — её и май­нят во вто­ром доме.

Давай­те выяс­ним наци­о­наль­ность, зная назва­ние крип­то­ва­лю­ты. Это не англи­ча­нин, кото­рый живёт в крас­ном доме (п. 2), и не испа­нец с соба­кой (п. 3), пото­му что во вто­ром доме дер­жат лошадь. Ещё это не япо­нец, кото­рый май­нит Monero (п. 14), и не нор­ве­жец из пер­во­го дома. Полу­ча­ет­ся, что во вто­ром доме живёт укра­и­нец, а соглас­но п. 5 укра­и­нец пьёт чай.

Зане­сём новые дан­ные в таб­ли­цу:

Дом  1 2 3 4 5
Цвет жёл­тый синий ? ? ?
Наци­о­наль­ность нор­ве­жец укра­и­нец ? ? ?
Напи­ток вода чай моло­ко ? ?
Крип­то­ва­лю­та Ethereum Stellar ? ? ?
Живот­ное ? лошадь ? ? ?

Где живёт лиса

Исхо­дя из п. 11 (сосед того, кто май­нит Stellar, дер­жит лису), мы пони­ма­ем, что раз Stellar май­нят во вто­ром доме, то лиса живёт или в пер­вом, или в тре­тьем доме.

Допу­стим, что лиса — в тре­тьем доме. Теперь дела­ем вне­зап­ный пово­рот и зада­дим­ся вопро­сом: а что тогда пьёт чело­век из п. 7, кото­рый раз­во­дит ули­ток и май­нит Bitcoin? Он не пьёт сок, пото­му что сок пьёт люби­тель IOTA (п. 13), и моло­ко — его пьют в тре­тьем доме, где, как мы пред­по­ла­га­ем, дер­жат лису. Вода и чай уже заня­ты на преды­ду­щих эта­пах. Оста­ёт­ся толь­ко кофе, кото­рый пьют в зелё­ном доме (п. 4).

А раз так, то полу­ча­ет­ся, что в зелё­ном доме живёт чело­век, кото­рый раз­во­дит ули­ток, май­нит Bitcoin и пьёт кофе. Он точ­но не нор­ве­жец или укра­и­нец — мы это выяс­ни­ли рань­ше. И это точ­но не англи­ча­нин, кото­рый живёт в крас­ном доме (п. 2), не испа­нец, у кото­ро­го соба­ка (п. 3), и не япо­нец, кото­рый май­нит Monero (п. 14). Мы исклю­чи­ли все наци­о­наль­но­сти, а тако­го не может быть, поэто­му наше исход­ное пред­по­ло­же­ние о том, что лиса живёт в тре­тьем доме — невер­ное.

Полу­ча­ет­ся, что лиса живёт в пер­вом доме. Доба­вим это в таб­лич­ку:

Дом  1 2 3 4 5
Цвет жёл­тый синий ? ? ?
Наци­о­наль­ность нор­ве­жец укра­и­нец ? ? ?
Напи­ток вода чай моло­ко ? ?
Крип­то­ва­лю­та Ethereum Stellar ? ? ?
Живот­ное лиса лошадь ? ? ?

Третий дом

У нас оста­лось два сво­бод­ных напит­ка — кофе и апель­си­но­вый сок, кото­рые пьют в чет­вёр­том и пятом доме.

Тот, кто май­нит Bitcoin и раз­во­дит ули­ток, не живёт в доме, где пьют сок, пото­му что его пьёт люби­тель IOTA (п. 13). Зна­чит, дела­ем пред­по­ло­же­ние, что люби­тель ули­ток живёт в доме, где пьют кофе, а по п. 4 кофе пьют в зелё­ном доме. А мы толь­ко что разо­бра­ли в раз­де­ле про лису имен­но ту ситу­а­цию, когда жилец зелё­но­го дома раз­во­дит ули­ток и пьёт кофе. Тогда мы при­шли к выво­ду, что это невоз­мож­но, а зна­чит, люби­тель ули­ток не может пить кофе или сок, поэто­му он не живёт в чет­вёр­том или пятом доме.

Полу­ча­ет­ся, что люби­тель ули­ток, кото­рый май­нит Bitcoin, живёт в тре­тьем доме.

Дом  1 2 3 4 5
Цвет жёл­тый синий ? ? ?
Наци­о­наль­ность нор­ве­жец укра­и­нец ? ? ?
Напи­ток вода чай моло­ко ? ?
Крип­то­ва­лю­та Ethereum Stellar BitCoin ? ?
Живот­ное лиса лошадь улит­ки ? ?

Четвёртый и пятый дома

В зелё­ном доме пьют кофе (п. 4), а люби­тель IOTA пьёт сок (п. 13), поэто­му он не может жить в зелё­ном доме. Полу­ча­ет­ся, что в зелё­ном доме май­нят Monero, а раз так, то это — япо­нец (п. 14).

Это озна­ча­ет, что в остав­шем­ся доме пьют сок и май­нят IOTA, и дом этот на 3-м или на 4-м месте (по п. 6 — зелё­ный дом сто­ит сра­зу спра­ва от бело­го дома). Допу­стим, в тре­тьем доме живёт испа­нец, у кото­ро­го долж­на быть соба­ка (п. 3), но в таб­ли­це в тре­тьем доме уже есть улит­ки, а зна­чит, испа­нец с соба­кой живёт в чет­вёр­том доме, и как раз имен­но он пьёт сок и май­нит IOTA.

Тре­тий дом мето­дом исклю­че­ния оста­ёт­ся англи­ча­ни­ну, а это зна­чит, что тре­тий дом — крас­ный (п. 2). Полу­ча­ет­ся, что у испан­ца белый дом.

Запи­шем всё в таб­ли­цу:

Дом  1 2 3 4 5
Цвет жёл­тый синий крас­ный белый зелё­ный
Наци­о­наль­ность нор­ве­жец укра­и­нец англи­ча­нин испа­нец япо­нец
Напи­ток вода чай моло­ко сок кофе
Крип­то­ва­лю­та Ethereum Stellar BitCoin IOTA Monero
Живот­ное лиса лошадь улит­ки соба­ка ?

Зебра

У нас оста­лась одна неза­пол­нен­ная клет­ка в таб­ли­це, кото­рая тоже мето­дом исклю­че­ния доста­ёт­ся зеб­ре.

Теперь мы можем отве­тить на вопро­сы по зада­че: воду пьёт нор­ве­жец, а зеб­ру дер­жит япо­нец.