Тема Текстовые задачи на конструктивы в комбе

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

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела текстовые задачи на конструктивы в комбе
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#90367

Есть 100  камней, выложенных в порядке возрастания весов. За какое наименьшее число взвешиваний на чашечных весах без гирь можно проверить или опровергнуть утверждение: “Любые пять камней вместе тяжелее любых трех”?

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

Показать ответ и решение

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

Ответ:

одно взвешивание

Ошибка.
Попробуйте повторить позже

Задача 2#93235

В одиннадцатом классе учится 30  школьников. В их учебный план включены 15  дисциплин. Для каждой дисциплины можно выбрать 5  сильнейших школьников — тех, которые наиболее хорошо разбираются в ней. Всегда ли можно рассадить всех школьников по двум аудиториям так, чтобы в каждой аудитории сидел хотя бы один школьник из каждой пятёрки сильнейших?

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Всего 2*2²⁵ способов. Сколько способов рассадить школьников по двум аудиториям так, чтобы существовала дисциплина пятерка сильнейших по одному которому сидела в одной из аудиторий?

Подсказка

Всего 15*2²⁶. Покажите, что это число меньше, чем общее количество способов рассадки школьников по двум аудиториям и завершите доказательство.

Показать ответ и решение

Всего способов рассадить школьников по двум разным аудиториям 230  (каждого из 30  школьников можно посадить в одну из двух аудиторий). Способов рассадить школьников по аудиториям, при которых по конкретному предмету в какой-то из аудиторий нет сильнейших   25   26
2⋅2 = 2 ,  ведь можно двумя способами выбрать аудиторию, в которой не будет сильнейших по предмету, а остальных в любую из двух. Тогда способов рассадки, при которых в одной из аудиторий нет сильнейших хотя бы по одному из предметов не более     26
15⋅2 .  Отметим, что     26      26  30
15⋅2  <16⋅2  = 2 ,  а значит, в каком-то из способов не нашлось аудитории, в которой нет сильнейших ни по одному предмету.

Ответ:

Да, всегда

Ошибка.
Попробуйте повторить позже

Задача 3#74051

Есть несколько карт. Зритель загадывает одну из них. Фокусник раскладывает все карты на 4  стопки и узнает у зрителя, в какой стопке оказалась задуманная карта. При каком наибольшем количестве карт можно наверняка определить задуманную карту за 3  вопроса?

Показать ответ и решение

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

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

Ответ:

 43 = 64  карты

Ошибка.
Попробуйте повторить позже

Задача 4#74052

Имеется 5  с виду одинаковых шаров, два из которых радиоактивны. Дозиметром можно проверить, есть ли хотя бы один радиоактивный шар в произвольной группе. За какое наименьшее число проверок можно выявить оба радиоактивных шара?

Показать ответ и решение

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

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

Ответ:

 4  проверки

Ошибка.
Попробуйте повторить позже

Задача 5#74053

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

Показать ответ и решение

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

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

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

Пронумеруем монеты от 1  до 20.  Первое взвешивание: 1− 5  монеты на первой чаше, а 11− 15  на второй.

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

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

Ответ:

 3  взвешивания

Ошибка.
Попробуйте повторить позже

Задача 6#74054

Каким наименьшим числом гирь можно набрать все веса 1  г, 2  г, 3  г, ...,127  г?

Показать ответ и решение

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

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

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

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 7#74055

Имеется 6  с виду одинаковых шаров, два из которых радиоактивны. Дозиметром можно проверить на радиоактивность любую группу шаров. За какое наименьшее число проверок можно выявить оба радиоактивных шара?

Показать ответ и решение

Пусть возможно определить радиоактивные шары за 4  проверки. Тогда рассмотрим каким может быть первое взвешивание: Если мы взяли один шар и дозиметр не пропищал, то осталось  2
C5 = 10  возможных исходов (2  радиоактивных среди 5  ). Если мы взяли два шара и дозиметр пропищал, то осталось 9  возможных исходов (1,  если оба выбранных радиоактивны; 8,  если один из них). Если мы взяли три шара или больше и дозиметр пропищал, то возможных исходов еще больше чем 9.  Таким образом за 3  оставшихся проверки мы можем получить максимум  3
2 = 8  различных последовательностей ответов. Если мы сделали всего четыре проверки, то после первого хода (на наше взвешивание дозиметр может пропищать или нет, но в любом случае есть результат, который не запрещает хотя бы 9  исходов) не получится однозначного соответствия возможных исходов и последовательностей ответов, значит, за 4  проверки гарантированно определить радиоактивные шары не получится.

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

Ответ:

 5  проверок

Ошибка.
Попробуйте повторить позже

Задача 8#74056

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

Показать ответ и решение

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

За семь взвешиваний — возможно. Пусть у нас есть гири a,b,c,d,e.  Первым действием сравниваем a  и b,  можем считать что a <b.  Вторым действием сравниваем c  и d,  можем считать что c< d.  Третьим действием сравниваем b  и d,  можем считать что b< d.  Тогда мы поняли, что a <b< d,  давайте еще за два действия упорядочим гири a,b,d,e:  сначала сравним b  и e,  а потом e  и a  (если e< b  ) или e  и d  (если b< e  ). Допустим гири как-то упорядочились x <y <z <t,  где x,y,z,t  — это в некотором порядке a,b,d,e.  Заметим, что мы знаем что c< d  и d≤ t,  тогда c< t.  Давайте за два действия определим место c :  сначала сравним c  и y,  а потом c  и x  (если c< y  ) или c  и z  (если y <c  ).

Ответ:

 7  взвешиваний

Ошибка.
Попробуйте повторить позже

Задача 9#74057

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

Показать ответ и решение

Каждый раз у Пети орех либо бьется, либо нет, но среди всех наших бросков не может быть больше двух разбившихся орехов, значит, за 19  бросков мы получим максимум  2   1    0
C19 +C19+ C19 = 191  различных последовательностей ответов. Возможных вариантов этажа, начиная с которого бьется орех — 201.  Если мы сделали всего 19  бросков, то не получится однозначного соответствия возможных исходов и последовательностей ответов, значит, гарантированно определить этаж не получится.

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

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

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

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

...

Если не разбился на 20+ 19+...+6  этаже, то бросаем с 20+19+ ...+ 6+ 5= 200  этажа: если разбился ,то поочередно проверяем с 20+ 19+...+6+ 1  до 20+19+ ...+ 6+ 5  — на это нам хватит одного ореха и 4  бросков;

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

Ответ:

 20  бросков

Ошибка.
Попробуйте повторить позже

Задача 10#74658

При каком наименьшем n  среди n  весов, из которых ровно k  сломанных, можно из 10  монет определить одну фальшивую (количество взвешиваний не ограничено)?

Показать ответ и решение

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

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

Ответ:

 2k+ 1

Ошибка.
Попробуйте повторить позже

Задача 11#74661

Докажите, что любым числом весов, среди которых есть двое сломанных, нельзя найти фальшивую монету (более легкую) из n> 36  монет за 11  взвешиваний.

Показать доказательство

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

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

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

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

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

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

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

Итак, если монета A  фальшивая, то в дереве алгоритма должно быть хотя бы 1+22+ 220= 35  листьев, которые на нее указывают. Перестановкой монет можно добиться, чтобы фальшивая монета имела любой номер от 1  до n,  поэтому листьев должно быть хотя бы 35⋅n.  С другой стороны, известно, что листьев ровно 311,  откуда следует неравенство 35⋅n ≤311  и n≤ 36.  Это противоречит условию задачи, по которому n> 36,  значит предположение о противном в начале решения было не верным.

Ошибка.
Попробуйте повторить позже

Задача 12#74783

Фокусник и его Ассистент готовятся показать следующий фокус. Фокуснику завяжут глаза, после чего один из зрителей напишет на доске 60-битное слово (последовательность из 60 нулей и единиц). Ассистент уверен, что сможет незаметно сообщить фокуснику 44 бита (не обязательно написанные в слове, можно вычислять любые функции). После чего Фокусник должен будет назвать слово. Для какого наибольшего числа C  Фокусник и Ассистент могут придумать стратегию, позволяющую всегда назвать слово, совпавшее хотя бы в C  битах с написанным зрителем?

Источники: Высшая проба - 2022, 11.6 (см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

Давайте начнём решать эту задачу с оценки. Причём мы будем рассуждать так, что фокусник при выписывании последовательности ошибся максимум в k символах, то есть C = 60 - k. Пусть мы знаем последовательность, написанную фокусником. Тогда с помощью какой информации на основе введённых данных мы сможем определить исходную последовательность?

Подсказка 2

Верно, нам нужно знать, в каких символах он ошибся. Тогда мы сможем однозначно определить последовательность. Но как нам это поможет в задаче? Давайте представим немного нашу задачу через множество и его покрытие. Всего возможных последовательностей, которые может написать зритель это 2^60. Давайте подумаем, как мы можем посчитать, сколько покроет одна последовательность, учитывая, что фокусник может ошибиться максимум в k знаках?

Подсказка 3

Верно, это считается с помощью числа сочетаний. Может быть такое, что он вовсе не ошибся, ошибся один раз и т.д. до максимум в k знаках. И того, для одной последовательности мы получаем сумму числа сочетаний. Но всего фокусник может получить 2^44 различных последовательностей, имея информацию от ассистента. Тогда учитывая мысль про покрытия множества размером 2^60, какую оценку мы получаем?

Подсказка 4

Да, сумма, умноженная на 2^44, должна быть больше 2^60. Но зачем? Чтобы даже, если мы ошибёмся максимум в k знаках, то мы всё равно победим, так как затронем все последовательности. Таким образом, несложной прикидкой получим оценку для k=4, откуда C=56. Теперь в следующей подсказке разберёмся с примером.

Подсказка 5

Суть нашего примера будет заключаться в том, как же действовать ассистенту, то есть какую последовательность передавать, и, что с ней делать фокуснику. Заметим, что фокусник в итоге ошибается только в 4 позициях. Давайте тогда для удобства, пока магически разобьём то, что будет передавать ассистент на блоки по 11 цифр. Тогда в каждом блоке фокусник будет что-то досчитывать, записывать и, в итоге, ошибаться максимум 1 раз в блоке. Попробуйте поугадывать, какая информация ему может понадобиться из этих 11 цифр? Стоит подумать в сторону информатики, последовательности 0 и 1 из 4 знаков и чётности, нечётности.

Подсказка 6

Давайте составим табличку из последовательностей с четырьмя символами, в которых есть хотя бы две единицы, и пронумеруем. Их будет как раз 11 штук. В последние 4 позиции блока запишем следующие "контрольные" суммы. Сначала запишем сумму по модулю два тех из первых 11 позиций, записанное 4-значное число которых имеет 1 в первом разряде. Потом аналогичное сделаем для 1 во втором разряде и т.д. до 4 разряда. Попробуем взять произвольную последовательность из 15 символов, а записать только 11. Посчитаем для них самостоятельно контрольные суммы. Теперь поизучайте эту конструкцию, например, что будет если контрольные суммы не совпадут? В скольких разрядах у них будет расхождение и где может быть ошибка – в четырех контрольных суммах или в первых 11 цифрах? А сколько в принципе может случится ошибок в такой строке, если не совпали контрольные суммы?

Подсказка 7

Ага, несложным перебором, где и сколько штук можно было допустить ошибок, понимаем, что она возможна только одна(либо в 11 цифрах, либо в контрольных суммах). Но для чего это всё таки было? Попробуйте прокрутить теперь эту конструкцию в обратном порядке. Пусть мы получили "кодовое слово" длины 15. Дальше считаем контрольные суммы по первым 11 цифрам и дописываем их. Таким образом, 15 цифр будут расходится максимум в 1 позиции. Как тогда отсюда получается окончательный пример?

Подсказка 8

Да, получается, что ассистент бьёт 60 цифр на группы по 15 и делает для них "кодовые слова" длинной 11, убирая контрольные суммы. Так и получается всего передача 44 знаков. Фокусник же далее восстанавливает контрольные суммы, как и само слово, ошибившись максимум 4 раза. Но всё таки осталось ещё понять, почему же вообще любое из слов длины 15 получается искажением какого-то из кодовых слов не более чем в одной позиции. И после этого будет победа!

Показать ответ и решение

Докажем оценку C ≤ 56.

______________________________________________________________________________________________________________________________________________________

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

   (               )
244 C060+C160+ ...+ Ck60 ≥ 260

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

(                )
 C060+ C160+ ...+ Ck60  ≥216

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

216 > 64000

 0    1    2   3         602  603
C60+ C60+C 60+ C60 < 1+ 60 + 2 + 6 = 1+ 60+ 1800+ 36000

_________________________________________________________________________________________________________________________________________________________________________________

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

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

PIC

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

_________________________________________________________________________________________________________________________________________________________________________________

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

На этом и построим стратегию Фокусника и Ассистента. Ассистент видит написанное зрителем 60-битное слово, режет его на четыре 15-битных слова w1,w2,w3,w4.  Как доказано выше, для них найдутся кодовые слова u1,u2,u3,u4,  такие что wi  отличается от ui  не более чем в одном символе. Тогда Ассистент выбрасывает из каждого кодового слова контрольные символы, получает четыре слова длины 11, то есть одно слово длины 44. Его он и передает Фокуснику. Фокусник восстанавливает контрольные суммы, получает слово u1u2u3u4,  отличающееся от исходного максимум в четырех битах — победа.

Ответ: 56

Ошибка.
Попробуйте повторить позже

Задача 13#88722

У геолога есть чашечные весы без гирь и 8  камней. Он хочет знать, верно ли, что два камня всегда тяжелее одного. Как ему гарантированно проверить это за 13  взвешиваний?

Показать доказательство

Пусть масса i  -го камня равна a.
 i  Разобьём камни на пары и в каждой паре сравним их: a ≥a ,a ≥a ,a ≥ a,a ≥ a.
1   2  3  4  5  6  7   8  Далее за  3  взвешивания среди камней a1,a3,a5,a7  находим самый тяжёлый (пусть это a1  ) по схеме: взвешиваем два из них, легкий заменяем на ещё не взвешенный камень. Аналогичным образом, за 3  взвешивания среди камней a2,a4,a6,a8  найдём самый лёгкий (пусть это a8  ).

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

Ясно, что a6  легче всех камней от a1  до a5  и тяжелее a8.  Сравним a6  с a7.  Если a6 ≤ a7.  То a6  — второй самый лёгкий камень после a8.  В противном случае таким камнем является a7  (пусть a6 ≤ a7  ). Осталось убедиться в том, что a1 < a8+ a6.  Из этого неравенства следуют все другие неравенства между одним и двумя камнями, так как ai ≤ a1 <a8+ a6 ≤ aj +ak  при любых i,j,k.

Ошибка.
Попробуйте повторить позже

Задача 14#74663

(a) Даны n  монет попарно различных масс и n  чашечных весов, n > 2.  При каждом взвешивании разрешается выбрать какие-то одни весы, положить на их чаши по одной монете, посмотреть на показания весов и затем снять монеты обратно. Какие-то одни из весов (неизвестно, какие) испорчены и могут выдавать случайным образом как правильный, так и неправильный результат. За какое наименьшее количество взвешиваний можно заведомо найти самую тяжелую монету?

(b) То же, но на весы можно класть сколько угодно монет.

Источники: Всеросс., 2019, ЗЭ, 11.3(см. olympiads.mccme.ru)

Показать ответ и решение

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Ответ:

(a) 2n − 1  (b) 2n− 1

Ошибка.
Попробуйте повторить позже

Задача 15#96043

Имеется по 144  монеты двух типов (всего 288  монет), внешне неразличимых между собой. Можно ли за три взвешивания на чашечных весах без гирь проверить, весят ли монеты разных типов одинаково?

Источники: Лига открытий - 2018

Показать ответ и решение

Разобьем монеты на пять равных по количеству групп A,B, C,D  и E  и останется еще три монеты. Взвесим A  с B,A  с C  и A+ B  с D + E.  Если хотя бы в одном из взвешиваний наступило неравенство, то монеты разных типов весят по-разному. Пусть в A  ровно k  монет первого типа. Тогда всего монет первого типа от 5k  до 5k+ 3,  но число 144  не представляется в таком виде.

Ответ:

Можно

Ошибка.
Попробуйте повторить позже

Задача 16#96055

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

Источники: Лига открытий - 2018

Показать доказательство

Пронумеруем монеты числами 1,2,3,...,10,  и положим на проверку монеты 1,2,3,4  и 5.  Будем без ограничения общности считать, что среди них больше настоящих, иначе настоящих больше среди монет 6,7,8,9  и 10,  и монеты можно перенумеровать. Заменим монету   1  на 6  и снова проверим их. Далее оставляем 6  -ю монету и последовательно меняем 2  на 7,  потом 3  на 8,  и, наконец, 4  на 9.  Заметим, что если бы мы поменяли 5  на 10,  то фальшивых точно бы стало больше. Будем мысленно считать что это замену мы тоже произвели. Тогда прибор в некоторый момент стал показывать, что фальшивых монет больше; пусть первый раз это произошло при замене монеты    x  на x +5.  Тогда монета с номером x  обязательно настоящая, ведь только убрав настоящую монету мы могли увеличить количество фальшивых.

Ошибка.
Попробуйте повторить позже

Задача 17#96332

У Лены было 100  внешне одинаковых колец с массами 1  г, 2  г, 3  г, .., 100  г, но она потеряла половину. Сможет ли она гарантированно определить массу хотя бы одного из колец, используя только двухчашечные весы без гирь?

Источники: Лига открытий - 2018

Показать ответ и решение

Рассмотрим два набора 1,2,3,...,50  и 2,4,6,...,100.  Заметим, что эти два набора неразличимы на двухчашечных весах.

Ответ:

Нет, не может

Ошибка.
Попробуйте повторить позже

Задача 18#99836

Имеется по 10  монет двух типов (всего 20  монет), внешне неразличимых между собой. Можно ли за два взвешивания на чашечных весах без гирь проверить, весят ли монеты разных типов одинаково?

Источники: Лига открытий - 2018

Показать ответ и решение

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

Ответ:

Можно

Ошибка.
Попробуйте повторить позже

Задача 19#99957

У Лены было 100  внешне одинаковых колец с массами 1  г, 2  г, 3  г, ..., 100  г, но одно она потеряла. Как только с помощью чашечных весов без гирь узнать вес потерянного кольца? Взвешивания можно проводить сколько угодно раз.

Источники: Лига открытий - 2018

Показать доказательство

Во-первых, кольца можно упорядочить по возрастанию веса. Далее, для двух пар соседних колец с весами a< b  и c <d  мы можем проверить равенство a+ d= b+ c.  Если равенство соблюдается, то ни между a  и b,  ни между c  и d  убранных колец нет. Значит, мы сможем найти одну единственную разницу между соседними кольцами, отличающуюся от остальных, либо такой разницы не будет. Если мы нашли такую разность, то легко вычислим вес потерянного кольца. Если не нашли, то потеряно либо кольцо массой 1,  либо кольцо массой 100.  Для трех самых легких колец x < y < z  тогда проверим равенство x+ y = z.  Если оно выполнено, то потеряно 100,  если нет, то потеряно 1.

Ошибка.
Попробуйте повторить позже

Задача 20#93512

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

Источники: Лига открытий - 2017

Показать доказательство

Пронумеруем монеты от 1 до 10. Взвесим тройки (1,2,3)  и (4,5,6).  Пусть (1,2,3)= (4,5,6).  Тогда монеты 1− 6  обычные. Взвесим   7  и 8  монеты. Если они равны, то волшебная монета 9  или 10,  и взвесив 1  с 9  мы найдем ее. Если 7> 8,  то одна из них волшебная, и сравнив 1  и 7  мы определим волшебную монету.

Пусть (1,2,3)> (4,5,6),  случай (1,2,3)< (4,5,6)  разбирается аналогично. Монеты 7− 10  тогда обычные. Взвесим (1,2,3)  и (7,8,9).  Из результата этого взвешивая можно понять в какой тройке ((1,2,3)  или (4,5,6)  ) волшебная монета и в каком она состоянии. Пусть волшебная монета в (1,2,3).  Взвесим 1  и 2.  Если они равны, то 3  монета волшебная, иначе, зная состояние волшебной монеты, мы определим, какая из 1  и 2  монеты волшебная. Аналогично, если волшебная монеты была в тройке (4,5,6).

Рулетка
Вы можете получить скидку в рулетке!