I am attempting to solve a problem where Jellyfish has (n) green apple pieces, each weighing 1 kg, and she aims to distribute them equally among (m) people, given (n < m).
Using a magic knife, Jellyfish can divide each apple into two smaller pieces, each with half the weight of the original. The objective is to determine the minimum number of operations needed to ensure each person receives an equal total weight of apple pieces.
My initial observation involves dividing each apple into a power of 2 parts, denoted as $(g_i)$. So, for $(n)$ apples divided into $(g_i)$ parts each, the expression $(2^{g_1} + 2^{g_2} + \ldots + 2^{g_n}) \% m = 0 $. This signifies that $(m)$ must be a multiple of 2.
However, I'm uncertain about the next steps or additional conditions required to ensure an equal distribution among the people given (n < m). Could someone guide me further in determining the conditions under which there would be no solution to achieve an equal distribution?how to find the sufficient condition for which there is no solution?
If the apple pieces must be completely distributed (no leftovers), then each person will receive a weight of $\frac nm$ kg. If you give someone two pieces of the same size, that just means you could have skipped one cutting of a piece of the next-larger-size in two, and just given that person the uncut piece. So with no wasted cutting, each person will receive at most one piece of any given size. So the total amount given to a person will be $\frac{d_1}2+ \frac{d_2}4 + \frac{d_3}8 + \dots$, where the $d_i$ are all either $0$ or $1$. This is a binary number. Since every person receives the same weight, it is the same binary number for all of them, which must be $\frac nm$ in binary.
So express $\frac nm$ in binary, and it will tell you what cuts you need to make. If you are allowed to make an infinite number of cuts, there is no restriction on the size of $m$. But for a finite number of cuts, this will require that if $\frac nm = \frac pq$ with $p$ and $q$ relatively prime, then $q = 2^k$ for some $k$.
For example. If there are $16$ people and $7$ apple pieces of $1$ kg each, then $\frac 7{16} = \frac{111_2}{10000_2} = 0.0111_2$. So,
Give each person one each of the $0.25, 0.125,$ and $0.0625$ kg pieces.
As you can see, the easy algorithm is just to cut all pieces until you have at least $m$, all the same size. Hand out $m$ pieces, then resume cutting until you have at least $m$ more. Repeat until you have no leftovers (or forever, if you fail to limit your guests to a power of $2$ times some divisor of the kg of apples you have available).