Среди математических задач на сообразительность особый интерес представляют логические задачи. Такие задачи, как правило, не требуют специальных математических знаний, и их условие может быть объяснено даже людям, весьма далёким от математики.
В настоящей статье мы разберём четыре логические задачи. В этих задачах у нас будут присутствовать люди правдивые, говорящие во всех случаях только правду, и лгуны, всегда говорящие только неправду. Однако наибольшую трудность и наибольший интерес, как мы увидим, будут представлять те задачи, в которых встречаются ещё и обманщики, т. е. люди, говорящие что угодно, только бы запутать спрашивающего.
Задача 1. На развилке двух дорог, одна из которых ведёт в город $A$, где живут правдивые люди, а другая ведёт в город $B$, где живут лгуны, математик встретил жителя одного из этих городов. Может ли математик за один вопрос выяснить у встреченного им жителя, какая из дорог ведёт в город $A$?
Ответ в задаче 1 является положительным даже при дополнительном условии, которого мы всегда будем придерживаться в статье: вопрос должен задаваться в такой форме, чтобы ответом на него служили слова «да» и «нет». Вопрос, решающий задачу 1, таков: «Ведёт ли эта дорога (указывая на одну из дорог) в ваш родной город?». Легко проверить, что ответ «да» означает, что данная дорога ведёт в $A$, ответ «нет» — что в $B$. В самом деле, если отвечающий является жителем города $A$, то он всегда говорит правду, и поэтому его ответ «да» означает, что указанная дорога ведёт в $A$, а ответ «нет» — что в $B$. Если же отвечающий живёт в $B$, то его ответ «да», поскольку этот человек всегда говорит неправду, означает, что указанная дорога ведёт не в $B$, т. е. в $A$, а ответ «нет» означает, что эта дорога ведёт в его родной город, т. е. в $B$. Таким образом, в обоих случаях ответ «да» означает, что данная дорога ведёт в $A$, и ответ «нет» — что в $B$, что и утверждалось.
Заметим, что мы не определяем при ответе, с кем мы разговариваем — с жителем города $A$ или с жителем города $B$, но это и не требовалось. Автору известны и другие решения задачи 1, но все они основаны на одной и той же идее: вопрос о том, ведёт ли данная дорога в город $A$, нужно задать в такой форме, чтобы лгуну приходилось давать «дважды отрицательный» ответ. Поскольку двойное отрицание эквивалентно положительному ответу, лгун в этом случае даёт тот же ответ, что и человек, говорящий правду. Это и происходит в приведённом нами решении.
Вторая задача, которую мы разберём, является усложнением первой. Это усложнение связано с появлением среди отвечающих обманщика.
Задача 2. Пусть в условиях задачи 1 математик встретил на развилке не одного, а трёх человек, один из которых является жителем города $A$, второй — жителем города $B$, а третий — обманщиком. При этом математик знает, что среди этих троих один — житель города $A$, другой — житель города $B$, а третий — обманщик, но конкретно не знает, кто из них есть кто. Может ли математик за два вопроса выяснить дорогу в $A$?
Уточним, что каждый из двух вопросов может быть задан любому из трёх лиц, встреченных математиком на развилке, и на вопрос отвечает только тот, кому этот вопрос задан. Кроме того, каждый из встреченных знает, «кто есть кто» среди них и какая дорога ведёт в $A$ и какая — в $B$.
Решение задачи 1 наталкивает на мысль: а нельзя ли первым вопросом выделить из трёх человек того, который не является обманщиком? Тогда задача 2 будет сведена к задаче 1 и, задав выделенному человеку тот же вопрос, что и в задаче 1, мы узнаем дорогу в $A$. Оказывается, такой первый вопрос задать можно, хотя догадаться до него, как кажется автору, непросто.
Перенумеруем для удобства всех трёх человек произвольным образом. Вопрос задаётся первому. Вот он: «Предположим, что каждый из вас троих сейчас отправится в $A$ или в $B$ по следующему принципу: житель города $A$ пойдёт в город $A$, житель города $B$ — в город $B$, а обманщик — если только обманщиком не являетесь вы сами — пойдёт вместе с вами; если же вы — обманщик, то вы пойдёте куда угодно. Пойдёт ли при этих условиях в $A$ вот этот (указывая на второго) человек?».
Мы утверждаем, что при ответе «да» третий человек — не обманщик, а при ответе «нет» второй человек — не обманщик. Действительно, если вопрос мы задали обманщику, то и второй, и третий из опрашиваемых не являются обманщиками. Далее, если вопрос мы задали человеку, который всегда говорит правду, то его «да» означает, что второй является обманщиком и, стало быть, третий им не является. Наоборот, его ответ «нет» свидетельствует о том, что второй человек является лгуном (ведь только лгун не идёт вместе с ним). Если же вопрос мы задали лгуну, то его «да» означает, что, поскольку обманщик идёт в $B$, а человек, говорящий правду, — в $A$, второй человек — обманщик, а третий — человек, говорящий правду. «Нет» же означает, что, наоборот, второй — это человек, говорящий правду, а третий — обманщик.
Проанализировав все возможности, нетрудно увидеть, что при ответе «да» третий человек, а при ответе «нет» второй человек заведомо не являются обманщиками. Таким образом, в обоих случаях мы можем указать человека, не являющегося обманщиком, и тем самым задача 2 решена.
Заметим, что, как и при решении задачи 1, основная идея состояла в том, чтобы заставить лгуна сделать двойное отрицание, то есть добиться того, чтобы его ответы имели тот же смысл, что и у человека, говорящего правду, и чтобы они при этом различали обманщика и необманщиков.
Задача 3. На химический конгресс приехали $N$ учёных; некоторые из них являются химиками, остальные — алхимиками, причём известно, что химиков больше. Химик на все вопросы отвечает правдиво, а алхимик всегда лжёт. На конгресс попал математик, задавшийся целью установить о всех учёных, кто из них есть химик, а кто — алхимик. Для этого ему разрешается спрашивать любого учёного о любом другом учёном, кто он. Укажите способ, при котором математик может выяснить «кто есть кто» за $N-1$ вопросов.
Решение задачи 3 сравнительно несложно. А именно, спросим у любого учёного (назовём его для определённости первым) о каждом из остальных. В результате эти $N-1$ учёных будут разбиты на две группы: группа тех, кто по словам первого учёного является химиком, и группа тех, кто по словам первого учёного является алхимиком. Отнесём первого учёного к первой группе. Выберем из этих групп бо́льшую. Тогда учёные этой группы — химики, учёные другой группы — алхимики (докажите!). Тем самым задача решена.
Теперь мы подошли к центральной задаче нашей статьи — задаче М585 («Квант», 1979, №9). Её условие совпадает с условием задачи 3, за тем исключением, что алхимики являются уже не лгунами, а обманщиками. В задаче М585 предлагалось выяснить «кто есть кто» на конференции за:
- $4N$ вопросов;
- $2N-2$ вопросов;
- $\left[\dfrac323N\right]$ вопросов.
Эта задача является несравненно более сложной, чем задача 3, и опять это связано с тем, что ответы лгуна хотя и являются неправильными, но они, так сказать, «постоянно неправильны», что позволяет извлекать из них почти столько же информации, что и из правильных ответов правдивого человека. Ответы же обманщика произвольны, и извлечь из них какую-либо информацию — задача гораздо более сложная.
Приводимое ниже решение даёт возможность выяснить, кто — химик, а кто — алхимик, даже за меньшее, чем $\left[\dfrac32N\right]$, число вопросов, а именно — за $q=3k$ вопросов, если $N=2k+1$ — число нечётное, и за $q=3(k-1)$ вопросов, если $N=2k$ — число чётное.
Вначале мы рассмотрим нечётные $N$. Искомый способ мы определим индукцией по $N$. Если на конференции присутствовал $N=1$ учёный ($k=0$), то он, очевидно, химик, поскольку химиков должно быть больше; никаких вопросов в этом случае задавать не надо: $q=0=3\cdot0$.
Предположим теперь, что для всех нечётных чисел, меньших данного числа $N=2k+1$, мы уже имеем способ, позволяющий решить задачу в требуемое число вопросов. Укажем такой способ для числа $N=2k+1$. Перенумеруем для удобства всех участников конференции произвольным образом и начнём спрашивать второго, третьего и т. д. учёных, кто есть первый учёный. Этот опрос мы прекратим, как только произойдёт одно из двух событий:
Событие $A$. Среди опрошенных учёных большинство высказалось за то, что первый учёный — алхимик.
Событие $B$. Число учёных, утверждающих, что первый учёный — химик, равно $k$.
Ясно, что если произошло событие $A$ и к этому моменту $t$ учёных утверждали, что первый учёный — химик, и $f$ — что он алхимик, то $f=t+1$. (Действительно, $f\gt t$, а если предположить, что $f\ge t+2$, то событие $A$ должно произойти хотя бы на один вопрос раньше). Ясно, кроме того, что при этом опросе было задано $q_1=f+t=2f-1$ вопросов (частным случаем события $A$ является ситуация, когда уже второй учёный сказал, что первый является алхимиком — здесь $t=0$, $f=1$).
Если же произошло событие $B$ и при этом $f$ учёных утверждали, что первый учёный — алхимик, то общее число заданных вопросов равно $q_1=k+f$.
Нетрудно видеть, что опрос прервётся до того, как будут опрошены все учёные, присутствующие на конференции. В самом деле, предположим противное. Значит, перед опросом последнего учёного не произошло ни одно из событий $A$, $B$. Пусть в этот момент среди опрошенных учёных $t$ человек высказались за то, что первый учёный — химик, и $f$ — за то, что он алхимик. Поскольку не произошло события $A$, $f\le t$. Поскольку не произошло события $B$, $t\le k-1$. Поэтому общее число опрошенных $f+t\le2(k-1)$. Добавив к ним первого и последнего учёных, мы получаем, что общее число участников конференции не превосходит $2k$, тогда как их $2k+1$. Полученное противоречие доказывает, что одно из событий — $A$ или $B$ — произойдёт до того, как будет опрошен последний учёный.
Пусть произошло событие $A$. Тогда мы утверждаем, что в группе учёных, состоящей из первого учёного и всех опрошенных учёных, число алхимиков не меньше числа химиков.
Действительно, если первый учёный — химик, то те $f$ учёных, которые утверждали, что он алхимик, — сами алхимики. Поскольку общее число учёных в рассматриваемой группе есть $1+t+f=2k$, число алхимиков в группе в этом случае не меньше числа химиков. Если же первый учёный — алхимик, то алхимиками являются и те $t$ учёных, которые утверждали, что он химик. Поэтому и в этом случае число алхимиков не меньше $1+t=f$, т. е. не меньше половины.
Далее, поскольку общее число химиков превосходит по условию задачи общее число алхимиков, в оставшейся группе из $N-2f=2(k-f)+1$ учёных число химиков также должно превосходить число алхимиков. Число $N-2k$, очевидно, меньше $N$, поэтому по предположению индукции существует способ, позволяющий за $q_2=3(k-f)$ вопросов выяснить, кто в оставшейся группе учёных есть химик и кто — алхимик. Выберем теперь из этой группы произвольного химика (такой, очевидно, найдётся) и спросим его (на это уйдёт $q_3=1$ вопрос), кто есть первый учёный.
Если он алхимик, то те $f$ учёных, которые утверждали, что он химик, — алхимики. Поэтому нам остаётся лишь выяснить у выбранного нами химика, «кто есть кто» среди тех $f$ учёных, которые утверждали, что первый учёный — алхимик (на это уйдёт ещё $q_4=f$ вопросов). В результате мы восстановим полную картину разбиения участников конференции на химиков и алхимиков и истратим на это $q=q_1+q_2+q_3+q_4=2f-1+3(k-f)+1+f=3k$ вопросов, что и требовалось.
Если же первый учёный оказался химиком, то те $f$ учёных, которые утверждали, что он алхимик, сами являются алхимиками. Поэтому нам остаётся выяснить у выбранного нами химика лишь «кто есть кто» в группе из $t$ учёных, утверждавших, что первый учёный — химик. На это мы затратим $q_4=f$ вопросов. Общее число вопросов $q=q_1+q_2+q_3+q_4=2f-1+3(k-f)+1+t=3k-1$ в этом случае даже меньше того числа вопросов, которое мы вправе использовать. Тем самым случай, когда произошло событие $A$, полностью разобран.
Рассмотрим теперь тот случай, когда произошло событие $B$. Мы утверждаем, что в этом случае первый учёный — химик.
В самом деле, если бы он был алхимиком, то и те $k$ учёных, которые утверждали, что он химик, тоже были бы алхимиками, и общее число алхимиков было бы не меньше $k+1$, т. е. больше половины, а это противоречит условию задачи.
Итак, первый учёный — химик, а те $f$ учёных, которые утверждали, что он алхимик, сами — алхимики. Выясним теперь у первого учёного «кто есть кто» среди тех $k$ учёных, которые утверждали, что он химик (на это уйдёт $q_2=k$ вопросов), и «кто есть кто» среди остальных учёных, не участвовавших в опросе (на это уйдёт ещё $q_3=N-(1+k+f)=2k+1-1-k-f=k-f$ вопросов). Таким образом, мы полностью выясним «кто есть кто» на конференции и затратим на это $q=q_1+q_2+q_3=k+f+k+k-f=3k$ вопросов. Тем самым оба случая — и когда происходит событие $A$, и когда происходит событие $B$ — рассмотрены, и поэтому для нечётного числа участников задача полностью решена.
Для чётных $N$ решение задачи почти дословно повторяет решение, данное нами для нечётных $N$, и мы оставляем его в качестве упражнения тем, кто хочет глубже понять проведённое рассуждение.
