Текстовые задачи на конструктивы в комбе → .06 Взвешивания и количество информации

Сначала подставим число, состоящее из всех единиц, чтобы узнать их количество в

Далее будем рассматривать пятерку чисел, о которой мы будем знать количество единиц в ней, подставив число, состоящее из 5 двоек на позициях рассматриваемой пятерки. Далее в нашей пятерке зафиксируем число на произвольной позиции, относительно которого будем рассматривать пары чисел, подставляя на их позиции число 2. Таким образом, проведя 3 таких операции, мы определим число единиц в каждой такой паре. Значит, если в какой-то паре мы получили ответ, что в ней 0 или 2 единицы, то их позиции определяются однозначно. Зная, какая цифра находится на фиксированной позиции, мы однозначно определяем позиции остальных чисел. Если на все три пары мы получили ответ, что в них находится одна единица, то у нас возможны 2 варианта: либо на фиксированной позиции стоит цифра 2, а в остальных 1, либо наоборот, на фиксированной позиции стоит цифра 1. Зная количество единиц в этой пятерке, мы можем однозначно определить, какой из этих случаев выполняется.

Разбив число на 20 таких пятерок, получим, что мы определяем его за ход, но зная общее количество единиц в числе и число единиц в каждой из 19 пятерок, мы можем определить количество единиц в последней пятерке, не тратя на это ход. Следовательно, узнав характеристики 80 чисел можно однозначно определить число

Разобьем ленту на участков из числа и останется последние клетки. Стратегия будет повторяться отдельно для каждого участка.

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

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

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

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

Заметим, что достаточно найти несколько монет общей массой г, так как они уравновесят оставшиеся монеты. Возьмем любые пять монет и обозначим их буквами А, Б, В, Г, Д. Первыми двумя действиями взвесим пары А и Б, В и Г.

Если в обоих взвешиваниях весы показали неравенство, то монеты г и г найдены, их сумма составляет г.

Если в обоих взвешиваниях весы показали равенство, то монеты А, Б, В, Г все весят по  г. Третьим действием поставим А и Б на одну чашу, а Д — на другую. Так мы поймем массу монеты Д и при любой её массе среди известных масс набирается г.

Если в одном взвешивании было равенство, а в другом — неравенство, пусть А = Б и В > Г. Тогда монеты А и Б весят по  г, а В — или  г. Взвесив В с А и Б вместе, определим массу монеты В. Если В весит  г, то Г весит  г. Тогда монеты А, Б, В, Г имеют общую массу  г. Если В весит  г, то монеты А, Б и В имеют общую массу  г.

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

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

Предъявим конкретное взвешивание: на первую чашу весов кладём пять самых лёгких гирь, на вторую три самые тяжёлые. Действительно, если утверждение “любые пять камней вместе тяжелее любых трех” верно, то весы очевидно покажут перевес на первой чаше. Если же утверждение неверно, то есть можно выбрать пятёрку камней и тройку камней, что суммарный вес пятёрки не больше веса тройки. А поскольку суммарный вес любых пяти камней как минимум вес пяти самых лёгких, а суммарный вес любых трёх камней не больше веса трёх самых лёгких, весы гарантированно покажут не перевес первой чаши. Соответственно мы различим исходы и сделаем верный вывод.

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

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

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

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

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

Приведём также пример, что одну из карт угадать всегда получится. Разобьем первым действием карты на стопки по Нам укажут на одну из этих стопок. карт выбранной стопки разобьем на стопки по остальные — как угодно. Нам снова укажут на одну из стопок, значит, загаданная карта — одна из четырёх. Эти карты снова разбиваем на четыре стопки, теперь по одной, остальные как угодно. Нам укажут на одну из стопок, а значит и на одну из этих четырёх карт, и мы однозначно определим, какая карта загадана.

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

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

Каждый раз весы показывают либо равенство, либо что первая чаша легче, либо что вторая чаша легче, а значит за два взвешивания мы получим максимум различных последовательностей ответов. Возможных вариантов, когда три рядом лежащие монеты фальшивые, — 20. Если мы сделали всего два взвешивания, то не получится однозначного соответствия возможных исходов и последовательностей ответов, значит, за 2 гарантированно определить фальшивые монеты не получится.

За три взвешивания— возможно.

Лемма: За взвешивание можно найти три фальшивые среди пяти подряд идущих монет. Доказательство: Пусть монеты Взвесим и Если весы показали равенство, то фальшивые Если тяжелее ( тяжелее аналогично), то фальшивые Таким образом, лемма доказана.

Пронумеруем монеты от до Первое взвешивание: монеты на первой чаше, а на второй.

Если весы показали равенство, то значит среди и монет нет фальшивых. Вторым действием: на первой чаше, а на второй. Равенства в таком случае быть не может. Одна чаша тяжелее, там и находятся все три фальшивые монеты. Наша задача за действие найти среди пяти подряд идущих монет три фальшивые, мы это умеем по лемме.

Если весы показали, что тяжелее ( тяжелее аналогично), то значит среди находятся все три фальшивые монеты. Вторым действием: взвесим и Если весы показали равенство — фальшивая тройка полностью содержится среди умеем находить за 1 действие по лемме. Если тяжелее, то все три фальшивые монеты находятся среди умеем находить за действие по лемме. Если тяжелее, то все три фальшивые монеты находятся среди умеем находить за действие по лемме.

Каждую гирю мы можем либо взять, либо нет.

Используя гирь, мы можем различить максимум весов, что меньше чем

Теперь возьмём гири Любое число можно единственным образом разложить в сумму различных степеней двоек (двоичная система счисления). А значит, любое число граммов от до можно получить с помощью данных гирь.

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

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

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

За семь взвешиваний — возможно. Пусть у нас есть гири Первым действием сравниваем и можем считать что Вторым действием сравниваем и можем считать что Третьим действием сравниваем и можем считать что Тогда мы поняли, что давайте еще за два действия упорядочим гири сначала сравним и а потом и (если ) или и (если ). Допустим гири как-то упорядочились где — это в некотором порядке Заметим, что мы знаем что и тогда Давайте за два действия определим место сначала сравним и а потом и (если ) или и (если ).

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

За — возможно.

Сбросим с этажа: если разбился ,то поочередно проверяем с до — на это нам хватит одного ореха и бросков.

Если не разбился на этаже, то бросаем с этажа: если разбился ,то поочередно проверяем с до — на это нам хватит одного ореха и бросков;

Если не разбился на этаже, то бросаем с этажа: если разбился ,то поочередно проверяем с до — на это нам хватит одного ореха и бросков;

Если не разбился на этаже, то бросаем с этажа: если разбился ,то поочередно проверяем с до — на это нам хватит одного ореха и бросков;

Если же орех не разбился с этажа, то значит он бьется при больших высотах, чем нам дано.

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

Пусть у нас не более весов. Попросим все сломанные весы действовать так, как будто вторая монета фальшивая, а остальные равны, тогда как на самом деле фальшивой является первая. Тогда никогда не удастся выяснить, то ли все сломанные — сломаны (и фальшивая — первая), то ли наоборот (и фальшивая — вторая).

Предположим противное — пусть существует алгоритм, позволяющий найти фальшивую монету из монет за ходов.

Любой алгоритм можно закодировать в виде дерева, которое строится следующим образом. На первом уровне находится одна вершина-корень, соответствующая первому взвешиванию. Из нее исходит три ребра на второй уровень, соответствующие различным результатам этого взвешивания: и Аналогично выстраиваются и последующие уровни: на уровне с номером находится вершин. На каждой указано, какое взвешивание в ней совершается, и из каждой вершины исходит по ребра на уровень соответствующие всевозможным результатам этого взвешивания.

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

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

Которые соответствуют случаю, когда все взвешиваний были сделаны правильно. Ясно, что такой лист только один;

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

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

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

Покажем, что Петя сможет определить вес одной гири, даже если у него 8000 гирь. Положим

______________________________________________________________________________________________________________________________________________________

Лемма. Для любых гирь Петя может найти две гири, для которых он знает их суммарный вес.

Доказательство. Пусть Петя положит в прибор по очереди все возможные наборы из 10 гирь из наших Заметим, что каждое показание прибора — это вес какой-то из пар гирь (будем говорить, что это показание использует эту пару). В то же время, Петя получит показаний. Значит, одна из пар будет использована хотя бы

раз.

Иначе говоря, найдутся измерений таких, что (1) в них прибор показывает один и тот же вес и (2) во всех десятках, использованных в этих испытаниях, есть две общих гири и Мы покажем, что при выполнении условий (1) и (2) суммарный вес и обязательно равен то есть вес этой пары Петя и сможет определить по показаниям прибора. Назовём десятки, использованные в этих измерениях, нужными.

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

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

Во всех остальных нужных десятках хорошая пара содержит либо либо Если есть хорошая пара, содержащая то для получения нужной десятки, содержащей эту пару, её надо дополнить гирей и ещё семью гирами из оставшихся Итого, таких нужных десяток не больше Аналогично, нужных десяток, содержащих хорошую пару с гирей тоже не больше

Итого, получаем

Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Завершим решение задачи. Построим следующий граф. Сопоставим каждой гире вершину. Среди каждых гирь найдём одну пару с известной суммой; две соответствующих вершины соединим ребром. Если в этом графе нет нечётных циклов, то, как известно, его вершины можно раскрасить в два цвета так, чтобы каждое ребро соединяло вершины разных цветов. Но тогда вершины одного цвета не меньше и потому среди них мы провели ребро; противоречие.

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

он узнает вес гири

Докажем оценку

______________________________________________________________________________________________________________________________________________________

Пусть существует стратегия, позволяющая ошибаться не более чем в битах т.е. Тогда заметим, что Наблюдатель, знающий стратегию Фокусника, сообщенное Ассистентом слово, и набор бит, в которых ошибся Фокусник, может восстановить написанное Зрителем слово. В самом деле, Наблюдатель берет слово, которое должен был написать Фокусник, и меняет его в тех местах, где Фокусник ошибся. Значит, количество различных пар вида "слово сообщенное Ассистентом и набор мест, в которых фокусник ошибся"не меньше, чем различных слов, которые мог написать зритель. То есть

Перепишем в виде

Заметим, что при неравенство неверно:

_________________________________________________________________________________________________________________________________________________________________________________

Теперь попробуем показать, из каких соображений строится пример. Для начала напомним конструкцию, известную как математикам так и программистам: двоичный код длины 15, позволяющий передать 11 бит полезной информации и исправить ошибку не более чем в одном бите (также известен как 15-битный код Хэмминга). Построим его.

Для начала заметим, что есть ровно 11 слов длины 4 из нулей и единиц, содержащих хотя бы две единицы (всего слов минус одно из одних нулей, минус четыре с одной единицей). Припишем такие слова номерам от 1 до 11 как угодно, например как в таблице:

Теперь построим код таким образом: в первые 11 бит запишем те биты, которые хотим передать (первые 11 позиций будем называть информационными). В последние 4 бита запишем следующие контрольные суммы. В 12-й запишем сумму по модулю два тех из первых 11 бит, приписанное 4-значное число которых имеет 1 в первом разряде, то есть биты № 3,5,6,8,9,10,11. В 13-й — сумму тех из первых 11 бит, приписанное 4-значное число которых имеет 1 во втором разряде, в 14-й сумму бит, имеющих 1 в третьем разряде приписанного слова, в 15-й — в четвертом. Покажем, почему этот код позволяет исправить одну ошибку при передаче.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть Получатель получил кодовое слово, возможно искаженное в одном бите. Получатель точно так же по первым 11 битам посчитает 4 контрольные суммы, и сравнит их с четырьмя полученными. Если совпали все четыре — то слово дошло без искажений. В самом деле, если бы исказился контрольный бит — в нем было бы расхождение, а если информационный — то расхождения были бы во всех контрольных, в которые он входит. Аналогично, если расхождение есть ровно в одном контрольном бите, то исказился именно он. В самом деле, если исказился другой контрольный — то все информационные дошли правильно, тогда в этом контрольном расхождения бы не было; а если исказился информационный, то все контрольные дошли правильно, и тогда расхождения были бы во всех контрольных, в которые входит искаженный информационный, а таких контрольных хотя бы два (именно за этим мы приписывали комбинации нулей и единиц, содержащие хотя бы две единицы). По аналогичным соображениям если получатель видит не менее двух расхождений с контрольными битами, то искажен точно информационный. Тогда достаточно из 11 информационных позиций выбрать ту, в приписанном 4-битном слове которой единицы стоят ровно на тех местах, на которых есть расхождения с контрольными суммами — это и есть искаженная позиция.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь подумаем в других терминах, что же мы построили. У нас есть код из кодовых слов. Каждое из этих слов можно исказить 16 способами (ничего не менять, или изменить один из 15 бит). Все полученных в результате слов будут разными. В самом деле, если бы какое-то слово получалось двумя разными способами: искажением кодового слова и искажением кодового слова (в обоих случаях — не более чем в одном бите), то код бы не исправлял одну ошибку — Получатель может получить слово но в этом случае не может понять, посылали ему или Итак, все слов разные, но это означает что вообще любое из слов длины 15 получается искажением какого-то из кодовых слов не более чем в одном бите.

На этом и построим стратегию Фокусника и Ассистента. Ассистент видит написанное зрителем 60-битное слово, режет его на четыре 15-битных слова Как доказано выше, для них найдутся кодовые слова такие что отличается от не более чем в одном символе. Тогда Ассистент выбрасывает из каждого кодового слова контрольные символы, получает четыре слова длины 11, то есть одно слово длины 44. Его он и передает Фокуснику. Фокусник восстанавливает контрольные суммы, получает слово отличающееся от исходного максимум в четырех битах — победа.

Пусть масса -го камня равна Разобьём камни на пары и в каждой паре сравним их: Далее за взвешивания среди камней находим самый тяжёлый (пусть это ) по схеме: взвешиваем два из них, легкий заменяем на ещё не взвешенный камень. Аналогичным образом, за взвешивания среди камней найдём самый лёгкий (пусть это ).

Нетрудно понять, что — самый тяжёлый среди всех камней, а — самый лёгкий. Не умаляя общности, при нахождении самого легкого камня из мы получили что поэтому достаточно сравнить и чтобы найти самый лёгкий камень из (пусть это ).

Ясно, что легче всех камней от до и тяжелее Сравним с Если То — второй самый лёгкий камень после В противном случае таким камнем является (пусть ). Осталось убедиться в том, что Из этого неравенства следуют все другие неравенства между одним и двумя камнями, так как при любых

Пусть Архимед сначала положит в прибор четыре самых тяжёлых слитка. Их суммарный вес — кг, и прибор сработает. Других четвёрок слитков общим весом кг у Архимеда нет. Значит, он показал Гиерону, какие четыре слитка — самые тяжёлые. Затем он положит в прибор слитков весами кг и кг. Прибор снова сработает. Поскольку, как легко видеть, других девяток слитков общим весом кг у Архимеда нет, он показал Гиерону, каков набор из восьми самых лёгких слитков и слитка весом кг. При этом оба раза в прибор клали ровно один слиток в кг, а ни разу не клали ровно один слиток в кг. Поэтому Архимеду достаточно было написать веса на слитках в и кг.