Школьная задача про пиво и взвешивание.

[bitcoin]

Помогите, пожалуйста, разобраться.

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

Я понимаю, что 243 бутылки можно проверить за 5 взвешиваний, а 244 уже за 6 (и понимаю как это просто показать пример разбив на группы 81,81,81,1). Но существует ли простой способ доказать, что за 5 взвешиваний не получится среди 244 выявить подделку?) Или только в лоб нужно расписывать все возможные случаи, написав минимальное количество взвешиваний для 2,3,4,...., 244 бутылок? Я пробовал притянуть индукцию, но она хорошо работает для $3^n$ бутылок, а вот для $3^n+1$ уже что-то не то получается)

[realeugene]

Какая мощность множества всех возможных результатов 5 взвешиваний?

[bitcoin]

realeugene в сообщении #1608748 писал(а):

Какая мощность множества всех возможных результатов 5 взвешиваний?

Спасибо.
Получается, что 243. Но как количество возможных результатов взвешиваний связано с количеством бутылок? Что-то тут туплю.

[realeugene]

Попробуйте определить функцию, отображающую результат взвешиваний в номер бутылки.

[bitcoin]

realeugene в сообщении #1608750 писал(а):

Попробуйте определить функцию, отображающую результат взвешиваний в номер бутылки.

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

[svv]

bitcoin
Этой функции на вход подаётся совокупность результатов всех пяти взвешиваний. Вы сказали, что возможных результатов взвешиваний всего 243. Сколько различных "ответов" может появиться на выходе функции?

[sergey zhukov]

bitcoin
А почему, кстати, вы увернены, что для 243 бутылок минимальное количество взвешиваний 5? Может, и меньше есть? Как вы определили, что 5?

Так-то недолив пива я бы и на глаз определил вообще без взвешивания.

[bot]

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

[sergey zhukov]

bot
Неужели одно?

[bitcoin]

sergey zhukov в сообщении #1608755 писал(а):

Вот тут легко объяснить - почему два. Просто сказать, что сначала взвешиваем по две бутылки на каждой чаше. Обязательно перевесит чаша с фальшивой (но не ясно - какая именно из двух, потому нужно второе взвешивание). За второе взешивание - узнаем - какая именно фальшивая. Почему нельзя за одно? Вот тут я вижу такое объяснение. Если мы взвесим по одной бутылке, то в худшем случае получаем равновесие и тогда какая-то из оставшихся будет фальшивая. Но чтобы узнать - какая именно - для этого нужно будет еще одно взвешивание. Ситуацию со взвешиванием по 2 бутылки мы уже рассмотрели (и поняли - почему не хватает одного взвешивания). Сравнение веса одной бутылки с тремя - никакой полезной информации не даст. Других вариантов просто нет) Аналогичным образом можно и дальше описывать для большего количества бутылок, но количество вариантов будет довольно-таки быстро расти.

-- 11.09.2023, 13:18 --

sergey zhukov в сообщении #1608755 писал(а):

bitcoin
А почему, кстати, вы увернены, что для 243 бутылок минимальное количество взвешиваний 5? Может, и меньше есть? Как вы определили, что 5?

Так-то недолив пива я бы и на глаз определил вообще без взвешивания.

Вот тут только непосредственной проверкой вижу только вариант убедиться, аналогичной той, что я сделал с 4-мя бутылками. P.S. Недолив на 0,5% заметили бы?))

-- 11.09.2023, 13:27 --

svv в сообщении #1608754 писал(а):

bitcoin
Этой функции на вход подаётся совокупность результатов всех пяти взвешиваний. Вы сказали, что возможных результатов взвешиваний всего 243. Сколько различных "ответов" может появиться на выходе функции?

Я результаты взвешивания вижу следующим образом (сначала обозначения):

0 - массы бутылок совпали

1 - бутылка на левой чаше весов легче

2 - бутылка на правой чаше весов легче

И тогда результаты можно ожидать в виде

00000
10101
22110
12011
......
Ну и тут просто объяснить - почему именно 243. Но как сопоставить результаты такого вида конкретным бутылкам, с учетом того, что мы могли взвешивать по 10 бутылок, по 84 итд. Просто в голову не укладывается.

[sergey zhukov]

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

Каждое взвешивание имеет три варианта исхода: правое тяжелее, левое тяжелее, оба равны (очевидно, ставим всегда равное число бутылок на весы с обеих сторон, т.к. в противном случае нам ответ заранее известен). Допустим, пометим исходы взвешивания, как $-1, 0, +1$. Выполнив $N$ взвешиваний, имеем $3^N$ возможных последовательностей результатов взвешиваний. Например, такую: $0, -1, -1, +1, 0, 0 ...$. В результате $N$ взвешиваний мы должны ответить на вопрос о том, какая бутылка легче. У нас всего $3^N$ результирующих разных последовательностей, т.е. мы не можем по результатам этих взвешиваний получить более, чем $3^N$ разных ответов о том, какая бутылка легче. Если бутылок у нас больше, чем вообще существует разных возможных ответов (разных последовательностей), то мы не можем решить задачу однозначно.

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

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

[mihaild]

bitcoin, немного другое объяснение того же самого.
Представьте что Вы составляете инструкцию по взвешиванию, и даёте её мне. Я Вам сообщаю последовательно результаты взвешиваний - в первом перевесила левая чаша, во втором равновесие, и т.д. Что именно я взвешивал, сообщать не обязательно, т.к. Вы можете это вычислить исходя из инструкции и предыдущих частей моего рассказа: первое взвешивание не должно зависеть ни от чего, второе может зависеть только от первого, и т.д.
Таким образом, получив от меня рассказ о взвешиваниях (а таких рассказов $3^N$ вариантов) Вы должны суметь назвать номер от $1$ до $M$, причем, естественно, по одному и тому же рассказу Вы должны называть один и тот же номер, и любой номер будет назван для некоторого рассказа (хотя бы для получающегося если бутылка именно с этим номером фальшивая). Значит $M \leqslant 3^N$ (обновлено, была опечатка - неравенство не в ту сторону).

[Mikhail_K]

mihaild в сообщении #1608798 писал(а):

Значит $M \geqslant 3^N$.

Наоборот, $M\leq 3^N$.
$N$ - количество взвешиваний, $M$ - количество бутылок, которые можно распознать этими взвешиваниями.

[мат-ламер]

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

[bot]

bitcoin в сообщении #1608793 писал(а):

сначала взвешиваем по две бутылки на каждой чаше

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

мат-ламер в сообщении #1608804 писал(а):

Дьявол перед взвешиванием мгновенно выбирает группу бутылок с наибольшим количеством бутылок