“Математика в школе” 2009-3
Обобщение задачи 5026.В нашем распоряжении имеются 32k неотличимых по виду монет, одна из которых фальшивая – она весит чуть легче настоящей. Кроме того, у нас есть трое двухчашечных весов. Известно, что двое весов исправны, а одни – сломаны (показываемый ими исход взвешивания никак не связан с весом положенных на них монет, т. е. может быть как верным, так и искаженным в любую сторону, причем на разных взвешиваниях – искаженным по-разному). При этом неизвестно, какие именно весы исправны, а какие сломаны. Как определить фальшивую монету за 3k + 1 взвешивание?
Прежде всего, необходимо осознать, с какими хитрыми весами мы имеем дело в этой задаче. Если бы сломанные весы показывали неправильный результат взвешивания – задача была бы намного проще. Однако результат взвешивания может быть как неправильным, так и правильным! Иными словами, решить задачу нужно в предположении, что весы хитрят и действуют против нас – так, чтобы не дать нам возможности отыскать фальшивую монету за желаемое число взвешиваний! Позволим ли мы себя запутать? Конечно, нет.
Сначала разберемся с базовым случаем: (k=1). Здесь в нашем распоряжении 9 монет и 4 взвешивания. Покажем, как за первые три взвешивания достичь следующего результата: либо определить фальшивую монету (для краткости – ФМ), либо определить одни заведомо исправные весы и при этом оставить в числе «подозреваемых» только 3 монеты из 9.
Мысленно разложим 9 монет на клетки доски 3x3 и занумеруем их шахматной нотацией (от a1 до c3). Первым взвешиванием кладем монеты на весы №1 – какую-то одну строку на левую чашку, а другую строку – на правую. Второе взвешивание проводим независимо от результатов первого взвешивания на весах №2: какой-то один столбец кладём на левую чашку, а другой – на правую. Эти два взвешивания дадут нам такую информацию: если весы №1 исправны, то мы знаем строку с ФМ, а если исправны весы №2 – мы знаем столбец. Таким образом, если и те, и другие весы исправны, то мы знаем обе координаты ФМ. Без ограничения общности, можно считать, что ФМ находится на клетке a1. Если же исправны только какие-то одни из первых двух весов, то фальшивыми могут оказаться еще четыре монеты – a2, a3, b1 и c1. Именно эти пять монет и остались в списке «подозреваемых». Третье взвешивание мы проводим на весах №3 и действуем при этом так: на одну чашу весов кладём монеты a2 и a3, а на другую – монеты b1 и c1. Если чашки весов уравновесились, это означает, что по мнению весов №3 фальшивыми монетами являются другие пять монет. Но среди них только одна подозреваемая монета – a1! Следовательно, в этом случае мы уже нашли фальшивую монету. Если же одна из чашек оказалась легче, это означает, что монеты с другой чашки, а также монета a1, по мнению весов №3, являются настоящими. Тем самым, результат этого взвешивания противоречит результату одного из первых двух взвешиваний – того, в котором именно этот ряд (строка или столбец) должен был содержать фальшивую монету по мнению каких-то из первых двух весов. Раз двое весов противоречат друг другу, то какие-то из них точно сломаны, а оставшиеся весы – заведомо исправные. Следовательно, после трех взвешиваний мы нашли исправные весы, и так как одно взвешивание на них уже было сделано, то число подозреваемых монет сократилось с 9 до 3. Поставленная цель достигнута, и последним взвешиванием на этих весах мы легко отыщем ФМ.
Теперь воспользуемся математической индукцией для решения задачи для произвольного k. База индукции нами уже доказана. Переход. Пусть мы уже научились решать задачу для 32k–2 монет за 3k–2 взвешивания. Покажем, как решить задачу для 32k монет. Разложим их, аналогично тому, как мы это делали выше, на клетки доски 3x3, по 32k–2 монеты на каждую клетку. Будем считать каждую группу монет, лежающую на одной клетке доски, «обобщенной монетой». Проделаем с обобщенными монетами три точно таких же взвешивания, как описано выше. В результате мы получим либо одну обобщенную ФМ, либо 3 обобщённых ФМ + заведомо исправные весы. В первом случае у нас осталось как раз 32k–2 монеты и 3k–2 взвешивания, – то есть можно применить предположение индукции. Во втором – имеется 32k–1 «подозреваемых» монет, и для нахождения одной фальшивой из них на исправных весах нам достаточно проделать 2k–1 взвешивание. Так как
, то и в этом случае цель достигнута, ч. и т. д.
Является ли наше решение оптимальным? Иначе говоря, верно ли, что для определения ФМ из 3m монет действительно необходимо порядка 1.5m взвешиваний? Оказывается, нет:
Сколько же взвешиваний на самом деле необходимо? Докажем следующую оценку:
Если за d взвешиваний можно определить ФМ из n монет, то
.
Мы продемонстрируем два разных подхода к доказательству, каждый из которых имеет свои достоинства.
Доказательство 1. Пусть есть алгоритм, позволяющий найти ФМ за d взвешиваний. Результаты взвешиваний, проведенных по этом алгоритму (т.е. <, = или >), мы записываем в строчку. В итоге получилась строка из d знаков. При этом по каждой такой строчке мы умеем восстановить, какие именно взвешивания мы делали (ибо по первым i результатам алгоритм определяет, какое именно взвешивание делается на следующем (i+1)-м шаге, а значит, каждой такой строчке однозначно соответствует ФМ. Теперь выясним, сколько различных строчек соответствует одной и той же ФМ. Их хотя бы 2d+1: действительно, есть как минимум такие строчки: 0) в которой все ответы весов правильны; 1) две строки, в которых ровно первый ответ неверен (для неверного ответа есть 2 варианта); 2) две строки, в которых только второй ответ неверен;…; d) две строки, в которых ровно d-й ответ неверен. Ясно, что строка 0) отличается от всех остальных; остальные же строки i) и j) при i<j отличаются друг от друга хотя бы в i-м разряде. Таким образом, строк должно быть не меньше, чем n(2d+1). Однако общее число строк длины d на трехсимвольном алфавите равно 3d, что и доказывает нашу оценку..
Замечание. Из этого доказательства видно, как должен быть устроен алгоритм, если мы хотим его сделать близким к этой оценке. Оценка будет точной, если (почти) все строчки будут возможны и если вранье каких-либо весов мы сможем распознать раньше, чем проведем на них следующее взвешивание. (Если мы этого не сделаем, то количество строк, соответствующих одной ФМ, увеличится, поскольку появятся строки, в которых неверными являются несколько разных ответов.)
Доказательство 2. При каждом взвешивании мы делим монеты на три кучи, и очередные весы выбирают в качестве фальшивой какую-то одну кучу и отказывают двум остальным. Пусть некоторые взвешивания уже проделаны. Монеты, которые всегда оказывались в фальшивой группе при взвешивании на i-х весах, назовем фальшивыми с точки зрения этих весов. Тогда в каждый момент все монеты делятся на следующие группы. А) монеты, фальшивые с точки зрения всех весов («подозреваемые»). Б) монеты, фальшивые с точки зрения всех весов, кроме i-х (такие монеты мы назовём отказниками i-го типа,.они могут оказаться фальшивыми, только если i-е весы сломаны). В) Монеты, которые хотя бы двое весов помещали в группу настоящих (а так как сломанные весы только одни, то эти монеты являются заведомо настоящими). Пусть у нас имеется алгоритм, позволяющий найти ФМ из n монет за d взвешиваний. Можно считать, что он всегда заканчивает свою работу ровно через d шагов (если это случается раньше, просто сделаем еще несколько произвольных взвешиваний, не обращая внимания на их результаты).
Введем понятие значимости монеты в некоторый момент алгоритма. Если осталось m шагов до конца алгоритма (то есть сделано d–m взвешиваний), то будем говорить, что значимость любой подозреваемой монеты равна 2m+1, а значимость любого отказника – 1 (значимость заведомо настоящей монеты равна 0). Что происходит со значимостью подозреваемой монеты после взвешивания? Если это взвешивание оставило монету подозреваемой (это происходит в одном из трех исходов), то ее значимость уменьшилась на 2. Если же в результате взвешивания монета стала отказником (в двух из трех исходов), ее новая значимость стала равна 1. Аналогично для монеты-отказника, тип которого не совпадает с номером весов, на которых проводится взвешивание: в одном из трех случаев она остается отказником и сохраняет значимость 1, в двух других случаях оказывается настоящей и получает значимость 0. И только если тип отказника равен номеру текущих весов, то во всех трех исходах его значимость будет равна 1. Таким образом, суммарная значимость всех монет в результате всех трех исходов данного взвешивания не уменьшается. Если сумма значимостей монет до взвешивания была равна x, то при одном из исходов она станет не меньше, чем x/3. Предположим, что при каждом взвешивании и получается именно такой исход. В начале алгоритма суммарная значимость была равна (2d+1)n (все монеты подозрительны), а в конце она должна стать равной 1, так как после d шагов значимость любой монеты равна 1. Значит,, что и требовалось доказать.
Замечание.Это доказательство тоже немало говорит о том, как должен выглядеть оптимальный алгоритм. А именно, суммарная значимость должна каждый раз уменьшаться втрое. Фактически, это соображение дает рецепт построения оптимального алгоритма. Что может нам помешать каждый раз уменьшать значимость ровно в 3 раза? Во-первых, использование весов того типа, в котором есть отказники (значимость этих отказников не делится на три). Значит, мы должны строить процесс так, чтобы такой ситуации не возникало. Во-вторых, в каждом конкретном взвешивании суммарные значимости ситуаций, к которым ведут три различных возможных исхода, должны быть равными. Для того, чтобы это обеспечить, нам может понадобиться использовать во взвешиваниях и некоторые заведомо настоящие монеты. Ну так что ж – начиная с третьего шага, они у нас уже есть в достаточном количестве (4/9 от общего числа монет).
Прежде всего, необходимо осознать, с какими хитрыми весами мы имеем дело в этой задаче. Если бы сломанные весы показывали неправильный результат взвешивания – задача была бы намного проще. Однако результат взвешивания может быть как неправильным, так и правильным! Иными словами, решить задачу нужно в предположении, что весы хитрят и действуют против нас – так, чтобы не дать нам возможности отыскать фальшивую монету за желаемое число взвешиваний! Позволим ли мы себя запутать? Конечно, нет.
Сначала разберемся с базовым случаем: (k=1). Здесь в нашем распоряжении 9 монет и 4 взвешивания. Покажем, как за первые три взвешивания достичь следующего результата: либо определить фальшивую монету (для краткости – ФМ), либо определить одни заведомо исправные весы и при этом оставить в числе «подозреваемых» только 3 монеты из 9.
Мысленно разложим 9 монет на клетки доски 3x3 и занумеруем их шахматной нотацией (от a1 до c3). Первым взвешиванием кладем монеты на весы №1 – какую-то одну строку на левую чашку, а другую строку – на правую. Второе взвешивание проводим независимо от результатов первого взвешивания на весах №2: какой-то один столбец кладём на левую чашку, а другой – на правую. Эти два взвешивания дадут нам такую информацию: если весы №1 исправны, то мы знаем строку с ФМ, а если исправны весы №2 – мы знаем столбец. Таким образом, если и те, и другие весы исправны, то мы знаем обе координаты ФМ. Без ограничения общности, можно считать, что ФМ находится на клетке a1. Если же исправны только какие-то одни из первых двух весов, то фальшивыми могут оказаться еще четыре монеты – a2, a3, b1 и c1. Именно эти пять монет и остались в списке «подозреваемых». Третье взвешивание мы проводим на весах №3 и действуем при этом так: на одну чашу весов кладём монеты a2 и a3, а на другую – монеты b1 и c1. Если чашки весов уравновесились, это означает, что по мнению весов №3 фальшивыми монетами являются другие пять монет. Но среди них только одна подозреваемая монета – a1! Следовательно, в этом случае мы уже нашли фальшивую монету. Если же одна из чашек оказалась легче, это означает, что монеты с другой чашки, а также монета a1, по мнению весов №3, являются настоящими. Тем самым, результат этого взвешивания противоречит результату одного из первых двух взвешиваний – того, в котором именно этот ряд (строка или столбец) должен был содержать фальшивую монету по мнению каких-то из первых двух весов. Раз двое весов противоречат друг другу, то какие-то из них точно сломаны, а оставшиеся весы – заведомо исправные. Следовательно, после трех взвешиваний мы нашли исправные весы, и так как одно взвешивание на них уже было сделано, то число подозреваемых монет сократилось с 9 до 3. Поставленная цель достигнута, и последним взвешиванием на этих весах мы легко отыщем ФМ.
Теперь воспользуемся математической индукцией для решения задачи для произвольного k. База индукции нами уже доказана. Переход. Пусть мы уже научились решать задачу для 32k–2 монет за 3k–2 взвешивания. Покажем, как решить задачу для 32k монет. Разложим их, аналогично тому, как мы это делали выше, на клетки доски 3x3, по 32k–2 монеты на каждую клетку. Будем считать каждую группу монет, лежающую на одной клетке доски, «обобщенной монетой». Проделаем с обобщенными монетами три точно таких же взвешивания, как описано выше. В результате мы получим либо одну обобщенную ФМ, либо 3 обобщённых ФМ + заведомо исправные весы. В первом случае у нас осталось как раз 32k–2 монеты и 3k–2 взвешивания, – то есть можно применить предположение индукции. Во втором – имеется 32k–1 «подозреваемых» монет, и для нахождения одной фальшивой из них на исправных весах нам достаточно проделать 2k–1 взвешивание. Так как
, то и в этом случае цель достигнута, ч. и т. д.Является ли наше решение оптимальным? Иначе говоря, верно ли, что для определения ФМ из 3m монет действительно необходимо порядка 1.5m взвешиваний? Оказывается, нет:
Сколько же взвешиваний на самом деле необходимо? Докажем следующую оценку:
Если за d взвешиваний можно определить ФМ из n монет, то
. Мы продемонстрируем два разных подхода к доказательству, каждый из которых имеет свои достоинства.
Доказательство 1. Пусть есть алгоритм, позволяющий найти ФМ за d взвешиваний. Результаты взвешиваний, проведенных по этом алгоритму (т.е. <, = или >), мы записываем в строчку. В итоге получилась строка из d знаков. При этом по каждой такой строчке мы умеем восстановить, какие именно взвешивания мы делали (ибо по первым i результатам алгоритм определяет, какое именно взвешивание делается на следующем (i+1)-м шаге, а значит, каждой такой строчке однозначно соответствует ФМ. Теперь выясним, сколько различных строчек соответствует одной и той же ФМ. Их хотя бы 2d+1: действительно, есть как минимум такие строчки: 0) в которой все ответы весов правильны; 1) две строки, в которых ровно первый ответ неверен (для неверного ответа есть 2 варианта); 2) две строки, в которых только второй ответ неверен;…; d) две строки, в которых ровно d-й ответ неверен. Ясно, что строка 0) отличается от всех остальных; остальные же строки i) и j) при i<j отличаются друг от друга хотя бы в i-м разряде. Таким образом, строк должно быть не меньше, чем n(2d+1). Однако общее число строк длины d на трехсимвольном алфавите равно 3d, что и доказывает нашу оценку..
Замечание. Из этого доказательства видно, как должен быть устроен алгоритм, если мы хотим его сделать близким к этой оценке. Оценка будет точной, если (почти) все строчки будут возможны и если вранье каких-либо весов мы сможем распознать раньше, чем проведем на них следующее взвешивание. (Если мы этого не сделаем, то количество строк, соответствующих одной ФМ, увеличится, поскольку появятся строки, в которых неверными являются несколько разных ответов.)
Доказательство 2. При каждом взвешивании мы делим монеты на три кучи, и очередные весы выбирают в качестве фальшивой какую-то одну кучу и отказывают двум остальным. Пусть некоторые взвешивания уже проделаны. Монеты, которые всегда оказывались в фальшивой группе при взвешивании на i-х весах, назовем фальшивыми с точки зрения этих весов. Тогда в каждый момент все монеты делятся на следующие группы. А) монеты, фальшивые с точки зрения всех весов («подозреваемые»). Б) монеты, фальшивые с точки зрения всех весов, кроме i-х (такие монеты мы назовём отказниками i-го типа,.они могут оказаться фальшивыми, только если i-е весы сломаны). В) Монеты, которые хотя бы двое весов помещали в группу настоящих (а так как сломанные весы только одни, то эти монеты являются заведомо настоящими). Пусть у нас имеется алгоритм, позволяющий найти ФМ из n монет за d взвешиваний. Можно считать, что он всегда заканчивает свою работу ровно через d шагов (если это случается раньше, просто сделаем еще несколько произвольных взвешиваний, не обращая внимания на их результаты).
Введем понятие значимости монеты в некоторый момент алгоритма. Если осталось m шагов до конца алгоритма (то есть сделано d–m взвешиваний), то будем говорить, что значимость любой подозреваемой монеты равна 2m+1, а значимость любого отказника – 1 (значимость заведомо настоящей монеты равна 0). Что происходит со значимостью подозреваемой монеты после взвешивания? Если это взвешивание оставило монету подозреваемой (это происходит в одном из трех исходов), то ее значимость уменьшилась на 2. Если же в результате взвешивания монета стала отказником (в двух из трех исходов), ее новая значимость стала равна 1. Аналогично для монеты-отказника, тип которого не совпадает с номером весов, на которых проводится взвешивание: в одном из трех случаев она остается отказником и сохраняет значимость 1, в двух других случаях оказывается настоящей и получает значимость 0. И только если тип отказника равен номеру текущих весов, то во всех трех исходах его значимость будет равна 1. Таким образом, суммарная значимость всех монет в результате всех трех исходов данного взвешивания не уменьшается. Если сумма значимостей монет до взвешивания была равна x, то при одном из исходов она станет не меньше, чем x/3. Предположим, что при каждом взвешивании и получается именно такой исход. В начале алгоритма суммарная значимость была равна (2d+1)n (все монеты подозрительны), а в конце она должна стать равной 1, так как после d шагов значимость любой монеты равна 1. Значит,
, что и требовалось доказать.Замечание.Это доказательство тоже немало говорит о том, как должен выглядеть оптимальный алгоритм. А именно, суммарная значимость должна каждый раз уменьшаться втрое. Фактически, это соображение дает рецепт построения оптимального алгоритма. Что может нам помешать каждый раз уменьшать значимость ровно в 3 раза? Во-первых, использование весов того типа, в котором есть отказники (значимость этих отказников не делится на три). Значит, мы должны строить процесс так, чтобы такой ситуации не возникало. Во-вторых, в каждом конкретном взвешивании суммарные значимости ситуаций, к которым ведут три различных возможных исхода, должны быть равными. Для того, чтобы это обеспечить, нам может понадобиться использовать во взвешиваниях и некоторые заведомо настоящие монеты. Ну так что ж – начиная с третьего шага, они у нас уже есть в достаточном количестве (4/9 от общего числа монет).
Упражнения и задачи.
- Придумайте алгоритм, позволяющий найти ФМ из 3n(n+1) монет за (n+1)2 взвешиваний.
- Как найти ФМ из n=310 монет за d=13 взвешиваний (здесь достигнута точная оценка, поскольку 2d+1=33)?
- Докажите, что любым числом весов, среди которых есть двое сломанных, за d=11 взвешиваний нельзя найти фальшивую монету из n>36 монет.
- Обобщите оценку, полученную в задаче 3, на произвольное натуральное d.
Эта статья выложена ее автором в блоге "Мои любимые головоломки".(http://blog.kknop.com)
Другая публикация - https://docs.google.com/document/d/1ba72GYKarHmdvZgaggD49341-f_QTc41SLhcEoALt34/edit?hl=ru
Комментариев нет:
Отправить комментарий