Похихикивая к офферу

Думать или не думать?

Профессор логики едет в лифте. Лифт останавливается, и кто-то снаружи спрашивает: "Этот лифт едет вверх или вниз? Профессор отвечает: "Да."

Неуместная шутка

Действительно ли нам нужно логически рассуждать?

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

Представьте, что вы находитесь посреди технического собеседования. Интервьюер просит вас решить задачу, которая кажется достаточно простой. Вы уверены — у вас все получится. Но вот неожиданный поворот: задача заключается не только в написании кода, но и в объяснении своего мыслительного процесса. Вот тут-то логическое мышление и выходит на первый план. Думайте о логическом мышлении как о GPS для вашего мозга. Без него вы, возможно, все равно доберетесь до пункта назначения, но, скорее всего, сделаете много неверных поворотов, окажетесь в тупике или, что еще хуже, ваш мозг будет "пересчитывать маршрут" бесконечно.

Допустим, вас попросили спроектировать масштабируемое веб-приложение. Без логического мышления вы, возможно, начнете с того, что набросаете кучу микросервисов, базу данных и немного фронтенд-кода, надеясь, что все как-то сработает. С логическим мышлением вы обдумываете требования системы, проектируете надежную архитектуру и обеспечиваете беспроблемное взаимодействие всех компонентов. Плюс, вы избегаете создания цифрового аналога машины Голдберга (погуглите, если вы не знаете, что это такое, забавная штука). Никто не хочет платить за год работы, чтобы получить лишь черновую реализацию алгоритма Дейкстры.

Логическое мышление прекрасно, но иногда нужно добавить немного креативности для остроты. Даже обезьяна (ладно, может, не обезьяна, но ChatGPT точно) может реализовать алгоритм Дейкстры, но только человек может придумать новый.

Вот пример из моей жизни: вам поручили оптимизировать алгоритм. Логическое мышление помогает понять текущую производительность алгоритма и выявить узкие места. Но творческая искра может привести к инновационному подходу, который значительно повысит эффективность и ускорит работу вашего кода. Например, если мы рассматриваем дорожную сеть, нам даже не нужно пытаться начать строить автомобильную дорогу из Парижа в Нью-Йорк --- они определенно находятся в разных компонентах связности! Вычисление с алгоритма Дейкстры для такого запроса было бы весьма долгим --- нам пришлось бы обойти весь континент, чтобы доказать, что такого пути нет.

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

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

Так нужно ли нам логически рассуждать? Безусловно. Но это не единственный инструмент в вашем арсенале. Хорошо подготовленный кандидат сочетает логическое мышление с креативностью, адаптивностью и сильными коммуникативными навыками.

В этой главе мы рассмотрим классические вопросы и идеи, предназначенные для оттачивания ваших навыков логического мышления, приправив их (возможно, неудачными!) шутками и практическими примерами.

Танцующий крокобобр

Вопросы в этом разделе вдохновлены тестом на логическое мышление Войнаровского.

Тест на логическое мышление Мирослава Войнаровского появился в 2005 году на LiveJournal автора и с тех пор стал широко популярен в интернете среди русскоязычных пользователей. Тест направлен на оценку вашей способности различать правильные логические выводы от неправильных. Психолог обеспечил равные условия для всех участников теста, добившись экспериментальной чистоты.

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

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

В предложенных нами вопросах компоненты следующие:

Условие — Внимательно прочитайте вопрос. В нём представлена истинная ситуация, которая уже доказана и не оспаривается.Выводы — Это утверждения, которые нужно исследовать. Из четырёх предложенных выводов всегда есть ровно один правильный и ровно один явно неправильный. Ваша задача — их определить.Даже если вы думаете иначе, вопросы не связаны друг с другом.

Повышенный уровень сложности — постарайтесь не хихикнуть ни разу, решая этот тест.

Итак, три, два, один... Поехали!

Отделите правду от лжи

Не каждого крокобобра можно назвать большим. a. Не существует маленьких крокобобров; b. Маленькие крокобобры существуют; c. Каждого крокобобра можно назвать маленьким; d. Большие крокобобры скоро захватят мир.Все крокобобры — хищники. Все хищники любят котят. a. Котят любят крокобобры; b. Крокобобры ненавидят котят; c. Котята — хищники; d. Крокобобры — это котята.

Неверно, что все крокобобры любят пить молоко и танцевать. a. Есть по крайней мере один крокобобр, который не любит пить молоко, или не любит танцевать, или не любит ни то, ни другое; b. Каждый крокобобр любит пить молоко и танцевать; c. Среди тех, кто любит пить молоко и танцевать, есть хотя бы один крокобобр; d. Танцующие крокобобры любят котят.Существуют котобобры с кривыми хвостами (все котобобры имеют хвосты). a. Не каждый котобобр имеет прямой хвост; b. Не каждый котобобр имеет кривой хвост; c. Есть котобобры с прямыми хвостами; d. Среди тех, у кого кривые хвосты, точно нет котобобров.Если поцеловать котобобра, начнется буря. Котобобра поцеловали. a. Буря уже началась; b. Буря начнется когда-то; c. Буря начнется когда-то или уже началась; d. Буря не связана с целованием котобобров.Если поцеловать крокобобра, буря начнется немедленно. В последний час бури не было. a. Крокобобра не целовали в последний час; b. Крокобобра целовали в последний час; c. Не стоит целовать кого попало; d. Крокобобра поцеловали больше часа назад.И крокобобры, и боброкрокодилы живут в лесу. Ни один крокобобр не пьет водку. a. В лесу есть боброкрокодилы, пьющие водку; b. В лесу есть хотя бы один непьющий крокобобр; c. Все боброкрокодилы в лесу пьют водку; d. Среди тех, кто пьет водку в этом лесу, есть крокобобры.Неверно, что все боброкрокодилы длинные и светлого цвета. a. Все боброкрокодилы принадлежат к категории длинных и светлых существ; b. Существует боброкрокодил, который короткий, или тёмного цвета, или и то, и другое вместе; c. Каждый боброкрокодил короткий или тёмного цвета, но не и то и другое вместе; d. Длинный и светлый боброкрокодил определённо когда-то станет короче и темнее.Если покормить котобобра, он успокоится. Спокойного котобобра можно доить. a. Если не покормить котобобра, его нельзя будет доить; b. Котобобра можно доить без кормления, он сам найдёт, что поесть; c. После кормления котобобра можно доить; d. Котобобра нельзя доить независимо от его состояния.Если сделать котобобра счастливым, он даст молоко. Котобобр будет счастлив, если потянуть его за хвост.a. Если потянуть котобобра за хвост, он даст молоко; b. Всем будет приятно, если потянуть их за хвост; c. Если не тянуть котобобра за хвост, он не даст молоко; d. Дергание за хвостик не влияет на состояние котобобра.Все белкопопугаи иногда поют, но не всегда.a. Некоторые белкопопугаи никогда не поют; b. Некоторые белкопопугаи поют очень громко; c. Некоторые белкопопугаи иногда поют тихо; d. Не существует белкопопугаев, которые никогда не поют.Информация о том, что эта книга о забавных математических задачах, оказалась ложной.a. Информация оказалась ложной; b. Книга не о математических задачах; c. Книга не о математических задачах, но не забавных; d. Такого рода информации не было.Огромный синий крокобобр напугал нашего генерального директора.a. Генеральному директору приснился кошмар; b. Генеральный директор попробовал плохой выпивки; c. Генеральный директор был напуган; d. Огромные синие крокобобры не существуют.Каждый, кто громко квакал, точно был поцелован. Все бобродемоны постоянно громко квакают.a. Каждый, кто громко квакает, — бобродемон; b. Все бобродемоны точно были поцелованы; c. Некоторые бобродемоны не были поцелованы; d. Каждый, кто был поцелован, — громко квакающий бобродемон.Если котокурица видит врага, она прячется. Котокурица спряталась.a. Котокурица увидела врага; b. Котокурица сейчас спрятана; c. Котокурица не увидела врага; d. Котокурица никогда не прячетсяБоброангелы всегда ищут еду ночью. Они точно нуждаются в пище. a. Некоторые боброангелы активны ночью; b. Боброангелы никогда не ищут еду днём; c. Боброангелы ищут еду только ночью; d. Боброангелы ищут еду только днём.Боброкрокодилы могут либо высоко прыгать, либо быстро бегать. a. Некоторые боброкрокодилы могут высоко прыгать и быстро бегать; b. Ни один боброкрокодил не может высоко прыгать; c. Если боброкрокодил не может высоко прыгать, он определённо может быстро бегать; d. Все боброкрокодилы могут высоко прыгать.У каждой котокурицы есть хотя бы одна красная полоска. a. Ни у одной котокурицы нет синих полосок; b. У некоторых котокуриц больше одной красной полоски; c. Все котокурицы имеют красные полоски; d. У некоторых котокуриц вообще нет полосок.В книге есть задачи как про крокобобров, так и про боброкрокодилов. a. В книге нет задач про крокобобров; b. В книге есть задачи про боброкрокодилов; c. В книге есть только задачи про крокобобров и боброкрокодилов; d. Боброкрокодилы не существуют!Греомолы могут быть либо хорошими, либо плохими. Неверно, что этот греомол не плохой. a. Этот греомол хороший; b. Этот греомол посредственный; c. Этот греомол плохой; d. Этот греомол нелогичен.Когда вы дышите, вы всегда мурлычете. a. Если вы мурлычете, это значит, что вы дышите; b. Если вы не дышите, вы не мурлычете; c. Если вы не мурлычете, это значит, что вы не дышите; d. Если вы не мурлычете, это значит, что вы дышите.Жан остановился, отвечая на этот тест, после того как ответил всего на 22 вопроса. a. Жан устал, отвечая на этот тест; b. Жан очень устал, отвечая на этот тест; c. Жан не закончил этот тест; d. В этом тесте могло быть ровно 20 вопросов.Если вы обнимете уткобобра, он сразу же испортится. Этот уткобобр не испорчен. Сейчас я его обниму. a. Не трогайте уткобобра; b. Уткобобр испортится; c. Уткобобр не испортится; d. Любой испортится, если его обнять.Если вы обнимете уткобобра, он сразу же испортится. Этот уткобобр не испорчен. a. Уткобобра не обнимали; b. Уткобобра обнимали; c. Оставьте уткобобра в покое; d. Когда-нибудь этот уткобобр испортится.

А что было-то?

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

Не каждого крокобобра можно назвать большим.

Правда: Маленькие крокобобры существуют;

Ложь: Не существует маленьких крокобобров.

Все крокобобры — хищники. Все хищники любят котят.

Правда: Котят любят крокобобры;

Ложь: Крокобобры ненавидят котят.

Неверно, что все крокобобры любят пить молоко и танцевать.

Правда: Есть по крайней мере один крокобобр, который не любит пить молоко, или не любит танцевать, или не любит ни то, ни другое;

Ложь: Каждый крокобобр любит пить молоко и танцевать.

Существуют котобобры с кривыми хвостами (все котобобры имеют хвосты).

Правда: Не каждый котобобр имеет прямой хвост;

Ложь: Среди тех, у кого кривые хвосты, точно нет котобобров.Если поцеловать котобобра, начнется буря. Котобобра поцеловали.

Правда: Буря начнется когда-то или уже началась;

Ложь: Буря не связана с целованием котобобров.

Если поцеловать крокобобра, буря начнется немедленно. В последний час бури не было.

Правда: Крокобобра не целовали в последний час;

Ложь: Крокобобра целовали в последний час.

И крокобобры, и боброкрокодилы живут в лесу. Ни один крокобобр не пьет водку.

Правда: В лесу есть хотя бы один непьющий крокобобр;

Ложь: Среди тех, кто пьет водку в этом лесу, есть крокобобры.

Неверно, что все боброкрокодилы длинные и светлого цвета.

Правда: Существует боброкрокодил, который короткий, или тёмного цвета, или и то, и другое вместе;

Ложь: Все боброкрокодилы принадлежат к категории длинных и светлых существ.

Если покормить котобобра, он успокоится. Спокойного котобобра можно доить.

Правда: После кормления котобобра можно доить;

Ложь: Котобобра нельзя доить независимо от его состояния.Если сделать котобобра счастливым, он даст молоко. Котобобр будет счастлив, если потянуть его за хвост.

Правда: Если потянуть котобобра за хвост, он даст молоко;

Ложь: Дергание за хвостик не влияет на состояние котобобра.

Все белкопопугаи иногда поют, но не всегда.

Правда: Не существует белкопопугаев, которые никогда не поют;

Ложь: Некоторые белкопопугаи никогда не поют.

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

Правда: Информация оказалась ложной;

Ложь: Такого рода информации не было.

Огромный синий крокобобр напугал нашего генерального директора.

Правда: Генеральный директор был напуган;

Ложь: Огромные синие крокобобры не существуют.

Каждый, кто громко квакал, точно был поцелован. Все бобродемоны постоянно громко квакают.

Правда: Все бобродемоны точно были поцелованы;

Ложь: Некоторые бобродемоны не были поцелованы.Если котокурица видит врага, она прячется. Котокурица спряталась.

Правда: Котокурица сейчас спрятана;

Ложь: Котокурица никогда не прячется.

Боброангелы всегда ищут еду ночью. Они точно нуждаются в пище.

Правда: Некоторые боброангелы активны ночью;

Ложь: Боброангелы ищут еду только днём.

Боброкрокодилы могут либо высоко прыгать, либо быстро бегать.

Правда: Если боброкрокодил не может высоко прыгать, он определённо может быстро бегать;

Ложь: Некоторые боброкрокодилы могут высоко прыгать и быстро бегать.

У каждой котокурицы есть хотя бы одна красная полоска.

Правда: Все котокурицы имеют красные полоски;

Ложь: У некоторых котокуриц вообще нет полосок.В книге есть задачи как про крокобобров, так и про боброкрокодилов.

Правда: В книге есть задачи про боброкрокодилов;

Ложь: В книге нет задач про крокобобров.

Греомолы могут быть либо хорошими, либо плохими. Неверно, что этот греомол не плохой.

Правда: Этот греомол плохой;

Ложь: Этот греомол хороший.

Когда вы дышите, вы всегда мурлычете.

Правда: Если вы не мурлычете, это значит, что вы не дышите;

Ложь: Если вы не мурлычете, это значит, что вы дышите.

Жан остановился, отвечая на этот тест, после того как ответил всего на 22 вопроса.

Правда: Жан не закончил этот тест;

Ложь: В этом тесте могло быть ровно 20 вопросов.

Если вы обнимете уткобобра, он сразу же испортится. Этот уткобобр не испорчен. Сейчас я его обниму.

Правда: Уткобобр испортится;

Ложь: Уткобобр не испортится.

Если вы обнимете уткобобра, он сразу же испортится. Этот уткобобр не испорчен.

Правда: Уткобобра не обнимали;

Ложь: Уткобобра обнимали.

Что значат мои результаты?

Каждый правильный ответ приносит вам один балл, так что за каждый вопрос можно получить до 2 баллов. Сложите свои баллы и посмотрите, насколько вы молодец:

45-48 баллов:

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

35-44 баллов:

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

20-34 балла:

Вариант 1:

У вас не хватило терпения завершить весь тест, и вы выбирали оставшиеся варианты наугад.

Вариант 2:

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

24 points:

Возможный сценарий:

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

8-19 баллов:

Вариант 1:

Вы проходили тест, случайно выбирая варианты.

Вариант 2:

У вас нет логического мышления. Результат, который вы достигли, мог быть получен просто угадыванием. Не пытайтесь рассуждать логически, особенно публично. Люди могут считать вас, мягко говоря, странным.

4-7 баллов:

Вы не захотели проходить тест.

0-3 балла:

Вы мастер логики, но решили повеселиться и ответить на всё неправильно просто по фану.

Головоломайки

Существуют задачи, которые можно объединить в общую категорию, известную как задачи «логические». Самая сложная задача — объяснить решение настолько просто и подробно, чтобы даже первоклассник смог его понять («Я не смог этого сделать. Я не смог объяснить это на уровне первокурсника. Это значит, что я сам этого не понимаю.» — Р. Фейнман).

Один из классических методов решения логических задач — создание таблиц. Рассмотрим следующую задачу.

Пример: Три друга — Жан, Алекс и Сергей — преподают математику, физику и литературу в школах Нью-Йорка, Лос-Анджелеса и Парижа. Жан не работает в Лос-Анджелесе, Алекс не работает в Нью-Йорке, житель Нью-Йорка преподаёт литературу, житель Лос-Анджелеса не преподаёт физику, а Алекс не преподаёт математику. Какой предмет преподаёт каждый из них и в каком городе?

Решение: Построим таблицу парных соответствий между именами, городами и предметами. Мы объединим их в одну таблицу.

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

После того как мы поставили плюс для утверждения, что преподаватель литературы живёт в Нью-Йорке, заполним пустые ячейки третьего ряда и первого столбца правой подтаблицы минусами. Как только мы ставим минус из-за утверждения «житель Лос-Анджелеса не преподаёт физику», мы осознаём, что в колонке Лос-Анджелеса правой подтаблицы остаётся только одна пустая ячейка, поэтому мы ставим туда плюс. После первоначального заполнения мы видим таблицу, изображённую на рисунке а).

(а) После первоначального заполнения (б) Решённая задача

Мы уже узнали многое: преподаватель литературы живёт в Нью-Йорке, преподаватель математики живёт в Лос-Анджелесе, а преподаватель физики — в Париже.

Давайте рассуждать дальше. Алекс не живёт в Нью-Йорке, Алекс не математик, математик живёт в Лос-Анджелесе → Алекс не живёт в Лос-Анджелесе → Алекс живёт в Париже. Ставим плюс. Теперь мы знаем, что Жан живёт в Нью-Йорке, а Сергей — в Лос-Анджелесе. Объединяя наши знания, мы получаем итоговую таблицу на рисунке б).

Вокруг так называемой загадки Эйнштейна

Следующая головоломка часто приписывается Альберту Эйнштейну на множестве сайтов. Якобы он придумал её в начале 1900-х годов, утверждая, что только 2% населения смогут её решить. (Правда ли это сейчас? Было ли это когда-либо правдой? А иногда ещё говорят "решить в уме", так-то....)

Однако головоломка впервые появилась в публичном доступе в журнале Life International 17 декабря 1962 года, через семь лет после смерти Эйнштейна.

Эта головоломка, известная в англоязычной литературе как "Загадка о зебре" (Zebra Puzzle), иногда также связывается с Льюисом Кэрроллом. Однако нет никаких убедительных доказательств, что её создал либо Эйнштейн, либо Кэрролл. К тому же версия из Life International ссылается на марки сигарет, которых не существовало ни во времена Кэрролла, ни в молодости Эйнштейна.

Как выглядит наиболее известная постановка задачи?

Следующая версия головоломки появилась в Life International в 1962 году:

Пример:

Есть пять домов.

Англичанин живёт в красном доме.Испанец владеет собакой.Кофе пьют в зелёном доме.Украинец пьёт чай.Зелёный дом находится сразу справа от кремового дома.Курильщик Old Gold владеет улитками.Сигареты Kools курят в жёлтом доме.Молоко пьют в среднем доме.Норвежец живёт в первом доме.Мужчина, который курит Chesterfields, живёт в доме рядом с тем, в котором живёт лиса.Сигареты Kools курят в доме рядом с тем, где держат лошадь.Курильщик Lucky Strike пьёт апельсиновый сок.Японец курит Parliament.Норвежец живёт рядом с синим домом.Кто пьёт воду? Кто владеет зеброй?

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

Журнал LIFE International с удовольствием примет ответы от своих читателей и опубликует один или несколько из тех, которые, по мнению редакторов, лучше всего сочетают правильное решение с краткостью и ясностью в изложении логики, с помощью которой было достигнуто решение. Интуитивные ответы, пожалуйста, не присылайте.

— Life International, 17 декабря 1962 года

Кстати, как заметили Вассберг и Вассберг в своей статье "Перегружена ли головоломка Эйнштейна?" из 2009 года, в оригинальной версии подсказка 12 была плохо написана. В ней говорится, "Kools курят в доме рядом с тем домом, где держат лошадь". Правильнее было бы написать "... курят в одном из домов рядом...". Так как слово "тем" подразумевает в единственном числе, Kools пришлось бы курить либо во втором, либо в четвёртом доме в ряду, что приводит к противоречию.

Матрицы, которые есть

Можно построить бесконечное число подобных задач, но с меньшей сложностью, сократив количество параметров для рассмотрения. Существуют даже онлайн-генераторы для таких логических головоломок, которые во французском называются "intégrammes", а в английском — "logic grid puzzles". На русском нормальных генераторов я не нашла, возможно, дело в том, что это немного сложнее с лингвистической точки зрения: попробуйте не запутаться в падежах и двойных отрицаниях!

Вот пример упрощенной версии описанной ранее головоломки, которая, кажется, лучше подходит для собеседования на работу:

Пример:

На улице стоят четыре соседних дома разного цвета. В каждом доме живет человек разной национальности; каждый из четырех владельцев имеет разную профессию. Даны следующие подсказки:

Между серым домом и домом программиста — два дома.Швед живёт в черном доме.Англичанин живет в доме номер четыре.Датчанин живёт справа от банкира.Бельгиец живёт сразу справа от шведа.Астроном живёт в синем доме.Где находится белый дом?

Решение:

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

Англичанин живет в четвертом доме.

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

Заметим, что швед живёт в черном доме. Из первого условия следует, что серый дом должен быть либо домом номер 1, либо номером 4. Но дом номер 1 — чёрный, значит, серый дом — дом номер 4. Следовательно, программист живёт в первом доме.

Датчанин живёт справа от банкира. Так как программист живёт в первом доме, банкир живёт во втором доме.

Астроном живёт в синем доме, который должен быть третьим. Таким образом, белый дом — это дом номер 2.

Однако вернемся к нашим зебрам. Никто не исключает возможности, что на собеседовании вам могут дать лист бумаги с задачей, в которой вы сразу узнаете головоломку про зебру. Поняв, что вот-тут то вам карта и пошла, вы скажете: <<Зебра принадлежит японцу!>> И тогда интервьюер поймет, что вы даже не удосужились прочитать изменённые условия задачи. Неловко, не так ли?

И да, маловероятно, что вам действительно придется решать всю головоломку. Обычно достаточно начать логически рассуждать, чтобы интервьюер перешел к следующему вопросу.

— Вы действительно можете считать быстрее компьютера? — Да. — Сколько будет 25 умножить на 25? — Девять! — Это неправильно... — Но быстро!

Лживые рыцари

Еще одна важная тема в головоломках — рыцари (правдолюбы), лжецы и шпионы (или просто хитрецы, которые могут как говорить правду, так и лгать, возможно, с установленными ограничениями). Рассмотрим задачу на эту тему.

Пример:

Из трех человек, A, B и C, один является рыцарем, другой — лжецом, а третий — шпионом. A сказал: «Я шпион». B сказал: «A и C иногда говорят правду». C сказал: «B — шпион». Кто является лжецом, кто рыцарем, а кто шпионом?

Решение:

A утверждает, что он шпион, поэтому он не может быть рыцарем, потому что в этом случае он солгал бы.

Предположим, что A — лжец. Тогда он никогда не говорит правду, а значит, B солгал, когда сказал, что A и C иногда говорят правду, потому что если он имел в виду, что каждый из них иногда говорит правду, то он солгал. Следовательно, B — шпион. Тогда C — рыцарь, и C говорит правду. Этот вариант подходит. Но мы должны проверить все возможные варианты.

Предположим, что A — шпион. Тогда C точно лжет, потому что B тоже не может быть шпионом. Значит, C — лжец, потому что у нас уже есть шпион. Тогда B — рыцарь. Но C никогда не говорит правду, значит, B солгал, следовательно, он не рыцарь. Противоречие.

Таким образом, у нас есть единственный ответ: A — лжец, B — шпион, C — рыцарь.

Иногда выбор вопроса остается за нами.

Пример:

Перед вами две двери. Одна ведет к предложению работы мечты, а за другой — Лунная дверь. Перед каждой дверью стоит страж. Один всегда говорит правду. Другой всегда лжет. Вы можете задать один вопрос, чтобы определить, какая дверь правильная (вы не любите летать!). Какой вопрос вы зададите?

Решение:

Чтобы определить, какая дверь ведет к предложению работы, вы можете задать любому из стражей следующий вопрос:

«Если бы я спросил другого стража, какая дверь ведет к работе, на какую дверь он бы указал?»

Почему же?

Если вы зададите правдивому стражу этот вопрос, он честно скажет вам, что сказал бы лживый страж. Так как лжец указал бы на неправильную дверь, правдивый страж тоже укажет на неправильную дверь.

Если вы зададите этот вопрос лживому стражу, он солжет о том, что сказал бы правдивый страж. Так как правдивый страж указал бы на правильную дверь, лжец укажет на неправильную.

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

Третья черепашка

Мы уже использовали идею «Предположим... Получаем противоречие» в предыдущем разделе. Этот подход требует умения правильно строить отрицание, чему мы уже учились ранее.

Название этого метода («Доказательство от противного») говорит само за себя. Это частный случай метода, известного как «reductio ad absurdum» (с латинского), или «доведение до абсурда».

Если нам нужно доказать какое-то утверждение A, мы предполагаем, что оно ложно, то есть, что истинен его отрицание. После этого необходимо прийти к противоречию, что будет означать, что наше предположение было неверным, и задача решена.

Этот метод доказательства основывается на законе двойного отрицания в классической логике. Закон двойного отрицания — это принцип, лежащий в основе классической логики, согласно которому «если неверно, что не A, то A истинно». Этот принцип также называется законом устранения двойного отрицания.

Мы часто сталкиваемся с рассуждениями на основе доказательства от противного в повседневной жизни. Допустим, в какой-то момент вы не захотели идти на ежегодное рабочее мероприятие и притворились больным. Вы сказали врачу, что у вас болит горло. Он посмотрел на ваше горло и сказал: «Если бы оно действительно болело, оно было бы красным. Оно не красное, значит, не болит». Окей, этот пример не идеален, так как врачи предполагают, что взрослые люди не будут лгать по такому глупому поводу, но, надеюсь, вы поняли, о чем я.

Этот принцип может быть очень полезным при решении математических задач, потому что он позволяет установить истинность утверждения, показав, что его отрицание приводит к противоречию.

Один классический пример связан с жестоким королем, который хотел казнить своего министра, не вызывая негодования у народа. Он объявил, что, будучи добрым королем, простит министра или доверится их древним богам. Он написал «смерть» и «жизнь» на двух одинаково выглядящих клочках бумаги, и министр должен был выбрать один. В зависимости от написанного на нем, решалась его судьба. Министр, будучи мудрым, понял, что на обоих бумажках было написано «смерть», но он сумел выжить, проглотив выбранную бумажку. Чтобы определить его судьбу, люди посмотрели на оставшуюся бумажку, где было написано «смерть». Это доказало, что ему посчастливилось выбрать бумажку с надписью «жизнь».

\includegraphics\includegraphics[width=150pt]{}\includegraphics

Пример: Целые точки на прямой окрашены в красный и синий цвета. Докажите, что существует отрезок, у которого оба конца и середина окрашены в один цвет.

Решение: Предположим противное, то есть предположим, что такого отрезка не существует. Рассмотрим все точки с четными координатами, кроме 0. Либо среди них есть точка того же цвета, что и 0, либо они все отличаются от 0 по цвету. Во втором случае мы сразу приходим к противоречию, рассматривая точки 2, 4 и 6. Итак, у нас есть точки того же цвета, что и 0, и 2x, где x принадлежит множеству целых чисел. Тогда -2x, x и 4x должны быть другого цвета. Но x является серединой отрезка с концами -2x и 4x, что приводит к противоречию.

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

Решение: Предположим противное, то есть предположим, что первое условие задачи выполняется, даже если представителей каждой породы не более 14. Назовем животных, представляющих свою породу в одиночку, «одиночками», в отличие от «групп», в которых будет как минимум 2 животных. Так как первое условие задачи должно выполняться, групп не может быть больше 4, иначе можно было бы выбрать группу из 10 животных с 2 представителями каждой породы. С другой стороны, если групп не более 3, то останется как минимум 60 - 3 * 14 = 18 одиночек, и, выбрав 10 одиночек, мы сразу придем к противоречию. Таким образом, групп ровно 4, при этом останется как минимум 60 - 4 * 14 = 4 одиночки, и, выбрав по 2 животных из каждой группы и 2 одиночки, мы приходим к противоречию. Противоречия, полученные при всех возможных распределениях животных, завершают решение задачи.

Задача: Десять друзей отправили друг другу поздравительные открытки, так что каждый отправил 5 открыток. Докажите, что найдутся двое друзей, которые отправили открытки друг другу.

Решение: Предположим противное, то есть таких людей не существует. Это означало бы, что в любой паре людей была отправлена только одна открытка, или вовсе ни одной. Всего существует 10 * 9 * 1/2 = 45 пар, значит, было отправлено не более 45 открыток. Однако в сумме было отправлено ровно 10 * 5 = 50 открыток — противоречие.

Однажды ты спросишь меня, кого я люблю больше — тебя или математику. Я отвечу: «Предположим, что это математика...» И ты уйдешь, так и не узнав, что это было доказательство от противного.

Фаршированные зайцы

Решение задач на принцип Дирихле обычно основывается на методе «доказательство от противного».

Обычно впервые с принципом Дирихле школьники, занимающиеся олимпиадной математикой, сталкиваются в 5 классе. Звучит он следующим образом: «Если в N клетках сидит не менее N+1 кроликов, то в какой-то из клеток сидит не менее двух кроликов». Воспользуемся методом «от противного» — предположим, что «это не так», то есть в каждой клетке сидит менее двух кроликов, то есть 1 или 0. Тогда в N клетках максимально будет сидеть N·1 = N кроликов, что меньше, чем N+1. В большинстве англоязычной литературы этот принцип называется «pigeonhole principle» и формулируется для голубей.

Естественным обобщением можно считать следующее утверждение: «Если в N клетках сидит не менее kN+1 кроликов, то в какой-то из клеток сидит хотя бы k+1 кроликов».

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

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

Решение: Найдём «кроликов» и «клетки». Нетрудно догадаться, что в качестве «кроликов» будут выступать люди, а в качестве «клеток» — количество их знакомств. У любого человека может быть от 0 до n-1 знакомых, где n — количество людей в компании. Значит, клетки будут иметь номера от 0 до n-1. Казалось бы, и «клеток», и «кроликов» — поровну, так что же, принцип Дирихле тут не работает? Работает, но с небольшой модификацией. Заметим, что в клетках 0 и n-1 не могут одновременно сидеть кролики. Действительно, тогда будет человек, который не знаком ни с кем, и человек, который знаком со всеми, чего не может быть. Следовательно, непустых клеток, оказывается, у нас N-1. То есть, принцип Дирихле в данной задаче всё же сработал.

Полученное противоречие завершает решение задачи.

Пример: В таблице 8×8 расставлены целые числа, причём любые два числа в соседних по сторонам клетках отличаются не более, чем на 4. Докажите, что среди этих чисел есть 2 равных.

Решение: Предположим противное. Тогда в таблице нет двух одинаковых чисел — все числа различные. Рассмотрим наименьшее и наибольшее из них — они будут отличаться хотя бы на 63. Но от одного из них можно добраться до другого через соседние клетки за, максимум, k+l ≤ 7+7 = 14 ходов (рисунок ниже).

Так как разница между соседними числами не более, чем 4, то, сделав ≤ 14 ходов, разница будет не более, чем 4·14 = 56. Полученное противоречие завершает доказательство задачи.

Пример: В вашем ящике лежат 3 красных носка, 101 желтый носок и 13 синих носков. Будучи занятым и рассеянным STO компании, вы наугад вытаскиваете несколько носков из ящика и пытаетесь найти подходящую пару. Предполагая, что каждый носок имеет равную вероятность быть выбранным, какое минимальное количество носков вам нужно взять, чтобы гарантировать пару носков одного цвета?

Решение: Когда у вас есть 3 цвета (3 ячейки), согласно принципу Дирихле, вам нужно взять 3+1 = 4 носка (4 объекта), чтобы гарантировать, что хотя бы два носка будут одного цвета (2 объекта попадают в одну ячейку).