Боян-боянистый.

Есть старая задача про 12 шаров и три взвешивания.Если кто не знает то условие таково: Есть 12 шаров, 11 одинаковых, 12-й либо тяжелее, либо легче (это неизвестно) Есть весы, которые бывают в 3-х положениях "больше", "меньше" и "поровну" Есть 3 взвешивания, которые можно сделать

Необходимо определить какой из шаров - имеет аномальную массу

Вот попробовал её решить и не выходит ничего. Кто -нибудь знает есть ли у неё решение вообще? Вот чувствую что дело в положении весов "поровну". В лоб не решить,всего 3 взвешивания.

Тю! Делим пополам, взвешиваем. на третьей попытке получаем три шара - два на весах, один отдельно. Если равновесие - то ...

2sanykrimea
А если нет?

Flier написал : В лоб не решить,всего 3 взвешивания.

Два раза делить на ДВЕ кучки, один раз на ТРИ.

В любой последовательности

Например: 4+4+4 -с одного взвешивания получаем кучку в которой неправильный шар. (взвешиваем две кучки. неправильный либо определиться а весах либо будет в оставшейся третей) Потом 4 два раза взешиваем пополам.

Или 6+6 3+3 1+1+1

Или

6+6 2+2+2 1+1

Muxa написал : Два раза делить на ДВЕ кучки, один раз на ТРИ.

Есть одна проблема.В условии задачи сказано

Flier написал : 12-й либо тяжелее, либо легче (это неизвестно)

Поэтому после первого взвешивания даже двух кучек идти дальше непонятно куда. Да и это уже будет 2 взвешивания из трёх отпущенных. Говорят что тот кто решит эту задачу за 2 часа того берут брокером на Лондонскую биржу,но это уже наверно легенда,приложение к этому бояну.

Хотя наверно я неправильно понял условия задачи.... Если считать одним взвешиванием взвешивание по кругу всех кучек тогда всё совсем по другому.

2sanykrimea

Flier написал : 12-й либо тяжелее, либо легче (это неизвестно)

Понял, понял, потому и стёрся.

2Muxa Засада в случае, если из трех кучек неправильный шар оказывается в одной из кучек на весах. Будет непонятно, в какой.

Flier написал : Есть одна проблема.В условии задачи сказано

Настаиваю на искажении передачи условий задачи.

Хотя.

Помечаем все шары. Делим на три кучки 4+4+4 Взвешиваем и записываем результат

Визуально представляем это

о о о о о о о о о о о о

Смешаем верхние два шара в любую сторону на один столбец

о о о о о о о о о о о о

Если аномальная кучка переползла то откидываем неподвижные пары Если осталась на месте то подвижные.

После чего оставшиеся 2+2+2 пополамим по высоте и сдвигаем (повторяя аналогичные действия)

Если аномальность переползла то это сдвинутый шар в новой аномальной кучке.

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

Думаю должно сработать, но проверять лень :)

Muxa написал : Настаиваю на искажении передачи условий задачи.

Собственно задачу эту я копипастнул отсюда. http://alexeymas.livejournal.com/27119.html Это известный в Украинском сегменте товарищ,и задача эта настолько ему нравится что он в объявлении о поиске программистов к себе на работу ставит её решение условием приёма.