Question

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

Answer 1

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