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

Question

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

Answer 1

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