Ходят слухи, что эту задачку иногда предлагают на собеседованиях при приеме на работу программистов. Вот, например, и сейчас развлекается Украинская баннерная сеть (http://www.banner.kiev.ua/job), которая пытается найти себе хорошего программиста. Обычно на решение задачи дают два часа. Задача отличная, требует хорошо развитой логики, немного знания комбинаторики. Если вы уверены в себе, то попробуйте решить задачу в уме, не делая записей. Если нет, то делайте записи. И, главное, посмотрите на время, когда вы начали решать задачу. Удачи.
Есть 12 шаров, 11 одинаковых, 12-й либо тяжелее, либо легче (это неизвестно). Есть весы, которые бывают в 3-х положениях "больше", "меньше" и "поровну". Есть 3 взвешивания, которые можно сделать. Необходимо определить какой из шаров - имеет аномальную массу.
2010-06-28 • Просмотров [ 7588 ]
С бочками не знаю даже, надо думать, Раб может умереть за сутки или за час, а суток двое.....
Делим 12 шаров на 2 группы, одну группу в копилку, а вторую взвешиваем по 3 шара,
если при взвешивании масса одинаковая,
{
то необходимый шар находится в копилке.
Берем из копилки любые 3 шара и ложим на одну из чаш весов вместо других 3-х шаров,
если весы на одинаковом уровне
{
значит из трех шаров в копилке находится аномальный
взвешиваем любые два и определяем шар
}
если весы не на одинаковом уровне
{
значит тройка новых шаров имеет аномальный шар
взвешиваем из них любые два и определяем нужный
}
}
если при взвешивании масса не одинаковая
{
значит среди взвешанных есть аномальный шар, а в копилке все одинаковые
берем любые три шара из копилки и ложим на одну из чаш весов вместо других трех шаров
если весы стали на одинаковом уровне
{
значит из убранных шаров есть аномальный
взвешиваем любые два из убранных и определяем шар
}
если весы не стали на одинаковом уровне
{
значит аномальный шар находится в другой чаше
взвешиваем любые два шара из другой чаши и определяем нужный
}
}
P.S. С помощью этого метода можно узнать направление массы аномального шара, но я направление массы не определял, так как по условию задачи это не нужно.
P.S.S. 36 минут
1 При 3 взвешиваниях можно получить 100% результат( указать шар и направление отклонения его веса) лишь в 25%
2 При 3 взвешиваниях можно указать аномальный шар без указания направления отклонения его веса лишь в 50%
3 Для 100% результата в 75% нужно 4-е измерение
В известнейшем советском фильме герой устами Юрия Никулина говорил что-то типа: "Пол-литра? Вдребезги? Да я тебя..."
Так это за пол-литра, а тут 240 бочек.
Правда встречал интерпритацию этой задачи более гуманную (правда всегда думал, что она переделана из жалости к рабам). Там вместо рабов было 5 драгоценных камней со следующим свойством: если камень окунуть в отравленное вино, то он почернеет в течение часа (в какой момент – неизвестно).
Патриций решил устроить праздник и для этого приготовил 240 бочек вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну из бочек. Недоброжелателя тут же поймали, дальнейшая его судьба неизвестна.
Про яд известно, что человек, его выпивший, умирает в течение (не «через»!) 24 часов. До праздника осталось два дня, то есть 48 часов. У патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать в какой именно бочке яд.
Как патрицию вычислить отравленную бочку?
Хотя думаю, что реально решать (читай решить) подобные задачи могут единицы, большинство может воспроизвести однажды увиденное решение. ИМХО.