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

tramal

имеются 13 монет, одна из них фальшивая - легче или тяжелее, неизвестно. Как за три взвешивания ее найти?

1sandra

А типа, это невозможно.

resident

типа ты пиздишь.
решение:
1. делим на 6 и 7 монет
2. Рассмотрим кучку из 6 монет - делим на 3 и 3 - взвешиваем
Если равно - го ту пункт 3, иначе продолжаем и укладываемся в 3 взвешивания
3. Рассмотрим кучку из 7 монет - делим на 4 и 3
берем кучку из 4 монет - делим на 2 и 2 - взвешиваем
если равно - то рассматриваем кучку из 3 монет и укладываемся в 3 взвешивания
иначе продолжаем и все равно укладываемся в 3 взвешивания

tanuhka3

могу рассказать
кстати по моему эта задача уже обсуждалась здесь

_shmel_

>рассматриваем кучку из 3 монет и укладываемся в 3 взвешивания
как найти фальшивую монетку из 3-х за 1 взвешивание?

resident

хм

aqvamen

подробней
одна из них фальшивая - легче или тяжелее, неизвестно

Mike3

Гуля, четай Мартина Гарднера
Во-первых, специальным образом пронумеруем монеты: присвоим им трехзначные номера 001, 010, 011, 012, 112, 120, 121, 122, 200, 201, 202, 220.
Для первого взвешивания положим на одну чашу весов те монеты, у которых старший разряд равен 0 (то есть 001, 010, 011, 012 а на другую - те монеты, у которых он равен 2 (200, 201, 202, 220). Если перетянет чашка с "0", запишем на бумажке цифру 0. Если перетянет "2" - запишем 2. Если чаши весов останутся в равновесии - запишем 1.
Для второго взвешивания на одну чашу выложим монеты 001, 200, 201, 202 (то есть все те монеты, у которых второй разряд равен 0 а на другую - 120, 121, 122, 220 (то есть те монеты, у которых средний разряд равен 2). Запишем результат взвешивания таким же образом, что и при первом взвешивании.
Третьим взвешиванием сравниваем 010, 020, 200, 220 с 012, 112, 122, 202 (соответственно, нули и двойки в младшем разряде) и записываем третью цифру.
Мы получили три цифры - иначе говоря, трехзначное число. Далее определяем фальшивую монету по следующему рецепту:
1) Если это число совпадает с номером какой-то монеты, то эта монета фальшивая и тяжелее остальных.
2) Если нет, то заменим в этом числе все нули на двойки, а все двойки на нули. После этого оно должно совпасть с номером какой-то монеты. Эта монета фальшивая и легче остальных.
А теперь представим себе, что нам не нужно узнавать про фальшивую монету, легче она или тяжелее настоящих. Оказывается, что в этом случае можно за три взвешивания выявить фальшивую даже среди 13 монет! Как это сделать?
Оказывается, очень просто: присвоим этой монете номер 111 и не будем ее использовать ни в одном взвешивании. Если она настоящая, то среди остальных монет мы обнаружим фальшивую точно так же, как и в первой задаче (и даже сумеем узнать, легче она или тяжелее). А если монета 111 фальшивая, то весы трижды останутся в равновесии (ведь фальшивую монету мы на чаши не кладем! поэтому мы трижды запишем цифру 1 и в результате получим как раз 111. В этом случае мы не будем знать, легче она или тяжелее, - но нам это и не нужно.

joker2oo9

Вот мое решение.
Взвешиваем две 4-ки. Самое сложное если они оказались не равны, остановимся на этом случае. Разобьем каждую 4-ку на три кучки как показано ниже, будем располагать в левом столбце монеты из тяжелой 4-ки, а справа из легкой
1 1
2 1
1 2
Поменяем монеты в первой строке и взвесим монеты из первых двух строк (к монетам из второго столбца добавим одну монету из третьей 4-ки).
Если фальшивая монета в первой строке, то правая чаша станет тяжелее.
Если фальшивая монета во второй строке, то левая чаша останется тяжелее.
Если фальшивая монета в третьей строке, то весы уравновесятся.
Далее всё очевидно.
Проверено

tanuhka3

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

joker2oo9

поподробнее последовательность взвешиваний укажи

tanuhka3

сначала 1я строчка, потом 2я, потом 3я.

joker2oo9

тк в каждой строчке по 13 взвешиваний

tanuhka3

ты не понял.
в каждой строчке по 4 плюса и 4 минуса.
Все монеты с плюсами кладем на правую чашу весов, а
с минусами на левую.

joker2oo9

чем определяется порядок "+" и "-" в первой строке
и вообще, попонятнее можешь написать.
у тебя знаками то результат взвешивания обозначается, то на какую чашу монеты кладутся

tanuhka3

блин, что непонятного-то?
По каждой из трех строчек можно сказать, какие монеты участвуют во взвешивании, и на какой чаше весов.
Монеты пронумерованы числами 1..13.
Монете под номером k соответсвует столбец под номером k.
Результат взвешивания обозначается +, если перевесила правая чаша, - если левая,
0 если равенство.
Такими же знаками обозначается где конкретная монета находится во время взвешивания.
Например, если первая монета фальшивая и тяжелее остальных,
то поскольку она во всех трех взвешиваниях лежала на правой чаше весов (+ + +
то правая чаша все время перевешивает, и результат взвешиваний тоже будет (+ + +).
Так по результату мы сможем определить, что именно монета под номером 1
является фальшивой и тяжелее остальных.

joker2oo9

с точностью до переобозначений "+","-","0" на "1","2","0" это тоже самое что вот .
Зачем было это писать? да еще так не понятно.

tanuhka3

ВСЕ ЗАБЕЙ
PS я даже не читал и не буду читать то решение,
потому что оно жутко длинное, а значит, непонятное.

joker2oo9

в твоих двух сообщениях 1292 символа
в основной части того сообщения 1310 символа
На мой взгляд, тот пост гораздо понятнее чем твой, твой я понял лишь, потому что прочитал тот.

Mike3

ты прав, ибо этот мой пост нагло спижжен из книжки М. Гарднера какой-то.
А он пишет очень популярно и красиво
Оставить комментарий
Имя или ник:
Комментарий: