Взвешивания и количество информации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Теперь попробуем показать, из каких соображений строится пример. Для начала напомним конструкцию, известную как математикам так и программистам: двоичный код длины 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. Его он и передает Фокуснику. Фокусник восстанавливает контрольные суммы, получает слово отличающееся от исходного максимум в четырех битах — победа.

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

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

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

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

(a) Докажем сначала, что за взвешивание можно найти самую тяжёлую монету. Более точно, мы докажем по индукции по что самую тяжёлую из данных монет можно определить за взвешивание, имея трое весов, одни из которых, возможно, испорчены.

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

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

Оба раза перевешивала одна и та же из двух монет; назовём её монетой а вторую из них — монетой Так как хотя бы одни из двух весов правильные, то монета действительно тяжелее монеты Значит, не самая тяжёлая. Задача сводится к тому, чтобы определить самую тяжёлую из монеты: монеты и монет, не участвовавших в первых двух взвешиваниях. По предположению индукции мы можем сделать это за взвешивания. Вместе с первыми двумя взвешиваниями получаем взвешивания.

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

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

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

(A) Монеты упорядочены по возрастанию масс и все весы (в том числе, испорченные) показывали правильные результаты во всех взвешиваниях.

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

Рассмотрим два случая:

В последнем, м взвешивании, не участвует монета с номером Предположим, что опять перевесила монета с большим номером. Тогда каждая из ситуаций (А) и (Б) по-прежнему возможна.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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