Есть кучка из 1057 орехов. За одну операцию можно любую из уже имеющихся кучек разделить...

Question

Есть кучка из 1057 орехов. За одну операцию можно любую из уже имеющихся кучек разделить на две. Если при этом получатся две неравные кучки, то взимается штраф 1 рубль. Какова наименьшая возможная сумма штрафа, которую придется заплатить, чтобы получить 1057 кучек по одному ореху в каждом?

Answer 1

Деление до конца без штрафов возможно, если количество орехов в кучке будет какой-либо степенью двойки (2, 4, 8, 16, 32, 64, 128, 256, 512). Число 1057 - нечетно, следовательно, его можно представить <четное>+<нечетное>. При делении 1056+1 получим первый штраф. Число 1056 не является степенью двойки, поэтому необходимо опять поделить орехи на неравные кучки: 1024+32 (второй штраф). 1024 и 32 - степени двойки, значит дальнейшее разделение можно выполнить без штрафов.
Можно делить, например, так:
1. 1024 и 33 ореха (штраф 1 рубль)
2. 33 делим на 2 кучки: 32 и 1 (штраф 1 рубль)
3 и все следующие операции: кучки из 1024 и 32 орехов делим на равные кучки (1024: 512 и 512, 512: 256 и 256, 256: 128 и 128, 128: 64 и 64, 64: 32 и 32, 32: 16 и 16 и т.д.).
Получаем, что минимальная сумма штрафа = 2 рубля.