matveychev_oleg (matveychev_oleg) wrote,
matveychev_oleg
matveychev_oleg

Category:

Самая сложная задача в мире



Как решить

В заголовке всё сказано.

Официально это самая сложная задача в мире. Автор — философ Джордж Булос.

Имеются три разработчика: бэкенд (А), фронтенд (В) и фулстек (С). Первый всегда говорит правду, второй всегда лжёт, а третий всегда отвечает случайным образом, то есть может как соврать, так и сказать правду. Нужно за три вопроса выяснить, кто из них кто.

Ограничения и условия:



  • программисты отвечают только фразами «Надо подумать» и «Зависит от ситуации». Одна из этих фраз означает «да», другая — «нет», но мы заранее не знаем, какая где;

  • один и тот же вопрос двум разработчикам задавать нельзя (но задать два вопроса одному разработчику — можно);

  • не обязательно задавать вопросы каждому разработчику, можно все три вопроса задать одному;

  • вы сами решаете, кому и в каком порядке задавать вопросы;

  • нельзя задавать философские вопросы, на которые нельзя ответить однозначно «Да» или «Нет»;

  • нельзя задавать такие вопросы, на которые невозможно ответить.



[Решение]
Решение

Наша задача — однозначно определить бэкенда и фронтенда, чтобы методом исключения найти фулстека.

Сложность задачи в том, что мы не знаем, что означают их ответы. Если мы что-то спросим и нам ответят «Надо подумать», то как мы поймём, это «Да» или «Нет»? Получается, что нам нужно задавать такие вопросы, чтобы уже с первого ответа понять, что на самом деле означает их «Зависит от ситуации» или «Надо подумать».

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

Например, сформулируем вопрос так «Если я спрошу у тебя „Программист В — это фулстек?“, ты ответишь мне „Зависит от ситуации“?»

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

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

Например, вот вопрос: «Если я спрошу у тебя „Разработчик В — это фулстек“, ты ответишь мне „Зависит от ситуации“?»

Если правильный ответ на заданный нами вопрос — «Да», то нам ответят «Зависит от ситуации», а если правильный ответ — «Нет», то нам ответят «Надо подумать».



[Доказательство]
Доказательство

Автор задачи понимал, что это утверждение нужно чем-то доказать, поэтому он сразу после текста задачи привёл доказательства своей правоты. Следите внимательно за логикой ответов.

1. Допустим, что «Зависит от ситуации» означает «Да», а «Надо подумать» означает «Нет»:

  • Мы спрашивали у бэкенда, и он ответил «Зависит от ситуации». Поскольку он всегда говорит правду и верный ответ на наш вопрос — «Зависит от ситуации», он означает «Да».

  • Мы спрашивали у бэкенда, и он ответил «Надо подумать». Поскольку он всегда говорит правду и верный ответ на наш вопрос — «Надо подумать», то он означает «Нет».

  • Мы спрашивали у фронтенда, и он ответил «Зависит от ситуации». Поскольку он всегда лжёт, то на наш вопрос он ответит «Надо подумать». Получается, что правильный ответ на вопрос — «Зависит от ситуации», который означает «Да».

  • Мы спрашивали у фронтенда, и он ответил «Надо подумать». Так как он всегда лжёт, то на наш вопрос он ответит «Зависит от ситуации». Получается, правильный ответ на вопрос — «Надо подумать», который означает «Нет».


2. Представим обратное: «Зависит от ситуации» означает «Нет», а «Надо подумать» означает «Да»:

  • Мы спрашивали у бэкенда, и он ответил «Зависит от ситуации». Поскольку он всегда говорит правду и верный ответ на наш вопрос — «Надо подумать», то его ответ означает «Да».

  • Мы спрашивали у бэкенда, и он ответил «Надо подумать». Поскольку он всегда говорит правду и верный ответ на наш вопрос будет «Зависит от ситуации», то его ответ означает «Нет».

  • Мы спрашивали у фронтенда, и он ответил «Зависит от ситуации». Так как он всегда лжёт, получается, что верный ответ на наш вопрос — «Надо подумать», и его ответ означает «Да».

  • Мы спрашивали у фронтенда, и он ответил «Надо подумать». Поскольку он всегда лжёт, то верный ответ на наш вопрос — «Зависит от ситуации», и получается, что его ответ означает «Нет».

Это безумно сложное на первый взгляд доказательство математически верное. Мы к нему ещё вернёмся, когда будем рассказывать про математическую логику и про то, как она работает в жизни.

Если вы три раза прочитали это, но так ничего и не поняли — это нормально, тогда просто поверьте, что доказательство верное 🙂



[Конец доказательства]
Конец доказательства

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

1. Сначала зададим второму разработчику вопрос: «Если я спрошу у тебя „Первый разработчик — это фулстек?“, ты ответишь мне „Зависит от ситуации“?»

Если второй разработчик отвечает «Зависит от ситуации», значит, либо он фулстек и отвечает абсолютно рандомно, либо он не фулстек, а на самом деле первый разработчик — фулстек. В любом варианте, третий оставшийся разработчик — это не фулстек.

Если же второй отвечает «Надо подумать», то либо он фулстек и отвечает случайным образом, либо он не фулстек, а это означает, что первый разработчик — тоже не фулстек. В любом варианте, первый разработчик — это не фулстек.

2. По первому вопросу нам стало понятно, кто из них НЕ фулстек. Спросим у него: «Если я спрошу у тебя: „Ты — фронтенд?“, ты ответишь мне „Зависит от ситуации“?» Поскольку он не фулстек, ответ «Надо подумать» означает, что он бэкенд, а ответ «Зависит от ситуации» означает, что он фронтенд.

3. Спросим у этого же разработчика «Если я у тебя спрошу: „Программист, которому я задавал свой первый вопрос — фулстек?“, ответишь ли ты „Зависит от ситуации“?» Если ответят «Зависит от ситуации» — то первый, у кого мы спрашивали, будет фулстеком, а если нам ответят «Надо подумать», то фулстеком будет программист, с которым ещё не говорили.

Последний разработчик определяется методом исключения.




Если вы прочитали решение и всё поняли с первого раза — снимаем шляпу.



Tags: задача
Subscribe

Recent Posts from This Journal

promo matveychev_oleg февраль 3, 2019 18:05 75
Buy for 100 tokens
Эта книга — антидот, книга-противоядие. Противоядие от всяческих бархатных революций и майданов, книга «анти-Джин Шарп», книга «Анти-Навальный». Мы поставили эксперимент. Когда книга была написана, но еще не издана, мы дали ее почитать молодому поклоннику…
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 5 comments