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

Как решить

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

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

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

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

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


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


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


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


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


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

Решение

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

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

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

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

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

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

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

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




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

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

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

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


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


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


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

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

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


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


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


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

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

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




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

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

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

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

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

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

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

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




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