Задача про 12 монет. Возвращение.

← →
zzet © (2003-10-21 14:20) [0]

Веревки поподжигали, изделия поодевали, давайте вспомним старую задачу про 12 монет?
Тем более что есть интересное решение и новый вариант.
(решение и задачи взяты из "БУМАЖНАЯ КОМПЬЮТЕРРА - 1997")

Задача 1
Из двенадцати монет одиннадцать настоящих, а одна фальшивая (она отличается по весу от настоящей, но не известно, в какую сторону). Требуется за три взвешивания на двухчашечных весах без гирь найти фальшивую монету и выяснить, легче она или тяжелее настоящей.

Решение:
Для начала специальным образом пронумеруем монеты: присвоим им трехзначные номера 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.Если нет, то заменим в этом числе все нули на двойки, а все двойки на нули. После этого оно должно совпасть с номером какой-то монеты. Эта монета фальшивая и легче остальных.

Задача 2
Из пяти монет три настоящие, одна фальшивая легкая и одна фальшивая тяжелая. Фальшивые монеты вместе весят столько же, сколько две настоящие. Можно ли за три взвешивания на двухчашечных весах определить обе фальшивых монеты? Если да, то как это сделать?

← →
Кабан (2003-10-21 15:05) [1]

интересно, зачем было приводить задачу и тут же давать решение, причем старое(кстати количество монет можно увеличить до 13)

← →
SergP © (2003-10-21 15:05) [2]

Взвешиваем поочереди монеты:
1.) 1+2 и 3+4
2.) 1+3 и 2+4
3.) 1+4 и 2+3

Если ни в одном из случаев не было одинакового веса, то одна фальшивая монета - та которая во всех случаях находилась на той чашке, которая либо всегда перевешивала (в этом случае она тяжелая), либо в той чашке, которая всегда оказывалась легче по весу (тогда она легкая). Вторая фальшивая будет 5 монета.

Если в одном из случаев зафиксировано равенство чашек весов, значит монета 5 - настоящая. Фальшивая легкая та которая находилась в обоих случаях в "легкой" чашке, а фальшивая тяжелая - та, которая в обоих случаях находилась в "тяжелой чашке".

← →
Sergp © (2003-10-21 17:09) [3]

Или нужно рещение аналогичное решению предыдущей задачи?
Типа заумное с цифирками....

← →
Johnmen © (2003-10-21 18:05) [4]

>Кабан (21.10.03 15:05)
>...количество монет можно увеличить до 13)

Можно и до 100. Только решить не получится...За 3 взв-ия...
:)))))))))

← →
Кабан (2003-10-22 10:22) [5]

2 Johnmen © (21.10.03 18:05) [4]
Очевино, что, когда я говорю, что количество монет можно увеличить до 13, то определить фальшивую монету можно за 3 взвешивания.

← →
Кабан (2003-10-22 10:23) [6]

хотя не получится определить легче или тяжелее

>Кабан (22.10.03 10:23)

А значит и не решается.

Еще задачка оттуда же, тоже, имхо, интересная.

У вас имеется куча монет и счетчик Гейгера. Две монеты в куче являются радиоактивными. Вы можете выбрать любое подмножество монет и поднести к ним счетчик (назовем такую процедуру замером). Если среди них есть хотя бы одна радиоактивная монета, счетчик обнаружит это. Требуется определить обе радиоактивных монеты за N замеров. Для какого наибольшего числа монет в куче это всегда можно сделать? Как именно нужно отбирать замеряемые подмножества монет?

Задал эту задачку в классе - никто не решил:) Один я:)

Задача про 12 монет. Возвращение. Найти похожие ветки