О людях правдивых, лгунах и обманщиках

8

О людях
правивых,
лгунах
и обманшиках

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

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

Задача 1*). На развилке двух дорог, одна из которых ведет в город A, две живут правдивые люди, а другой ведет в город B, две живут лгуны, математик встретил житель одного из этих городов. может ли математик за один вопрос выяснить у встреченного им жителя, какая из дорог ведет в город A?

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

*) Задачи 1 и 2 были сообщены автору венгерским математиком П. Майором.

жили слова «да» и «нет». Вопрос, решающий задачу 1, таков: «Ведет ли эта дорога (указывая на одну из дорог) в ваш родной город?». Легко проверить, что ответ «да» означает, что данная дорога ведет в A, ответ «нет» — что в B. В самом деле, если ответающий является жительем города A, то он всегда говорит правду и поэтому его ответ «да» означает, что указанная дорога ведет не в B, то есть в A, а ответ «нет» означает, что эта дорога ведет в его родной город, то есть в B. Таким образом, в общих случаях ответ «да» означает, что данная дорога ведет в A, и ответ «нет» — что в B, что и утверждалось.

Заметим, что мы не определляем при ответе, с тем мы разговариваем — с жительем города A или с жительем города B, но это и не требовалось. Автору известны и другие решения задачи 1, но все они основаны на одной и той же идее: вопрос о том, ведет ли данная дорога в город A, нужно задать в такой форме, чтобы лгуну приходиловать «дважды отрицательный» ответ. Поскольку двойное отрицание эквивалентно положительнымному ответу, лгун в этом случае дает тот же ответ, что и человека, говорящий правду. Это и происходит в приведенном нами решении.

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

Задача 2. Пусть в условиях задачи 1 математик встретил на развилке не одного, а трех человек, один из которых является жительем города A, второй — житель города B, а третий — обманчиком. При этом математик знает, что среди этих трех один — житель города A, другой — житель города B, а третий — обманчик, но конкретно не знает, кто из них есть кто. может ли математик за два вопросы выяснить дорогу в A?

9

Уточним, что каждый из двух вопросов может быть задан любому из трех лиц, встреченных математиком на развилке, и на вопрос ответает только тот, кому этот вопрос задан. Кроме того, каждый из встреченных знает «кто есть кто» среди них и какая дорога ведет в А и какая — в В.

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

Перенумерем для удобства всех трех человек произвольным образом. Вопрос задается первому. Вот он: «Предположим, что каждый из вас трех сейчас отправится в А или в В по следующему принципу: житель города А поедет в город А, житель города B — в город B, а обманчик — если только обманщик не является вы сами — поедет вместе с вам; если же вы — обманчик, то вы поедете куда угодно. Пойдет ли при этих условиях в А вот этот (указывая на второго) человек?».

Мы утверждаем, что при ответе «да» третий человек — не обманщик, а при ответе «нет» второй человек — не обманщик. Действительно, если вопрос мы задали обманщику, то и второй и третий из опрашиваемых не является обманщиком и, стало бы, третий им не является. Наоборот, его ответ «нет» свидетельствует о том, что второй человек является лгуном (ведь только лгун не идет вместе с ним). Если же вопрос мы задали лгуну, то его «да» означает, поскольку обманщик идет в В, а человек, говорящий правду, — в А, что второй человек — обманщик, а третий — человек, говорящий правду. «Нет» же означает, что, наоборот, второй — это человек говорящий правду, а третий — обманщик.

Проанализировав все возможности, нетрудно видеть, что при ответе «да» третий человек, а при ответе «нет» второй человек зависит не являются обманщиками. Таким образом, в обихах случай мы можем указать человека, не являющегося обманщиком, и тем самым задана 2 решена.

Заметим, что, как и при решении задачи 1, основная идея состоит в том, чтобы заставить лгун сделать двойное отрицание, то есть добиться того, чтобы его ответы имели тот же смысл, что и у человека, говорящего правду, и чтобы они при этом различили обманщикка и необманщикков.

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

Решение задачи 3 сравнительно несложно. А именно, спросим у любого ученого (назовем его для определения первым) о каждом из остальных. В результате эти (N—1) ученых будут разбииты на две группы: группы тех, кто по словам первого ученого является химиком, и группы тех, кто по словам первого ученого является алхимиком. Отнесям первого ученого к первой группе. Выберем из этих группы больше. Тогда ученые этой группы — химики, ученые другой группы — алхимики (доказите!). Тем самым задана решена.

Теперь мы подошли к центральной задаче нашей статьи — задаче M585 («Квант», 1979, № 9). Ее условия совпадает с условиям задачи 3, за тем исключением, что алхимики являются уже не лгунами, а обманщиками. В задаче M585 пред-

10

лагалось выяскить «кто есть кто» на конференции за а) 4N, 6) 2N—2, в) [3N/2] вопросов.

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

Приводимое ниже решение дает возможность выяскить, кто — химик, а кто — алхимик, даже за меньше, чем [3N/2], число вопросов, а именно — за $q=3k$ вопросов, если $N=2k+1$ — число нечетное, и за $q=3(k-1)$ вопросов, если $N=2k$ — число четное.

Вначале мы рассмотрим нечетные $N$. Искомый способ мы определим индукцией по $k$. Если на конференции присутствовал $N=1$ ученный ($k=0$), то он, очень/no, химик, поскольку химиков должно быть больше; никаких вопросов в этом случае задавать не надо: $q=0=3\cdot0$.

Предположим теперь, что для всех нечетных чисел, меньше than $N=2k+1$, мы уже имеем способ, позволяющий решить задачу в требуемое число вопросов. Укажем такой способ для числа $N=2k+1$. Перенумеруем для удобства всех частников конференции произвольным образом и начем спрашивать второго, третього и т. д. ученых, кто есть первый ученный. Этот прос мы прекратим, как только произойдет одно из двух событий:

Собътие А. Среди опрошенных ученых большиство высказалось за то, что первый ученный — алхимик.

Собътие В. Число ученых, утверждалось, что первый ученный — химик, равно $k$.

Ясно, что если произошло событие $A$ и к этому моменту $t$ ученых утверждали, что первый ученный — химик, и $f$ — что он алхимик, то $f=t+1$. (Действительно, $f>t$, а если предположить, что $f\geq 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\leq t$. Поскольку не произошло события $B$, $t\leq k-1$. Поэтому общее число опрошенных $f+t\leq 2(k-1)$. Добавив к ним первого и последнего ученых, мы получаем, что общее число участников конференции не превосходит $2k$, тогда как их $2k+1$. Полученное противоречение доказывает, что одно из событий — $A$ или $B$ — произойдет до того, как будет опрошен последний учены.

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

Действительно, если первый ученный — химик, то те $f$ ученых, которые утверждали, что он алхимик,— сами алхимики. Поскольку общее число ученых в рассматриваемой группе есть $1+t+f=2f$, число алхимков в группе в этом случае не меньше числа химиков. Если же первый ученный — алхимик, то алхимики являются и те $t$ ученых, которые утверждали, что он химик. Позному и в этом случае число алхими-