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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обложка:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Маша Климентьева

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Вам может быть интересно
Как выиграть в соревнованиях, когда играешь хуже всех
Как выиграть в соревнованиях, когда играешь хуже всех

Ещё одна обалденная задача на стратегию и игровую теорию.

hard
Коктейльная задача про доли и крепость
Коктейльная задача про доли и крепость

Ну, будем!

easy
Начинающим программистам: что такое фреймворки и библиотеки
Начинающим программистам: что такое фреймворки и библиотеки
medium
Геометрическая задача про программиста и плитку
Геометрическая задача про программиста и плитку

Интересная задача про площадь

easy
Быстрая задача про время
Быстрая задача про время

Если сможете решить в уме — наше почтение

easy
Посленовогодняя задачка: Санта-Клаус снова против Деда Мороза
Посленовогодняя задачка: Санта-Клаус снова против Деда Мороза

Кто быстрее: 9 оленей или 3 лошади?

easy
Хитрая головоломка про мандарины, секрет которой поймут только те, кто умеет логически мыслить
Хитрая головоломка про мандарины, секрет которой поймут только те, кто умеет логически мыслить

Секрет прост, но его нужно сформулировать

easy
Задача про скорость тестирования
Задача про скорость тестирования

Почему один программист уходит с работы раньше, чем второй

easy
Как выиграть в соревнованиях, когда играешь хуже всех
Как выиграть в соревнованиях, когда играешь хуже всех

Ещё одна обалденная задача на стратегию и игровую теорию.

hard
hard