9 монет (логическая задачка)

Имеются 9 монет и рычажные весы. Среди монет имеется одна фальшивая, отличающаяся от остальных по весу. Необходимо ее определить за три взвешивания.

Выглядит просто, но у меня меньше четырех взвешиваний не получается никак. Старею :(

на 3 кучки разделить надо вначале =)

1) по 4 монеты на каждую чашу весов, и одна в запасе.
1. a) если вес чаш одинаков - монета которая фальшивая в запасе
1. б) если вес чаш разный - берем ту сторону которая легче
2) делим эту сторону 4 монеты по 2 на каждую чашу и выбираем более легкую сторону
3) делим 2 монеты на каждую чашу по одной и находим фальшивую

XELFAER, не сказано, что фальшивка легче
Silencer, вроде правильно, но там хитрожопая вторая часть...

123 V 456 -> s1 ? {
  s1=="=": 789 - одна из фальшивая
  s1=="!=": 15 V 42 -> s2 ? {
    "=" => 36 - фальшивые
    s1==s2 => 14 - фальшивые
    s1!=s2 => 52 - фальшивые
  }
}

Подразумевается, что фальшивая монета легче. Изначально монеты были золотые и серебряные (только их подделывать есть смысл), а это тяжёлые металлы. Фальшивка же должна быть из недорогого и лёгкого металла.

"Vascom" написал:

Подразумевается, что фальшивая монета легче. Изначально монеты были золотые и серебряные (только их подделывать есть смысл), а это тяжёлые металлы. Фальшивка же должна быть из недорогого и лёгкого металла.

Вообще-то, весь цимес задачи в том, что неизвестно, в какую сторону фальшивка от настоящей монеты отличается, иначе бы она вообще в два действия решалась.

"Vascom" написал:

Подразумевается, что фальшивая монета легче.

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

Но если неизвестно легче или тяжелее, то делением на 3 кучки не найдёшь ведь.

"Vascom" написал:

Но если неизвестно легче или тяжелее, то делением на 3 кучки не найдёшь ведь.

решается... смотри у меня под спойлером, если невтерпёж... [очевидные действия я опустил]

ЗЫ: я вас ненавижу... уже три часа на braingames.ru с этой подачи зависаю...

Fat-Zer, всё равно за три взвешивания у тебя не получается определить одну фальшивую монету.

"Vascom" написал:

Fat-Zer, всё равно за три взвешивания у тебя не получается определить одну фальшивую монету.

Почему. Имхо в худшем случае 3

Может тогда распишите алгоритм Fat-Zer на пальцах и с пояснением каждой строки? Если не сложно.

Я согласен, что это можно сделать, но не алгоритмом Fat-Zer.

Vascom написал:

Может тогда распишите алгоритм Fat-Zer на пальцах и с пояснением каждой строки? Если не сложно.

Я согласен, что это можно сделать, но не алгоритмом Fat-Zer.

Делим монеты на три стопки по три.
1. 1ое Взвешивание. 123 и 456. Если веса равны то фальшивка в стопке 789 (переход на пункт 2) Иначе на п. 3.

2. Если по п.1 фальшивка в 789. 2ое взвешивание 7 против 8. Если веса равны то фальшивка 9. Больше взвешиваний не нужно. Иначе переходим на 2.1
2.1 3е взвешивание Взвешиваем 7 и 9. Если веса равны то фальшивка 8, если веса не равны фальшивка 7. Больше взвешиваний не нужно в обоих случаях

3. Перераспределяем монеты и взвешиваем (2-ое) 14 и 25. Если равны то переходим на 3.1 иначе на 3.2
3.1 Если 14 и 25 равны. То фальшивка в 3 или 6. Взвешиваем (3-е) 34 и 25. Если равны, то фальшивка 6 иначе 3. Больше взвешиваний не нужно
3.2. (Если 14 тяжелее 25 и 123 тяжелее 456 (по 1ому взвешиванию) ) или (Если 14 легче 25 и 123 легче 456 (по 1ому взвешиванию) ) то фальшивка 1 или 5 (переход на 3.2.1) иначе 4 или 2 (переход на 3.2.2)
3.2.1 Взвешиваем (3-е) 64 и 25 если равны фальшивка 1 иначе 5
3.2.2 Взвешиваем (3-е) 16 и 25 если равны фальшивка 4 иначе 2

Т.е ходы взвешиваний

1 - 2 (рез 9)
1 - 2 - 2.1 (рез 8 или 7)
1 - 3 - 3.1 (рез 6 или 3)
1 - 3 - 3.2.1 (рез 1 или 5)
1 - 3 - 3.2.2 (рез 2 или 4)

Не знаю как вам, а мне сложно было об этом догадаться по этому алгоритму:

123 V 456 -> s1 ? {
  s1=="=": 789 - одна из фальшивая
  s1=="!=": 15 V 42 -> s2 ? {
    "=" => 36 - фальшивые
    s1==s2 => 14 - фальшивые
    s1!=s2 => 52 - фальшивые
  }
}

"Vascom" написал:

Не знаю как вам, а мне сложно было об этом догадаться по этому алгоритму:

я сам не смог решить задачу пока не увидел этот алгоритм :)

Vascom, кто захотел тот понял... =)
+ рассчитывал, что алгоритм за одно/два взвешивания определить фальшивку из 2/3 монет вы можете...
ЗЫ: я конечно мастер изобретать псевдокоды, но пару не однозначностей синтаксиса допустил... поправлюсь от греха подальше...

123 V 456 -> s1 ? {
  s1=="=": 789 - фальшивые
  s1=="!=": 15 V 42 -> s2 ? {
    s2=="=" : 36 - фальшивые
    s1==s2 : 14 - фальшивые
    s1!=s2 : 52 - фальшивые
  }
}

"Fat-Zer" написал:

XELFAER, не сказано, что фальшивка легче

или легче или тяжелее - разница в весе, последовательность действий не меняется.

"XELFAER" написал:

или легче или тяжелее - разница в весе, последовательность действий не меняется.

Меняется. Как вы определите кучку, где находится фальшивая монета, не зная, легче или тяжелее она должна быть?

"Lupo Alberto" написал:

Меняется. Как вы определите кучку, где находится фальшивая монета, не зная, легче или тяжелее она должна быть?

точно, верно замечено.

Ну тут понятно, достаточно определить каких больше: тяжёлых или лёгких. И вроде в алгоритм это входит.