Chekanovo Y. Y.

n schoolchildren want to divide $m$ identical chocolate bars equally, with the condition that each chocolate bar can be broken no more than once.

a) For which $n$ is this possible if $m=9$?

b) For which $n$ and $m$ is this possible?
b) Arrange $m$ chocolate bars in a line and cut the resulting chocolate strip evenly into $n$ equal parts. We will assume that the length of a chocolate bar is $n$. Each student should receive a portion of length $m$. If $n \leq m$, then the length of the portion will be no less than $n$. Therefore, no more than one cut will pass through each chocolate bar.

Let $n=m+d$, where $d$ is a divisor of $m$. In this case, the length of the portion is $n-d$. With the described method of division, each chocolate bar is divided into parts whose lengths are multiples of $d$, meaning the distance from the cut line to the edge of the chocolate bar is no less than $d$. Two cuts passing through the same chocolate bar would cut out a piece no larger than $n - 2d$, which is less than the portion. Therefore, each chocolate bar will be cut no more than once.

We will prove that there are no other pairs $(n, m)$.

First method. Let $n=m+d$ and it was possible to divide the chocolate bars while meeting the conditions. We will prove that the lengths of all pieces, and therefore $m$, are multiples of $d$. Suppose this is not the case. Consider the piece of the smallest length $r$ that is not a multiple of $d$. Then there is a piece of length $n-r$. The student who received it also received a piece of length no greater than $m - (n-r) < r$, which is not a multiple of $d$. Contradiction.

Second method. Consider a graph where the vertices correspond to students, and the edges connect two students who received pieces from the same chocolate bar. Let a connected component of this graph have $n'$ vertices and $m'$ edges. This means that $m'$ chocolate bars are distributed among $n'$ students, i.e., $m' / n' = m / n$, or $m = d m'$, $n = d n'$, where $d$ is a rational number. On the other hand, due to connectivity, $m' \geq n' - 1$. Since $m' < n'$, then $n' = m' + 1$, i.e., $n = m + d$. From this, it is clear that $d$ is an integer and $m$ is a multiple of $d$.

## Answer

a) For $n=1,2,3,4,5,6,7,8,9,10,12,18$; b) when $n \leq m$ or when $m < n$ and $m$ is divisible by $n-m$.

Submit a comment