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

Question

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

Answer 1

Для того, чтобы получить наименьший штраф, делим так, чтобы в одной из кучек получилось орехов с количеством, равным степени числа 2. То есть 512 (2 в 9 степени). Во второй получаем 577-512 = 65 (это первый штраф). 512 делим до конца на 2 без остатка. Там штрафов нет. 65 делим так, чтобы снова осталось наибольшее число, равное степени 2. Это 64 (2 в 6 степени). Во второй остаётся 1 орех. (это второй штраф). 64 можем делить на равные части до конца.
Итого получаем 2 штрафа.