Предлагается решить такую задачку: "Есть восемь монет одинаковой формы и размера. Одна из них легче других по весу.
Надо при помощи аптекарских весов гарантированно ее определить не более чем за ДВА взвешивания."

Первое взвешивание - по 4 монеты произвольно на каждую чашу весов.
Та часть которая легче содержит искомую монету и участвует во втором взвенивании.

Второе взвешивание - по 2 монеты произвольно на каждую чашу весов.
Та часть которая легче содержит искомую монету.

Последний шаг: - снимаем по одной монете одновременно с каждой чаши. Если весы уравновесились, то монета у нас в руках, если нет, то осталась на чаше...
Другого пути не вижу, только не является ли этот третий шаг по сути третьим взвешиванием?

Ответ не верный

Каратаев
не является ли этот третий шаг по сути третьим взвешиванием?

Является

1. Берем две кучки по 3 монеты. Взвешиваем.
1.1. Если весы ровно, то взвешиваем оставшиеся две, весы покажут who is who
1.2. Если не ровно, то из кучки которая легче, берем две монеты, взвешиваем. Если ровно, то оставшаяся - искомая монета, если нет то весы покажут who is who.

2AleksM
Поздравляю!

А приз?

AleksM
А приз?

А где гарантия что где нибудь на просторах инета ответ не сдернули? ;)

Я дальше Фоксклуба не хожу. Боюсь
Вот так вот думаешь, думаешь, все мозги помнешь, а тебе не верят

PS Просто вспомнилась задачка про мешки с деньгами, которую тут тоже решали.



Отредактировано (28.07.05 08:34)

Цитата:

Просто вспомнилась задачка про мешки с деньгами, которую тут тоже решали

Вот оно что
Тут в аське с утра кидала программисту для разминки - так вместо шевеления мозгами в инет полез - ссылочку интересную прислал
golovolomka.hobby.ru
Видно так проще - в инет - и думать не надо
Ну раз так

Цитата:

Вот так вот думаешь, думаешь, все мозги помнешь

То приз... ээээ.... Во!
Приз за правильное решение:

Цитата:

Приз за правильное решение:

Спасибо. "Мой любимый цвет, мой любимый размер" (с)



Отредактировано (28.07.05 08:54)

мы радость хотели вам доставить (с)

А если исходную задачу немного переформулировать - одна из монет просто отличается по весу от остальных, в какую сторону неизвестно. Тогда какое минимальное количество взвешиваний потребуется для того, чтобы определить искомую монету?

Еще задача. Есть хрустальный шар и стоэтажный дом. Требуется выяснить начиная с какого этажа, хрустальный шар будет разбиваться, если его свободно бросить. Понятно, что имея один шар, нам понадобится максимум 100 шагов для выяснения этого: поднялись на первый этаж - бросили - не разбился - поднялись на следующий этаж и т.д. Заказчик не хочет ждать столько времени и дает еще один хрустальный шар. Ваша задача предложить алгоритм, который гарантированно будет определять этаж, начиная с которого шар будет разбиваться, за минимальное число шагов.

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

Для первого: max = 7 шаров.

PS 2**7 = 128





Исправлено 1 раз(а). Последнее : PaulWist, 20.02.08 14:26

Первое, что на ум пришло. Кидаем шар с 1-го этажа, далее со 2-го, 4, 8, 16, 32,64.
Если с N-го этажа шар бьется, то начинаем кидать второй шар начиная с N/2+1-го этажа.
Если на 64 этаже шар не бьется, то кидаем с 65 до 100.

PaulWist
На выбор, хоть метод дихотомии, хоть золотого сечения.
Для первого: max = 7 шаров.

PS 2**7 = 128

Паша, перечитай условие. Есть только два шара.

medstrax
Первое, что на ум пришло. Кидаем шар с 1-го этажа, далее со 2-го, 4, 8, 16, 32,64.
Если с N-го этажа шар бьется, то начинаем кидать второй шар начиная с N/2+1-го этажа.
Если на 64 этаже шар не бьется, то кидаем с 65 до 100.

Но это не лучший результат ;)

А-а-а, шаров-то всего два, понял.

Тогда 15 шагов получается, но если сейчас сумею вспомнить как взять производную от суммы геометрической прогрессии, то возможно будет меньше





Исправлено 1 раз(а). Последнее : PaulWist, 20.02.08 15:14

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

14 ты хотел сказать?

А, ты в смысле, что на последнем этапе можно-нужно тоже арифметич. прогрессию использовать, тогда, действительно 14. , тока всё равно чЁ то пока доказательство в аналитическом виде, пока не могу.