Задачка на взвешивание

Боян.

первая ссылка в гугле

Взвешиваем 6 и 6 монет. Выясняем в какой из шести-монетных кучек находится фальшивая. Затем взвешиваем 3 и 3 - выясняем в какой из трех-монетных кучек находится фальшивая.
Потом берем наугад 2 монеты из трех и взвешиваем их. Если одна легче другой - то она фальшивая. Если они одинаковые - то фальшивая та, которую не взвесили.

>Взвешиваем 6 и 6 монет. Выясняем в какой из шести-монетных кучек находится фальшивая.

фальшивая либо легче либо тяжелее настоящей

>Взвешиваем 6 и 6 монет. Выясняем в какой из шести-монетных кучек находится фальшивая.
Ну и как? Фальшивая либо легче либо тяжелее. И как понять в какой кучке фальшивая, если использовать твой метод?

>фальшивая либо легче либо тяжелее настоящей

Да, этого я не заметил.

Я не заметил что фальшивая может быть не только легче, но и тяжелее.

А вот тут уже, братан, Сила в действие вступает.

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

За 3 хода можно определить.

Разделяем на 3 кучки по 4 монеты
1 - взвесить две кучки по 4 монеты
если они уравновесятся - определяем, что фальшивая манета в невзвешенной кучке
если не уравновесятся - то хз, нужно дополнительное взвешивание, чтобы определить, какая кучка фальшивая

2 - взвешиваем две монеты (по одной на чашу) из фальшифой кучки.
далее:
а) если они уравновесятся, то там только 100% нормальные монеты, стало быть фальшивая в оставшихся двух монетах.
Тогда 3 - Сравниваем одну из оставшихся монет с монетой из 2х нормальных. Если они не уравновесятся, фальшивая и есть эта монета (которую сравниваем), а если уравновесятся - фальшивая та, что осталась.
б) если они не уравновесятся, то 100% нормальные монеты в невзвешенной кучке из 2х монет. Далее - как в а)

>если не уравновесятся - то хз, нужно дополнительное взвешивание

Нет, можно решить без доп. взвешивания.

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

Там по-мойму даже за 2

Ну как за 2 я не знаю. А за 3 решал давно уже.

Давай я выражу задачу по другому.

Есть у нас 12 булевых значений в массиве X с индексами от 0 до 11. Одно не равно всем остальным. И есть функция f(a, b), где a и b суть списки целочисленных значений, каждое из которых равно индексу массива. Функция возвращает булево значение в зависимости от того, одинаковы ли множества значений { X(i) for i in a } и {X(i) for i in b}.

Как определить, пользуясь лишь функцией f(), который из элементов X не равен остальным и каков расклад (искомый элемент False, остальные True, или наоборот)?

Пора сдувать пыль с пролога.

Зачем? Я могу и 12 раз взвесить, мне не сложно.

• Взвешиваем 4 и 4.
  Если в равновесии - фальшивая среди 4-х отложенных, за два взвешивания легко находится. [1]
  
• Запоминаем, какая из кучек тяжелее.
  Отбираем из тяжёлой кучки 3 монеты, кладём в сторону и заменяем тремя из лёгкой, а в бывшую лёгкую докладываем из уже найденных 4-х настоящих.
  Теперь:
  - Если весы уравновесились, то фальшивая среди 3-х отложенных (и она тяжелее).
  - Если весы поменяли положение, то фальшивая среди 3-х переложенных из лёгкой кучки (и она легче).
  - Если весы остались в том же положении, то 3 отложенные - настоящие, следовательно, фальшивая среди тех двух, что не перекладывались (вес неизвестен) - находится за одно взвешивание. [1]
  
• Имеем кучку из трёх монет, одна из них фальшивая, и уже известно, тяжелее или легче она настоящих:
  Взвешиваем любые две (по одной на каждой стороне). Если в равновесии, фальшивая - отложенная, иначе та, которая легче (тяжелее) - отношение весов определено уже.
  
  [1] - для тех, кто не знает, как определить среди двух одинаковых кучек - в которой находится фальшивая:
  - Кладём на одну половину первую кучку, на вторую - такого же размера кучку из настоящих (благо после 1-го взвешивания их достаточно).
  - Если весы в равновесии - фальшивая в отложенной, второй, иначе - в первой.
  Для «кучек» из одной монеты та же фигня.

А твоя постановка некорректна, потому что по ней нельзя определить, тяжелее монета или легче - а без этого за 3 взвешивания не решить.