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