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

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

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

Решаем задачи

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

Задача 21#124048Максимум баллов за задание: 7

Найдите максимальное целое число $n ≥0,$ для которого верно следующее утверждение: «Существует способ найти (определить) единственную фальшивую монету среди $n$ внешне одинаковых монет, взвешивая монеты на чашечных весах (без числовых делений) не более трех раз и одновременно определить ее относительный вес (то есть легче она или тяжелее настоящих)». (Замечание: предполагается, что все настоящие монеты имеют одинаковый вес, а фальшивая — другой вес, отличный от веса настоящих монет).

Источники: Иннополис - 2020, 11.3 (см. lk-dovuz.innopolis.university)

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

Подсказка 1

Сколько результатов можно получить за 3 взвешивания?

Подсказка 2

За одно взвешивание можно получить 3 результата, поэтому за 3 взвешивания получим 27. Теперь оцените n.

Подсказка 3

Количество вариантов фальшивой монеты и её относительного веса равно 2n, поэтому 2n ≤ 27 ⇒ n ≤ 13.

Подсказка 4

Будем перебирать n сверху. Пусть n = 13. Давайте предположим, что способ определить фальшивую монету существует, тогда либо приведем его, либо получим противоречие.

Подсказка 5

Заметим, что за 2 взвешивание можно получить только 9 результатов. Докажите, что в каждом взвешивании должно участвовать не менее 10 монет.

Подсказка 6

Докажите, что иначе в первом взвешивании участвует не более 8 монет.

Подсказка 7

Рассмотрите ситуации, когда в первом взвешивании участвует 10 монет, и сравните количества результатов с количествами вариантов.

Подсказка 8

Доказали, что n ≠ 13. Пусть n = 12. Попробуйте придумать алгоритм поиска фальшивой монеты. Сколько монет должно участвовать в первом взвешивании?

Подсказка 9

В первом взвешивании должно участвовать 8 монет, разберите ситуации, когда левая чаша тяжелее; правая чаша тяжелее; чаши уравновешены.

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

Сначала заметим, что за три взвешивания на чашечных весах можно получить только 27 результатов $(так как$ за каждое взвешивание на чашечных весах можно получить только 3 результата — левая чашка легче правой, чашки уравновешены, правая чашка $легче левой).$ Но так как количество вариантов фальшивой монеты $(из n)$ и ее относительного веса $(легче или тяжелее)$ равно $2n,$ то должно выполняться неравенство $2n≤ 27.$ Следовательно, $n ≤ 13.$

Пусть $n =13.$

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

Заметим, что так как за одно взвешивание на чашечных весах можно получить только 3 результата $(левая чаш ка$ легче правой, чашки уравновешены, правая чашка $легче левой),$ то за два взвешивания на чашечных весах можно получить только 9 результатов.

Теперь покажем, что в первом взвешивании должно участвовать не менее 10 монет $(∗)$ . Действительно, в противном случае в первом взвешивании участвует не более 8 монет $(число должно$ быть чётным, так как взвешивание происходит на чашечных весах, а на чашки весов надо класть равные $количества монет).$

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

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

В первом взвешивании участвует не менее 10 монет $(∗)$ — не менее 5 на каждой чаше весов. Если в результате первого взвешивания одна чашка $(с не менее,$ чем 5 $монетами),$ оказалась легче, а другая $(тоже с$ не менее, чем 5 $монетами)$ — тяжелее, то у нас возможно не менее 10 вариантов $(фальшивой монеты$ и ее $относительного веса).$ Вновь число результатов за 2 взвешивания будет меньше числа вариантов.

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

Пусть $n =12.$

В описании способа определения фальшивой монеты будем использовать следующие обозначения:

1.: Монеты будем обозначать $(1),(2),...,(14),$ а $гирьку$ — $(15).$
2.: Выражения вида $(p+q)?(r+ s)$ для взвешивания, в котором, в данном случае, пара монет $p$ и $q$ помещены на левую чашку весов, а пара других монет $r$ и $s$ (тоже из монет и гирьки) — на правую.
3.: У взвешивания $(p+ q)?(r +s)$ может быть три исхода: < $(если$ левая чашка $легче),$ = $(если$ чашки $уравновешены )$ и > $(если$ правая чашка $легче).$
4.: $case ((p + q)?(r + s)) of:$ означает «для такого выражения возможны следующие случаи» (и далее — случаи для =, > и <).

Теперь мы можем дать описание алгоритма, который получает 12 монет $(1),...,(12)$ , среди которых ровно одна фальшивая имеет вес, отличный от веса других настоящих монет равного веса, и определяет фальшивую монету и ее относительный вес за три взвешивания на чашечных весах. В круглых скобках находятся пояснения к каждому шагу.
$case ((1)+ ...+(4))?((5)+ ...+ (8)) of:$
(сначала мы кладем на левую чашу монеты с 1 по 4, а на вторую — с 5 по 8, остальные подобные выражения читаются аналогично)
$∙$ $=$ (получили равенство, тогда фальшивая среди $(9)...(12)$ , а все $(1)...(8)$ — настоящие):
$case ((1)+(9))?((10)+ (11)) of:$

$=$ (то есть фальшивая (12)):
$case ((1))?((12)) of:$
$■$ $<$ : фальшивая монета (12) и тяжелее;
$■$ $>$ : фальшивая монета (12) и легче;
$<$ (то есть фальшивая среди (9) и легче или среди (10) и (11) и тяжелее):
$case ((10))?((11)) of:$
$■$ $=$ (возможно только если (9) фальшивая и легче): фальшивая монета (9) и легче;
$■$ $<$ (возможно только если (11) фальшивая и тяжелее): фальшивая монета (11) и тяжелее;
$■$ $>$ (возможно только если (10) фальшивая и тяжелее): фальшивая монета (10) и тяжелее;
$>$ (то есть фальшивая среди (9) и тяжелее или среди (10) и (11) и легче):
$case ((10))?((11)) of:$
- $=$ (возможно только если (9) фальшивая и тяжелее): фальшивая монета (9) и тяжелее;
- $<$ (возможно только если (10) фальшивая и легче): фальшивая монета (10) и легче;
- $>$ (возможно только если (11) фальшивая и легче): фальшивая монета (11) и легче;

$∙$ $<$ (то есть фальшивая среди $(1)...(4)$ и легче, или среди $(5)...(8)$ и тяжелее, а все $(9)...(12)$ — настоящие):
$case ((1)+ (2)+ (5)+(6))?((3)+(9)+ (10)+ (11)) of:$

$=$ (то есть фальшивая среди (4) и легче, или (7) и (8) и тяжелее, а все остальные монеты — настоящие):
$case ((7))?((8)) of:$
$■$ $=$ (возможно только если фальшивая (4) и легче): фальшивая монета (4) и легче;
$■$ $<$ (возможна только если фальшивая (8) и тяжелее): фальшивая монета (8) и тяжелее;
$■$ $>$ (возможна только если фальшивая (7) и тяжелее): фальшивая монета (7) и тяжелее;
$<$ (возможно только если фальшивая среди (1) и (2) и легче):
$case ((1))?((2)) of:$
$■$ $<$ (возможна только если фальшивая (1) и легче): фальшивая монета (1) и легче;
$■$ $>$ (возможна только если фальшивая (2) и легче): фальшивая монета (2) и легче;
$>$ (возможно только если фальшивая среди (5) и (6) и тяжелее):
$case ((5))?((6)) of:$
$■$ $<$ (возможна только если фальшивая (6) и тяжелее): фальшивая монета (6) и тяжелее;
$■$ $>$ (возможна только если фальшивая (5) и тяжелее): фальшивая монета (5) и тяжелее;

$∙$ $>$ (то есть фальшивая среди $(1)...(4)$ и тяжелее, или среди $(5)...(8)$ и легче, а все $(9)...(12)$ — настоящие):
$case ((1)+(2)+(5)+(6))?((3)+ (9)+(10)+(11)) of:$

$=$ (то есть фальшивая среди (4) и тяжелее, или (7) и (8) и легче, а все остальные монеты — настоящие):
$case ((7))?((8)) of:$
$■$ $=$ (возможно только если фальшивая (4) и тяжелее): фальшивая монета (4) и тяжелее;
$■$ $<$ (возможна только если фальшивая (7) и легче): фальшивая монета (7) и легче;
$■$ $>$ (возможна только если фальшивая (8) и легче): фальшивая монета (8) и легче;
$<$ (возможно только если фальшивая среди (3) и тяжелее или (5) и (6) и легче):
$case ((5))?((6)) of:$
$■$ $=$ (возможно только если фальшивая (3) и тяжелее): фальшивая монета (3) и тяжелее;
$■$ $<$ (возможна только если фальшивая (5) и легче): фальшивая монета (5) и легче;
$■$ $>$ (возможна только если фальшивая (6) и легче): фальшивая монета (6) и легче;
$>$ (возможно только если фальшивая среди (1) и (2) и тяжелее):
$case ((1))?((2)) of:$
$■$ $<$ (возможна только если фальшивая (2) и тяжелее): фальшивая монета (2) и тяжелее;
$■$ $>$ (возможна только если фальшивая (1) и тяжелее): фальшивая монета (1) и тяжелее.

Итак, искомое $n= 12.$

Ответ:

$n =12$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 22#74663Максимум баллов за задание: 7

(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$

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

Задача 23#96043Максимум баллов за задание: 7

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

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

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

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

Ответ:

Можно

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

Задача 24#96055Максимум баллов за задание: 7

Имеется $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$ обязательно настоящая, ведь только убрав настоящую монету мы могли увеличить количество фальшивых.

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

Задача 25#96332Максимум баллов за задание: 7

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

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

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

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

Ответ:

Нет, не может

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

Задача 26#99836Максимум баллов за задание: 7

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

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

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

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

Ответ:

Можно

Курсы

Всё необходимое для достижения цели

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

Задача 27#99957Максимум баллов за задание: 7

У Лены было $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.$

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

Задача 28#93512Максимум баллов за задание: 7

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

Источники: Лига открытий - 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).$

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

Задача 29#93531Максимум баллов за задание: 7

На день рождения к Волку пришли семеро козлят и Маша. После того, как Волк отвлекся, он недосчитался $3$ пирожков. У Волка есть вместительные чашечные весы без гирь. Волк знает, что никто из козлят не успел бы съесть все три пирожка сразу. Как Волку за $10$ взвешиваний определить, виновна ли в поедании пирожков Маша? Первоначально все козлята весили одинаково, но Маша может иметь другой вес.

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

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

Назовем козленка легким, если он не съел ни одного пирожка, и тяжелым — в противном случае. Тогда, если найдется три тяжелых козленка, то Маша не виновата. Если найдется два тяжелых козленка, то Маша виновата тогда и только тогда когда они одного веса. И если тяжелых козлят не более одного, то Маша точно виновата. Пронумеруем козлят числами от $1$ до $7.$ Будем взвешивать козлят по двое, выбирая каждый раз более легкого (если они не равны) и любого (если они равны), и взвешивать его с любым еще не взвешенным козленком. Тогда за $6$ взвешиваний мы взвесим каждого хотя бы по разу, и последний выбранный козленок будет легким. Отметим также всех козлят, которые будут ему равны. Также мы определим количество тяжелых козлят и их номера. Если тяжелых козлят не два, то мы сразу получаем ответ. Иначе взвесим двух тяжелых козлят.

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

Задача 30#94169Максимум баллов за задание: 7

У Винни-Пуха есть $5$ горшков с медом весом $1,2,3,4$ и $5$ кг соответственно. На каждом горшке написан его вес. Винни-Пух подозревает, что от одного из горшков кто-то мог украсть часть меда (но может случиться, что все горшки нетронуты). Как ему за два взвешивания на чашечных весах без гирь определить, был ли украден мед и если был, то из какого именно горшка?

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

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

Будем считать, что горшки пронумерованы в соответствии со своим весом. Пусть первым взвешиванием Винни положит на одну чашку горшки $1$ и $2,$ а на другую — горшок $3.$ Возможны следующие варианты. $1)$ Если весы в равновесии, это означает, что все эти горшки нетронуты, так как иначе было бы хотя бы два горшка, из которых брали мед. Тогда вторым взвешиванием он сравнит горшки $1$ и $4$ с горшком $5.$ Если перевесит сторона $1$ и $4,$ то горшок $5$ — искомый. Если перевесит горшок $5,$ то горшок $4$ — искомый. Если весы в равновесии, то все горшки нетронуты. $2)$ Если сторона $1$ и $2$ перевесила, то горшок $3$ — искомый и второе взвешивание не требуется. $3)$ Если горшок $3$ перевесил, то искомый горшок среди $1$ и $2$ и он точно есть. Значит, горшки $4$ и $5$ нетронуты. Снова он сравнит горшки $1$ и $4$ с горшком $5.$ Если весы в равновесии, то горшок $2$ — искомый. Если горшок $5$ перевесил, то горшок $1$ — искомый. Сторона $1$ и $4$ перевесить не может.

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

Задача 31#94324Максимум баллов за задание: 7

Барон Мюнхгаузен разложил $10$ фруктов на чаши весов. Далее он $4$ раза сделал такую операцию: поменял два фрукта с правой чаши с одним фруктом с левой. Барон утверждает, что вначале и после каждой операции весы были в равновесии. Могут ли его слова быть правдой?

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

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

Например, на левой чашке лежали фрукты весом $3,4,5$ и 6 граммов, а на правой $− 1,1,1,1,2$ , и $12$ граммов. Первым ходом он меняет $1$ и $2$ на $3,$ вторым $− 1$ и $3$ на $4,$ третьим $− 1$ и $4$ на $5,$ четвертым $1$ и $5$ на $6.$ После этого справа остаются $6$ и $12,$ а слева — все остальные.

Ответ:

Да, могут

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 32#80498Максимум баллов за задание: 7

Имеется 288 внешне одинаковых монет весами 7 и 8 грамм (есть и те, и другие). На чаши весов положили по 144 монеты так, что весы в равновесии. За одну операцию можно взять с чаш любые две группы из одинакового числа монет и поменять их местами. Докажите, что можно не более, чем за 11 операций сделать так, чтобы весы не были в равновесии.

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

Подсказка 1

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

Подсказка 2

Верно! С самых маленьких. Поменяем местами две монеты (с каждой чаши по одной). Из предположения, они одинаковы. Это уже какая-то определённость. Может сделаем так ещё раз?

Подсказка 3

Действительно, аналогично мы можем найти ещё одну, одинаковую с этими двумя, монету. То есть на одной из чащ уже 2 одинаковых. Менять по одной — никаких 11 операций точно не хватит, нужно увеличивать шаг. Кажется, мы можем сделать подобное с 4 монетами (по 2 с каждой чаши)…

Подсказка 4

Точно! Таким же образом получите, что теперь у вас на одной из чаш уже 3 одинаковые монеты. Потом 5 и т.д. Интересно, на какую известную последовательность намекают эти числа?

Подсказка 5

Это же последовательность Фибоначчи! Невзначай скажем, что F₁₂ = 144, а дальше мы замолкаем. Успехов!

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

Будем менять группы монет с разных чаш. Пусть у нас при каждой из следующих замен равновесие сохраняется. Поменяем по одной монете. Они одинаковы. Поменяем одну из этих монет с новой. Теперь три монеты одинаковы: пара на одной и одна — на другой чаше. Поменяем эту пару с парой еще нетронутых. Теперь на одной чаше пара одинаковых, на другой — тройка таких же монет. Поменяем тройку с тройкой нетронутых. Теперь на одной чаше тройка одинаковых монет, на другой — пять таких же монет. Продолжая в том же духе, после k-го шага получим на одной чаше $Fk$ одинаковых монет, а на другой — $Fk+1$ таких же монет, где $Fi$ — i-ое число Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. Итак, после 11-го шага на одной из чаш все монеты одинаковы. Но тогда они таковы же и на другой, что по условию невозможно.

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

Задача 33#74058Максимум баллов за задание: 7

Глава Монетного двора хочет выпустить монеты $12$ номиналов (каждый — в натуральное число рублей) так, чтобы любую сумму от $1$ до $6543$ рублей можно было заплатить без сдачи, используя не более $8$ монет. Сможет ли он это сделать? (При уплате суммы можно использовать несколько монет одного номинала.)

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

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

Заметим, что $94 =6561> 6543.$ Покажем, что можно выбрать $12$ номиналов так, чтобы с помощью не более чем $8$ монет можно было уплатить без сдачи любую сумму от $1$ до $6560$ рублей.

Покажем сначала, как выпустить монеты трёх номиналов, чтобы с помощью не более чем двух монет можно было уплатить без сдачи любую сумму от $1$ до $8$ рублей. Пусть номиналы равняются $1,3$ и $4$ рублям. Тогда $1= 1,2 =1 +1,3= 3,4 =4$ , $5 =4+ 1,6= 3+3,7= 4+ 3$ и $8 =4 +4.$

Пусть теперь Монетный двор изготовит монеты с номиналами $k k 9,3⋅9$ и $k 4⋅9$ рублей при $k= 0,1,2,3.$ Любое число $N$ от $1$ до $6560$ единственным образом представляется в виде $3 2 N =a3⋅9 + a2⋅9+ a1⋅9+ a0,$ где числа $ak$ могут принимать значения от $0$ до $8.$ (Фактически, это разложение числа $N$ в девятеричной системе счисления.) Как показано выше, сумма $k ak⋅9$ может быть получена не более чем двумя монетами. Таким образом, вся сумма $N$ может быть получена не более чем $4⋅2= 8$ монетами указанных номиналов, что и требовалось.

Ответ:

Да, сможет

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

Задача 34#74662Максимум баллов за задание: 7

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

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

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

Докажем индукцией по $k.$

База. Для удобства занумеруем монеты числами от $0$ до $8$ и запишем их в троичной записи (таким образом, каждой монете сопоставлена пара цифр от $0$ до $2$ ). Первое взвешивание делаем первыми весами в соответствии с первой цифрой номера: на левую чашу кладем монеты, у номера которых первая цифра $0,$ на правую — у которых она $1.$ Второе взвешивание делаем аналогично вторыми весами в соответствии со второй цифрой номера. Знак $<$ указывает на то, что фальшивая монета среди чисел с $0$ на первом/втором месте, $>$ — что она среди чисел с $1$ на первом/втором месте, $=$ — что среди чисел с $2$ на первом/втором месте. После проведения взвешиваний можно перенумеровать числа так, чтобы результат первого взвешивания указывал на число с $0$ на первом месте, а второго — с $0$ на втором. Тогда $4$ монеты без нулей в номере точно не фальшивые (иначе соврали и первые, и вторые весы).

Теперь разобьем монеты на три группы следующим образом: в одну поместим $00,$ в другую $01$ и $02,$ в третью — $10$ и $20;$ дополним все группы до трех монет точно не фальшивыми и взвесим третьими весами. Если весы сказали, что фальшивая в группе с $00,$ то это и есть $00$ (иначе двое весов соврали), и четвертое взвешивание не понадобилось. Если взвешивание сказало, что фальшивая в группе с $01$ и $02,$ то третьи весы противоречат вторым. Поэтому хотя бы одни из них соврали, а значит, первые точно исправны. Но тогда у фальшивой первая цифра действительно $0;$ таким образом, остались лишь три кандидата на фальшивую монету и одни точно исправные весы, которыми мы находим фальшивую монету за $1$ ход. Аналогично поступаем, если третье взвешивание сказало, что фальшивая монета в группе с $10$ и $20.$

Переход. Разобьём $32k$ монет на одну $9$ куч по $32k−2$ в каждой. Будем считать каждую кучу за одну монету (куча с фальшивой монетой легче). Тогда по рассуждениям из базы мы либо находим за $3$ взвешивания кучу с фальшивой монетой и далее работаем с ней, пользуясь предположением, либо за $3$ взвешивания мы находим рабочие весы и три кучи, среди которых есть куча с фальшивой монетой. Во втором случае, нам хватит $2k− 1$ взвешиваний, если постоянно делить кучу на три кучи с одинаковым числом монет.

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

Задача 35#74660Максимум баллов за задание: 7

Банкир узнал, что среди одинаковых на вид монет одна — фальшивая (более легкая). Он попросил эксперта определить эту монету с помощью чашечных весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях не более двух раз. Какое наибольшее число монет может быть у банкира, чтобы эксперт заведомо смог выделить фальшивую за $n$ взвешиваний?

Источники: ММО-1997

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

Подсказка 1

Давайте для начала решим более простую задачу: пусть банкир запретил использовать каждую монету более 1 раза. Из какого наибольшего числа монет можно выделить более легкую за k взвешиваний?

Подсказка 2

Что, если на одной из чаш будет более одной монеты?

Подсказка 3

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

Подсказка 4

Если весы не в равновесии, то фальшивая монета очевидна. А если в равновесии, то количество подозрительных монет уменьшится на 2. Из скольких монет тогда можно выделить фальшивую при k взвешиваниях?

Подсказка 5

Из 2k+1. Вернемся к исходной задаче, обозначим ответ в ней за f(n). Пусть при первом взвешивании на чашах лежало по s монет. Что, если весы окажутся не в равновесии?

Подсказка 6

Тогда фальшивую монету надо будет искать среди s монет, причем каждую из них можно использовать лишь по одному разу, и осталось n-1 взвешивание. Что тогда следует из ранее доказанного?

Подсказка 7

s ≤ (2n - 1) + 1 = 2n - 1. Что, если весы окажутся в равновесии?

Подсказка 8

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

Подсказка 9

Монет, не попавших на весы, (f(n) - 2s), взвешиваний (n-1). Какое неравенство тогда получим?

Подсказка 10

f(n) - 2s ≤ f(n-1). Преобразуйте неравенство, воспользовавшись доказанным ранее.

Подсказка 11

Можно убедиться, что f(1) = 3, какая оценка накладывается на f(n) исходя из суммы арифметической прогрессии?

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

Решим сначала более простую задачу. Пусть банкир разрешает класть на весы монеты не более $1$ раза. Из какого наибольшего числа монет можно выделить более легкую за $k$ взвешиваний?

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

Если весы не в равновесии, то фальшивая монета очевидна. А если в равновесии, то количество подозрительных монет уменьшится на $2.$ Следовательно, при $k$ взвешиваниях можно выделить фальшивую из $2k +1$ монет.

Возвращаясь к исходной задаче, обозначим ответ в ней через $f(n).$ Пусть при первом взвешивании на чашах лежат по $s$ монет. Если весы окажутся не в равновесии, то придется искать фальшивую монету среди $s$ монет, причем каждую из них можно использовать лишь по одному разу, и осталось $n− 1$ взвешивание. По доказанному $s≤ 2(n − 1)+ 1= 2n − 1.$

Если весы в равновесии, то получаем исходную задачу для монет, не попавших на весы (их $f(n)− 2s$ ), и $n − 1$ взвешивания, значит,

f(n)− 2s≤ f(n − 1)

Отсюда

f(n)≤ f(n− 1)+ 2s≤ f(n − 1)+ 2(2n− 1)

Следовательно,

f(n)≤ 2(2n− 1)+2(2n− 3)+ ...+ 2⋅3+ f(1)

Поскольку, как легко проверить, $f(1)= 3,$ имеем $f(n)≤ 2n2+ 1$ по формуле для суммы арифметической прогрессии.

С другой стороны, если имеется $2 2n + 1$ монет и каждый раз брать $s$ максимальным, то есть на первом шаге $s =2n − 1,$ на втором — $s= 2n− 3,$ и т. д., то эксперт сможет выделить фальшивую монету. Значит, $2 f(n)= 2n + 1.$

Ответ:

$2n2+ 1$