Задача 67425
|
|
 |
Условие
Если Вася делит пирог или кусок пирога на две части, то всегда делает их равными по массе. А если делит на большее число частей, то может сделать их какими угодно, но обязательно все разной массы. За несколько таких дележей Вася разрезал пирог на $N$ частей. При каждом ли $N$ ≥ 10 все части могли получиться равными по массе? (Объединять части нельзя.)Решение
Кусок массой $N$ (натуральное число) надо разбить на единичные куски. Все степени двойки разбиваются делением пополам. Для дальнейших рассуждений приведём два способа.Способ 1. Число $N$ разложимо в сумму различных степеней двойки (двоичное представление). Возможны три случая.
1) В этом разложении не два слагаемых (одно или хотя бы три). Тогда разбиваем сначала ровно как в этом двоичном разложении, а потом превращаем в единицы каждую степень двойки.
2) $N = 2^a + 2^b$, где 0 < $a < b$. Тогда $b$ ≥ 3, так как $N$ ≥ 10. Разбиваем $N$ на куски 1, $2^a$ и $2^b-1$, последний из которых – на $b$ степеней двойки (1, 2, ..., $2^b−1$).
3) $N = 1 + 2^b$. Тогда $b$ ≥ 4, и мы разбиваем $N$ на куски 1, 2 и $2^b-2$, последний из них – на $b-1$ степеней двойки (2, ..., $2^b-1$).
Способ 2. Многократно отделяя пару кусков 1 и 2, сведём задачу к куску 10, 11 или 12. Кусок 10 сведём к 7, затем к 4. Кусок 11 сведём к 8. Кусок 12 разобьём на 1, 4 и 7. Все полученные куски мы уже умеем разбивать.
