16 монет и гирька, задача на алгоритм

[Xenia1996]

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

Найти алгоритм взвешивания и доказать, что меньшим числом взвешиваний не обойтись.

[Equinoxe]

Я умею за 4 действия, надо подумать, как доказать.
Назовём их все 1, 2, … 16
1. Сравниваем 1..4 с 5…8, если равны, идём в 2, иначе сравниваем 1..4 с гирькой, если равны, то фальшивая в 5..8, иначе в 1..4, а затем идём в 3
2. Сравниваем 9..12 с гирькой, если равны, то фальшивая в 13..16, иначе в 9..12
3. Мы знаем, в какой четверке есть бяка, пронумеруем её элементы 1..4. Возьмём 1..2 и сравним с любыми двумя из четверок, в которых нет бяки. Определили две монетки, среди которых есть бяка.
4. Сделали аналогично предыдущему пункту и нашли фальшивую

[Xenia1996]

Вот дказать-то, как раз, проще, чем алгоритм найти!
Подсказка: используйте троичную систему счисления.

-- Вт апр 05, 2011 21:35:51 --


Каждое взвешивание имеет ровно 3 возможных исхода:

1. перетянула левая чаша
2. правая
3. равноденствие равновесие

Если взвешиваний не более трёх, то возможных исходов не более $3\cdot 3\cdot 3=27$, а нам нужно 32 (одна из 16 монет бяка и 2 варианта отличия по весу).

[Equinoxe]

А, не учла различия по весу… Теперь понятно :)

[venco]

Меньше чем за 4 точно нельзя (максимум - 12, если нужно узнать, легче или тяжелее фальшивая монета). А за 4 можно проверить аж 39 и без гирьки.

Отставить. С гирькой можно и меньшим количеством обойтись. Скорее всего 3-х хватит.

[Xenia1996]

venco в сообщении #431620 писал(а):

Отставить. С гирькой можно и меньшим количеством обойтись. Скорее всего 3-х хватит.

Это как это?

У Вас в любом случае три исхода на одно взвешивание - хоть с гирькой, хоть без неё.

[venco]

Xenia1996 в сообщении #431622 писал(а):

venco в сообщении #431620 писал(а):

Отставить. С гирькой можно и меньшим количеством обойтись. Скорее всего 3-х хватит.

Это как это?

У Вас в любом случае три исхода на одно взвешивание - хоть с гирькой, хоть без неё.

А нет. Ошибся.
Таки надо 4 взвешивания, и тогда непонятно, зачем гирька, и почему монет только 16.

[Xenia1996]

venco в сообщении #431631 писал(а):

А нет. Ошибся.
Таки надо 4 взвешивания, и тогда непонятно, зачем гирька, и почему монет только 16.

А как без гирьки, если нужно и монету найти, и узнать, легче она или тяжелее?

[venco]

Без гирьки можно за 3 взвешивания найти фальшивую из 12-ти монет, а за 4 - из 39 монет. В общем виде $3\cdot\left[\dfrac {3^k} 6\right]$.

[Xenia1996]

venco в сообщении #431637 писал(а):

Без гирьки можно за 3 взвешивания найти фальшивую из 12-ти монет, а за 4 - из 39 монет. В общем виде $3\cdot\left[\dfrac {3^k} 6\right]$.

Это вот так, что ли?

[venco]

Да. Метод можно расширить на любое количество взвешиваний.

-- Вт апр 05, 2011 14:27:50 --

А формулу можно так записать:
$\dfrac {3^k-3}2$

[Xenia1996]

venco в сообщении #431641 писал(а):

Да. Метод можно расширить на любое количество взвешиваний.

-- Вт апр 05, 2011 14:27:50 --

А формулу можно так записать:
$\dfrac {3^k-3}2$

Спасибо!
Теперь буду знать.

[Руст]

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

[Equinoxe]

Руст, и что? Если одна половина будет тяжелее, другая легче, от этого действия мы узнаем лишь то, что среди этих 12 монет есть плохая, в моём варианте с первого взвешивания мы узнаем 8 монет, среди которых есть плохая.
И потом, что Вы имеете против док-ва Ксении недостаточности 3х взвешиваний?

[Xenia1996]

Руст в сообщении #431659 писал(а):

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

Предположим, перетянула та, на которой 8. Значит, либо фальшивая там, и она тяжелее, либо фальшивая среди четырёх других, и она легче.
Что мы имеем?