Решение задачи о взвешиваниях

В августе мы решали задачку о взвешиваниях (если помните, надо было найти минимальное количество гирек, чтобы отмерить любой целый вес от 1 до 40 килограммов чашечными весами). Тогда я подробно рассказал оценку минимума, но очень коротко прошёлся по построению примера, его реализующего. Месяц назад в комментарии к той заметки был задан вопрос, как найти такое решение, не проводя большого перебора. Увы, я тогда не смог сразу ответить (помешало большое количество других дел), поэтому отвечаю сейчас.

Когда мы поняли, что одна гирька x килограммов позволяет нам отвесить -x, 0 и x килограммов, то сразу же пробуем понять, что это значит для гирьки массой 1 килограмм.

Оказывается, если у нас есть гирька в один килограмм, то мы можем отвесить -1, 0 и 1 килограмм - это три веса «подряд». Теперь, если мы добавим ещё одну гирьку массы x, то мы сможем измерять не только вес x, но и x-1 и x+1 (то есть, гирька в один килограмм увеличивает «наш обзор» в три раза). Само собой, ещё мы сможем измерить -x-1, -x, -x+1, -1, 0, 1. В такой ситуации вполне естественным ходом было бы попробовать взять гирьку весом 3 килограмма (чтобы не было разрывов между этими тремя покрытыми интервалами).

Смотрите сами, мы покрываем так сразу девять весов подряд:
-3-1, -3, -3+1,
-1, 0, 1,
3-1, 3, 3+1.

Далее, раз мы уже покрыли 9 весов подряд, хочется добавить гирьку 9 килограммов, чтобы «сдвинуть» этот ряд дальше (но не создать разрыв). Легко видеть, что это позволяет покрыть все веса от -9-3-1=-13 до 9+3+1=13 - 27 весов. Когда мы возьмём гирьку 27 килограммов, то увидим, что можем измерить всё от -40 до 40 килограммов. Хоть отрицательные веса нам не интересны, с задачей мы успешно справились:
- доказали, что меньше четырёх гирек для выражения любого целого веса от 1 до 40 килограммов не хватит,
- предъявили такой минимальный набор из четырёх гирек.

Есть одна тонкость: это решение удалось построить так легко, потому что был правильно угадан вес самой лёгкой гирьки (1 килограмм). В некоторых задачах такое предположение не позволяет получить хороший пример, поэтому приходится пробовать с другими весами (2, 3...). Задачи такого типа часто решаются интуицией, а её можно развить только победив несколько десятков задачек. Успехов вам в этом!