Задача 79367
|
|
 |
Условие
На химической конференции присутствовало k учёных химиков и алхимиков, причём химиков было больше, чем алхимиков. Известно, что на любой вопрос химики всегда отвечают правду, а алхимики иногда говорят правду, а иногда лгут. Оказавшийся на конференции математик про каждого учёного хочет установить, химик тот или алхимик. Для этого он любому учёному может задать вопрос: ``Кем является такой-то: химиком или алхимиком?'' (В частности, может спросить, кем является сам этот учёный.) Доказать, что математик может установить это за: а) 4k вопросов; б) 2k - 2 вопросов.Решение
Приводимое решение дает возможность выяснить, кто — химик, а кто — алхимик, даже за меньшее, чем 2k - 2, число вопросов, а именно — за q = 3m вопросов, если k = 2m + 1 — число нечётное, и за 3m - 2 вопросов, если k = 2m — число чётное.Вначале мы рассмотрим нечётные k. Искомый способ мы определим индукцией по m. Если на конференции присутствовал k = 1 учёный (m = 0), то он, очевидно, химик, поскольку химиков должно быть больше; никаких вопросов в этом случае задавать не надо: q = 0 = 3 . 0. Предположим теперь, что для всех нечётных чисел, меньших данного числа k = 2m + 1, мы уже имеем способ, позволяющий решить задачу в требуемое число вопросов. Укажем такой способ для числа k = 2m + 1. Перенумеруем для удобства всех участников конференции произвольным образом и начнем спрашивать второго, третьего и т. д. учёных, кто есть первый учёный. Этот опрос мы прекратим, как только произойдёт одно из двух событий:
Событие A. Среди опрошенных учёных большинство высказалось за то, что первыйучёный — алхимик.
Событие B. Число учёных, утверждающих, что первый учёный — химик, равно m.
Ясно, что если произошло событие A и к этому моменту t учёных утверждали, что первый учёный — химик, и f — что он алхимик, то f = t + 1. (Действительно, f > t, а если предположить, что f ≥ t + 2, то событие A должно произойти хотя бы на один вопрос раньше.) Ясно, кроме того, что при этом опросе было задано q1 = f + t = 2f − 1 вопросов. (Частным случаем события A является ситуация, когда уже второй учёный сказал, что первый является алхимиком — здесь t = 0, f = 1.)
Если же произошло событие B и при этом f учёных утверждали, что первый учёный — алхимик, то общее число заданных вопросов равно q1 = m + f.
Нетрудно видеть, что опрос прервётся до того, как будут опрошены все учёные, присутствующие на конференции. В самом деле, предположим противное. Значит, перед опросом последнего учёного не произошло ни одно из событий A, B. Пусть в этот момент среди опрошенных учёных t человек высказались за то, что первый учёный — химик и f — за то, что он алхимик. Поскольку не произошло события A, f ≤ t. Поскольку не произошло события В, t ≤ m − 1. Поэтому общее число опрошенных f + t ≤ 2(m − 1). Добавив к ним первого и последнего учёных, мы получаем, что общее число участников конференции не превосходит 2m, тогда как их 2m + 1. Полученное противоречие доказывает, что одно из событий — A или B — произойдёт до того, как будет опрошен последний учёный.
Пусть произошло событие A. Тогда мы утверждаем, что в группе учёных, состоящей из первого учёного и всех опрошенных учёных, число алхимиков не меньше числа химиков. Действительно, если первый учёный — химик, то те f учёных, которые утверждали, что он алхимик, — сами алхимики. Поскольку общее число учёных в рассматриваемой группе есть 1 + t + f = 2f, число алхимиков в группе в этом случае не меньше числа химиков. Если же первый учёный — алхимик, то алхимиками являются и те t учёных, которые утверждали, что он химик. Поэтому и в этом случае число алхимиков не меньше 1 + t = f, то есть не меньше половины. Далее, поскольку общее число химиков превосходит по условию задачи общее число алхимиков, в оставшейся группе из k − 2f = 2(m − f ) + 1 учёных число химиков также должно превосходить число алхимиков. Число k − 2f, очевидно, меньше k, поэтому по предположению индукции существует способ, позволяющий за q2 = 3(m − f ) вопросов выяснить, кто в оставшейся группе учёных есть химик и кто — алхимик. Выберем теперь из этой группы произвольного химика (такой, очевидно, найдётся) и спросим его (на это уйдёт q3 = 1 вопрос), кто есть первый учёный. Если он алхимик, то те t учёных, которые утверждали, что он химик, — алхимики. Поэтому нам остаётся лишь выяснить у выбранного нами химика, "кто есть кто" среди тех f учёных, которые утверждали, что первый учёный — алхимик (на это уйдёт ещё q4 = f вопросов). В результате мы восстановим полную картину разбиения участников конференции на химиков и алхимиков и истратим на это q = q1 + q2 + q3 + q4 = 2f − 1 + 3(m − f) + 1 + f = 3m вопросов, что и требовалось.
Если же первый учёный оказался химиком, то те f учёных, которые утверждали, что он алхимик, сами являются алхимиками. Поэтому нам остаётся выяснить у выбранного нами химика лишь "кто есть кто" в группе из t учёных, утверждавших, что первый учёный — химик. На это мы затратим q4 = t вопросов. Общее число вопросов q = q1 + q2 + q3 + q4 = 2f − 1 + 3(m − f )+ 1 + t = 3m − 1 в этом случае даже меньше того числа вопросов которое мы вправе использовать. Тем самым случай, когда произошло событие A, полностью разобран.
Рассмотрим теперь тот случай, когда произошло событие B. Мы утверждаем, что в этом случае первый учёный — химик. В самом деле, если бы он был алхимиком, то и те m учёных, которые утверждали, что он химик, тоже были алхимиками и общее число алхимиков было бы не меньше m + 1, то есть больше половины, а это противоречит условию задачи. Итак, первый учёный — химик, а те f учёных, которые утверждали, что он алхимик, сами — алхимики. Выясним теперь у первого учёного "кто есть кто" среди тех m учёных, которые утверждали, что он химик (на это уйдёт q2 = m вопросов), и "кто есть кто" среди остальных учёных, не участвовавших в опросе (на это уйдёт ещё q3 = k − (1 + m + f) = 2m + 1 − 1 − m − f = m − f вопросов). Таким образом, мы полностью выясним "кто есть кто" на конференции и затратим на это q = q1 + q2 + q3 = m + f + + m + m - f = 3m вопросов. Тем самым оба случая — и когда происходит событие A, и когда происходит событие B — рассмотрены, и поэтому для нечётного числа участников задача полностью решена.
Пусть теперь k=2m – четное число. Удалим одного участника. По доказанному, за 3m-1 вопрос мы узнаем "кто есть кто". С помощью еще одного вопроса, заданного химику, мы узнаем, кем является последний участник.
(Решение из статьи XXX "О людях правдивых, лгунах и обманщиках", Квант 1980 номер 11 с.8-11.)
