Слитки золота и взвешивания.

[bitcoin]

Есть два задания, немного не получается догадаться. Сможете помочь с идеей, пожалуйста?

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


Точно понятно, что за одно взвешивание можно определить фальшивый слиток среди трех слитков. Понятно, что среди четырех слитков не получится определить фальшивый за одно взвешивание. Понятно, что разбив на три тройки слитков, можно за два взвешивания среди 9 слитков определить фальшивый.
А вот дальше немного тяжелее рассуждать, у меня получается длинное рассуждение с перебором случаев. За одно взвешивание можно определить среди двух равных групп слитков фальшивую группу или среди трех равных групп фальшивую. Поместим в группу $A_1$ три слитка, в группу $A_2$ три слитка, в группу $A_3$ оставшиеся слитки. В группах $A_1$ и $A_2$ мы может определять фальшивый слиток за одно взвешивание. Однако сравнив массы $A_1$ и $A_2$ может оказаться так, что они равны, тогда группа $A_3$ будет содержать 4 или более слитков, следовательно одного взвешивания не хватит. Но неужели нужно рассматривать остальные разбиения? А если слитков более 10?

2. Один из девяти слитков золота фальшивый, он весит легче настоящего. Как определить фальшивый слиток за два взвешивания, если второе взвешивание делается независимо от результатов первого?

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

[Dan B-Yallay]

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

Понятно, что среди четырех слитков не получится определить фальшивый за одно взвешивание

Вот и используйте этот аргумент для $n > 9$

[lel0lel]

(Оффтоп)

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

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

[wrest]

lel0lel в сообщении #1646748 писал(а):

Есть два задания, немного не получается догадаться. Сможете помочь с идеей, пожалуйста?

Ну идея тут простая. Количество исходов должно быть не меньше количества монет.
Одно взвешивание максимально даёт три исхода: перевесила первая, вторая чаша или ни одна из двух.
Сколько исходов даёт два взвешивания?

[bitcoin]

wrest в сообщении #1646750 писал(а):

Ну идея тут простая. Количество исходов должно быть не меньше количества монет.
Одно взвешивание максимально даёт три исхода: перевесила первая, вторая чаша или ни одна из двух.
Сколько исходов даёт два взвешивания?

Спасибо. 9 исходов. Но почему же количество взвешиваний должно быть не меньше количества монет?

Dan B-Yallay в сообщении #1646747 писал(а):

Вот и используйте этот аргумент для $n > 9$

В том-то и дело, что не очень ясно - как именно.

lel0lel в сообщении #1646748 писал(а):

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

Спасибо.
Но мы ведь заранее не знаем, где именно будет тройка с фальшивым слитком. А вдруг мы из этой тройки возьмем нефальшивый слиток?

-- 19.07.2024, 02:00 --

lel0lel в сообщении #1646748 писал(а):

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

Теперь понятно, спасибо с первой задачей

[Mihr]

По поводу второй задачи. Давайте пронумеруем слитки и занесём их номера в квадратную таблицу с 9 ячейками (первая строчка - номера 1, 2, 3, вторая - номера 4, 5, 6, третья - номера 7, 8, 9.
Первое взвешивание - выделяем "легчайшую строчку" этой таблицы, для чего сравниваем общий вес 1-го, 2-го и 3-го слитков с общим весом 4-го, 5-го и 6-го.
Второе взвешивание - выделяем "легчайший столбец" этой таблицы, для чего сравниваем общий вес 1-го, 4-го и 7-го слитков с общим весом 2-го, 5-го и 8-го.
На пересечении легчайшей строчки и легчайшего столбца - номер фальшивого слитка.

Первая задача уже разобрана, но я сделаю свое замечание. Общее количество информации, которое требуется получить, составляет $I=\log_2 9$ бит. Максимальное количество информации, которое может дать одно взвешивание, составляет $I_1=\log_2 3$ бит. Число взвешиваний не может быть меньше, чем $n=\dfrac{I}{I_1}=\dfrac{\log_2 9}{\log_2 3}=\log_3 9=2$. Решение не столь наглядное как Ваше, но зато существенно более короткое

[EUgeneUS]

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

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

Потому что у Вас есть $n$ возможных исходов - фальшивой может оказаться ровно одна из монет. (Фальшивая легкая или тяжелая - известно заранее).
И эти исходы нужно различать. А для этого система взвешивания должна давать не менее $n$ исходов.

[Mihr]

Да нет, количество необходимых взвешиваний меньше количества монет.

[EUgeneUS]

Mihr
Кто-то с этим спорит? (Для данного случая)

[Mihr]

EUgeneUS, нет? Тогда я не понял, о чём Ваша реплика, извините.

[lel0lel]

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

Но мы ведь заранее не знаем, где именно будет тройка с фальшивым слитком. А вдруг мы из этой тройки возьмем нефальшивый слиток?

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

[wrest]

Mihr в сообщении #1646772 писал(а):

нет? Тогда я не понял, о чём Ваша реплика, извините.

Тут всё просто. Моя версия развития событий такая.
Я написал что

wrest в сообщении #1646750 писал(а):

Количество исходов должно быть не меньше количества монет.

ТС переспросил что

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

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

Ну а EUgeneUS не заметил подмены исходы-> взвешивания (или посчитал что ТС ошибся/опечатался и не стал поправлять) и написал что

EUgeneUS в сообщении #1646765 писал(а):

Потому что у Вас есть $n$ возможных исходов

Это создало у вас ложное впечатление будто бы EUgeneUS положительно отвечал на вопрос ТС в [неверной] формулировке (как бы соглашаясь с ней) почему взвешиваний должно не меньше чем монет.

[bitcoin]

lel0lel в сообщении #1646773 писал(а):

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

Спасибо! Действительно, это работает и это очень просто. Сложнее всего догадаться до этого.

[мат-ламер]

Задача, похожая на первую в этой теме, разбиралась тут .

-- Пт июл 19, 2024 11:52:46 --

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

Сложнее всего догадаться до этого.

Если знать троичную систему исчисления, то догадаться легче.

[wrest]

(мат-ламер)

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

Задача, похожая на первую в этой теме, разбиралась тут
.

Так там ТС спрашивал про бутылки с пивом, а тут про слитки с золотом. Это ж разное, понимать надо...