Цитата из: Erlom-Tiu on 23-02-2003, 17:27:54
Цитата из: Chitatel on 23-02-2003, 11:36:44
Собственно, задачку-то можно и не решать, а вспомнить теорию кодов с коррекцией ошибок. Аналогия между взвешиванием и контрольной суммой вполне прозрачна, верно?
честно говоря, не совсем
Я предполагал примерно такую модельку: есть числа от одного до шести. Они нам передаются с возможным искажением. Чтобы отследить, были искажения или нет, передаются дополнительные соотношения между этими числами ("контрольные суммы"). Мы принимаем числа, вычисляем дополнительные соотношения и понимаем, было искажение или нет.
Например, тривиальные соотношения: 1 < 2 < 3 < 4 < 5 < 6.
Проверим их все - получим ответ, были искажения или нет.
Но в данной задаче можно указать меньше "контрольных сумм", чем в общем случае. В ней есть доп. информация, поэтому моя реплика, будто достаточно вспомнить теорию кодирования, отзывается за неверностью
Между прочим, эту информацию наверняка надо использовать, чтобы уложиться в два взвешивания - я сначала не обратил внимания. Подумаю теперь еще
Цитата:
Двумя - можно попробовать
.
Если можно, ответ из 3-х взвешиваний сюда или в приват.
Ну, раз он неоптимальный, так чего ж не опубликовать. Мне их несколько пришло в голову, но в итоге остался этот.
Вот соотношения:
(1) 1 + 2 + 3 + 4 < 5 + 6
(2) 1 + 2 < 4
(3) 1 + 5 < 3 + 4
Проверяем их по очереди, выставляя на весы гири с соответствующими номерами. Если каждый раз гири показывают правильное неравенство, то веса всех гирь равны их номерам. Естественно, как только взвешивание покажет не тот результат, алгоритм останавливается с ответом "нет".
Подробнее: если (1) выполнено, то мы имеем две гири, которые тяжелее всех остальных. Значит, эти две гири принадлежат множеству A = (5, 6), а все остальные - множеству B = (1, 2, 3, 4).
Неравенство (2) мы проверяем после (1), т.е. убедившись в том, что самой тяжелой гирей множества B может быть только гиря весом 4. Если одна гиря из мн-ва В тяжелее двух других, то эта гиря 4 и есть, две легкие принадлежат множеству C = (1,2), а не участвовавшая во взвешивании - конечно, имеет вес 3.
Итого, после двух взвешиваний мы убедились в том, что гири 3 и 4 соответствуют своим подписям, и путаница может быть только между (1, 2) или (5, 6). В неравенстве (3) мы берем самые легкие гири множеств А и С, они в сумме должны весить 6. Если перепутаны гири хотя бы в одном из множеств, то вес будет 7, а если в обоих - то и вовсе 8. Положив 1 и 5 на одну чашу весов, мы на другую кладем уже проверенные 3 и 4. Из выполнения неравенства (3) получим, что все гири помечены верно.
И алгоритм останавливается с ответом "да".
