Consider the following algorithm that takes a set $S$ of $l\leq n$ positive integers with sum $l\cdot n$ and returns a set of $l'\leq l-1$ positive integers with sum $l'\cdot n$ (call it an $n$-flow): Consider the maximal and minimal elements of $S$ (say $a\in S$ and $b\in S$ respectively). Delete $b$, replace $a$ with $a+b-n$. If any of the entries of the resulting set are $n$, delete them as well. (In particular, the output is also a subset of $\mathbb Z^+$.) Let $c_1,c_2,\dots,c_n$ be the $n$ colors, and let $a_1\leq a_2\leq \dots\leq a_n$ be the number of ornaments of the corresponding color. Repeatedly applying the "n-flow" to $S=\{a_1,a_2,\dots,a_n\}$ will eventually result in the empty set; it is not hard to see how this leads to the desired result.

Alias algorithm solves this problem immediately.

we rephrase the question to question wrote: Let $n$ be a positive integer. On the table, we have $n^2$ marbles each of which is one of $n$ colours, but not necessarily $n$ of each colour. Prove that they may be placed in $n$ boxes with $n$ marbles in each box, such that each box contains marbles of at most two colours. We solve for the more general problem, that is, to consider $cn$ marbles each of which is one of $c$ colors. We will prove that they may be placed in $n$ boxes with $n$ marbles in each box, such that each box contains marbles of at most two colors. We induct on $c.$ When $c = 1,$ this is trivial. Assume it is true for some $c,$ then this implies the case for $c+1.$ We consider a $(c+1)n$ rectangle, we represent each box as a column of this rectangle, thus the task translates into filling this $(c+1)n$ rectangle such that the columns contain marbles of atmost 2 colors. When not all $c+1$ colors are used, then we just put any other color in the $c+1$th column and then by the induction hypothesis, we can complete the remaining $cn$ rectangle. When all $c+1$ colors are used, Notice that then you can't have the number of marbles of each color $> n.$ Thus at least one number of one colored marbles must exist that is $\leq n$ Then you just pick that color to tile the $c+1$th column and any other color if the number is $< n,$ and then we can just tile the remaining $cn$ rectangle with $c$ colors from the induction hypothesis. Hence our induction is complete. Now, we just pick $c=n$ and win.

Note ornaments = balls in the solution below.

We prove a more general statement: If we have $nk$ ornaments which consists of $k$ different colours, then we can partition them into $k$ disjoint groups such that there are exactly $n$ ornaments in each group and there are at most $2$ different colours in each group. We induct on $k$. For $k = 1$, it is clear. Assume true for $k-1$, we will prove it for $k$. Let the colours be $1,2, \dots , k$ and let there be $a_i$ ornaments of the $i$ th colour. Assume wlog that $a_1 \geq a_2 \dots \geq a_k$. If there exist a $j$ such that $a_j < n$, then use $a_1$ and $a_j$ to form a group so that we use all of the ornaments of $j$ th colour.(We can do this since $a_1 \geq n$) So, now we have $k-1$ colours and $k-1$ groups left over, and there are $n(k-1)$ ornaments, so by the induction hypothesis, we can partition the rest. If there doesnt exist a $j$ such that $a_j < n$, then we must have $a_j = n$ for all $j = 1,2 \dots , k$, and thus it is trivial that we can partition those as well. So we are done.

Replace ornaments and trees with marbles and boxes. We proceed with induction on the number of boxes. To clarify, when there are $k$ colors, there exist $nk$ marbles and $k$ distinct boxes, each able to contain $n$ marbles. Base Case: When $k = 1$, we place all the marbles in the only box. Inductive Hypothesis: Assume a valid set of marbles can be placed in a satisfactory manner for $k = m$. We will prove the hypothesis for $k = m+1$. Induction Step: If there are exactly $n$ marbles in each of the $m+1$ colors, then we place all $n$ marbles of each particular color in the same box. Otherwise, there exists colors $X$ and $Y$ covering $b < n$ and $d > n$ marbles respectively. In this case, we place all $b$ marbles colored $X$ and $n - b < n < d$ marbles in color $Y$ inside a box. This leaves $n(k+1) - n = nk$ marbles in $k$ distinct colors, as there still remain $d - (n - b) > 0$ marbles colored $Y$. At this point, the Inductive Hypothesis suffices. $\blacksquare$ Remark: We are motivated to induct on the number of colors, as keeping the number of marbles per box constant is helpful for applying Pigeonhole. Furthermore, having exactly $n$ colors doesn't seem too important anyways.

Note ornaments = marbles in the solution below We consider the following generalised problem Prove that if we have $nk$ marbles of $n$ colors, they may be placed in $n$ boxes with $k$ marbles in each box, such that each box contains marbles of at most two colors. We induct on $n$. Note that for the base case $n=2$ pretty much anything works since there are only $2$ colors anyway. Let the above statement be true for some $n$. We prove it for $n+1$ Consider the case where there are $k$ marbles of each color. Note that this is obvious since we can just put these $k$ each in the boxes and we are done. Thus by PHP if not all $n+1$ colors have the same number of marbles, we we must have some color with at most $k-1$ marbles, and some with atleast $k+1$ marbles. Consider the color with minimum marbles $= m \leq k-1$ and the color with maximum marbles $= M \geq k+1$ Select all $m$ marbles from the minimum color and $k-m$ marbles from the maximum color (note that $k-m$ can be taken) and put these $k$ marbles into one of the boxes. We are now left with $(n+1)k-k = nk$ marbles of $n+1-1=n$ colors (since the minimum color one is gone) to be put in $n$ boxes with capacity $k$ each which is clearly possible by our induction hypothesis Moreover, taking $n=k$ in our generalized problem we get the required result.

We prove this statement inductively. For $n=2$ this follows directly. Now, assume we can hang the ornaments accordingly for $n-1$. By the pigeonhole principle there must be a color $A$ with less than or equal to $n$ ornaments, so let's hang all of these on the same tree $\mathcal{T}$. Now, there is also a color $B$ with more than or equal to $n$ ornaments. We hang as much as possible of these ornaments on $\mathcal{T}$, and now we have reduced the situation to $n-1$. We are done!

Nice problem considering the time of year. We will solve the problem for the more general configuration, where there are $nk$ ornaments, $k$ trees that hold $n$ ornaments, and $k$ colors. It is easy to see the statement holds true when $n=2$. Denote $c_i$ as the number of marbles of color $i$. For any set of ornaments, always rename them so that $c_1 \le c_2 ... \le c_k$. Assume that $c_k> c_1$, or else we could easily finish by each tree having $n$ ornaments. By Pigeonhole, $c_k > k > c_1$. Hence, we could fill up one tree where there are $c_k - c_1$ ornaments of color $k$ and $c_1$ ornaments of color $1$. Now there are $n(k-1)$ ornaments left, and $k-1$ trees. Using induction the result follows. $\blacksquare$

The main claim is the following: Claim. After filling $k$ boxes according to the condition, we can always guarantee that $k$ colors are eliminated. Proof. We may proceed inductively. Notice that after filling any $k$ boxes, by the inductive hypothesis there are only $n-k$ remaining colors, while there are $n^2-nk$ remaining marbles. This means that there exists at least one color occupying at most $n$ marbles and one color occupying at least $n$ marbles. The former color can be eliminated by being placed in a box with marbles of the latter color, as required. $\blacksquare$ However, this guarantees that there will always be a color occupying at least $n$ marbles, so it is always possible to fill another box. This implies all $n$ boxes can be filled.

Let there be $x_i$ balls of color $C_i$ and suppose $k$ colors have their $x_i$ less than $n$. The following algorithm works: Place these $k$ colors alone in boxes $A_1, A_2 , A_3 \cdots A_k$.Now take a color of which there are more than n balls. With this color , say $C$ , fill up the rest of $A_1$.If enough balls are left , fill up the rest of $A_2$..suppose after having successfully filled up $i$ boxes , the number of balls of color $C$ left is not sufficient to fill up $A_{i+1}$.Now put these remaining balls of color $C$ in box $A_{k+1}$. Now take up another color with more than $n$ balls and repeat the procedure starting from $A_{i+1}$ and repeat , and at the end put the leftover in box $A_{k+2}$. And if there are no colors with less than n balls initially , then consider the $A_i$' s at the beginning empty and do the same process

OTIS Version wrote: Let $n$ be an integer. There are $n^2$ marbles, each of which is one of $n$ colors, but not necessarily $n$ of each color. Prove that they may be placed in $n$ boxes with $n$ marbles in each box, such that each box contains marbles of at most two colors. We prove the more general version of the problem, that if there are $kn$ marbles of at most $k$ colors, then they may be placed in $k$ boxes with $n$ marbles in each box, such that each box contains marbles of at most two colors. Proceed with induction on $k$, with base case obvious. Let there be at most $n$ marbles of color Amaranth and at least $n$ of color Viridian. First, use up all the Amaranth marbles and finish the box by adding Viridian marbles. Then, $c$ is reduced by one, which finishes.

also doing the otis version, with marbles and boxes instead of ornaments and trees

gracemoon124 wrote: also doing the otis version, with marbles and boxes instead of ornaments and trees We define a move as a placement of $n$ marbles into a box (obviously we will make $n$ moves by the end of the process). We claim that we can remove all of the marbles of a certain color on each move. This would prove the result as there are $n$ moves and $n$ colors. We develop a strategy to remove a color on each turn. Consider a certain move. We take the color with the smallest number of marbles $k$, and pair those with $n-k$ marbles of the color with the most number of marbles. This will remove all of the marbles of the color with the smallest number of marbles. This is always achievable since if there are $n$ marbles in the smallest color every other color will have $n$ marbles. Similarly the largest pil will always have at least $n$ balls. $\blacksquare$ This was my favorite problem in a very long time. I think that my solution is quite unique

Math4Life7 wrote: gracemoon124 wrote: also doing the otis version, with marbles and boxes instead of ornaments and trees

fun problem

Generalize the problem to $mn$ ornaments, $m$ colours, and $m$ Christmas trees of size $n$. We will induct on $m$. Base case: $m = 1$. There is only a single tree. Put all the $n$ ornaments (which are of a single colour) in it. Assume it is possible till $m-1$. Now, for $m$: Case 1: Suppose there are exactly $n$ ornaments of each colour. Then put all the ornaments of each colour on a particular tree. Done. Case 2: There is at least one colour (call it a small colour) of which there are $< n$ ornaments $\Leftrightarrow$ there is at least one colour (call it a big colour) of which there are $> n$ ornaments . Take a small colour and put all of its ornaments on a tree. Fill the rest of the tree with ornaments of a big colour. Now we have used up $n$ ornaments, filled $1$ tree, and gotten rid of $1$ colour. We are left with $mn - n = n(m-1)$ ornaments, $m-1$ boxes and $m-1$ colours, so we are done by our inductive assumption.

Note that when trying to induct on $n$, both the number of colors and the number of boxes change, which is complicated. Hence we try to fix the number of marbels in the boxes to $n$ and induct on the number of colors $c$. The result then follows by letting $c=n$. Consider a $c\times n$ rectangle, so that we have $c$ colums. Hence, we wish to prove if that we have at most $c$ colors, then can fill a $c\times n$ table in such a way that there are no more than two colors in each column. The base case $c=1$ is clear. Assume that the result is true $c$ colors. Then add another column to the table, so that we can choose marbles of $c+1$ different colors. If all the $c+1$ colors are used, note that there must exist a color $k$ such that the number of marbles with color $k$ is a most $n$. Put them in the last column and fill the rest of the column with another color, which is clearly always possible. Now we have $c$ columns remaining and marbles of $c$ different colors, so by the induction hypothesis, we can fulfill our wishes. If not all $c+1$ colors are used, put one color in the last column, and thus we have at most $c$ colors to put in the remaining $c\times n$ table, which we can do by the induction hypothesis.

We generalize the problem as follows: Quote: Let $n$ be a positive integer. On the table, we have $mn$ marbles in $m$ different colours, not necessarily $n$ of each colour. Prove that we can put the marbles on $m$ boxes in such a way that there are exactly $n$ marbles in each box and the marbles in every box are of at most two different colours. We give an inductive arguement. For $m=2$, the problem is obvious. At any step, let the color A with smallest number of marbles be $k$ and color B with largest number be $K$. Then, $k\leq n$ and $K\geq n$ is forced. We fill an unfilled box with $k$ marbles of color A and $n-k$ marbles of color B. This is possible, as $n-k<n\leq K$. So, we essentialy completely use one color and completely fill one box and reduce the total number of marbles from $mn$ to $mn-n=(m-1)n$. Hence, $m$ is reduced to $m-1$. The induction is complete.

OTIS wrote: Let $n \ge 2$ be an integer. There are $n^2$ marbles, each of which is one of $n$ colors, but not necessarily $n$ of each color. Prove that they may be placed in $n$ boxes with $n$ marbles in each box, such that each box contains marbles of at most two colors. We prove a more general statement. Claim: If $cn$ marbles of at most $c$ colors are placed in $c$ boxes with $n$ marbles in each box, they can be placed in a way such that each box contains marbles of at most two colors. Proof: We will prove this by induction. The base case $c=1$ is vacuous. Assume the inductive statment holds for $c=k$. Out of those $k$ colors, say there are at most $n$ marbles of color $C_1$ and at most $n$ marbles of color $C_2$. Simply put all of the $C_1$ marbles in one box and fill with $C_2$ marbles if necessary. Then, remove that box and we are left with a figuration for $c=k-1$, completing the induction. $\square$

Claim: It is possible to place $kn$ marbles of $k$ colors into $k$ boxes with $n$ marbles each such that each box contains marbles of at most 2 colors. We prove this generalized assertion using induction on $k$. Note the base case $k=2$ is trivial. We show our claim is true for $k=m$ if $k=m-1$ holds. By Pigeonhole, there exists one color $A$ with at most $n$ marbles and one color $B$ with at least $n$ marbles. Isolate the marbles of color $A$ into one box and fill it to $n$ marbles using color $B$. The remaining marbles form the case $k=m-1$, as desired. $\blacksquare$

Induct downwards. If at any point there are exactly $n$ ornaments of a color, remove that color by placing all ornaments on a tree, reducing our problem to $n^2-n$ ornaments of $n-1$ colors, with $n-1$ trees. Now we can assume we have $k$ colors at some step in the process, with $n^2 - kn$ ornaments, where each color has strictly greater than, or less than $n$ ornaments. Now take the color with the minimal number of ornaments say $X$, and place them all on a tree. Fill the remaining spots with the color with the maximal number of ornaments. Hence, we remove $1$ color, $1$ tree and $n$ ornaments, inducting down to $n^2-(k+1)n$ ornaments, and $k-1$ colors.

Consider a method to hang the ornaments on $n$ Christmas trees satisfying the given conditions. Firstly, arrange the ornaments into $n$ groups such that each group consists of $n$ ornaments of the same color. If there are fewer than $n$ ornaments of a particular color, add additional ornaments of that color to complete the group. Next, for each group, distribute the $n$ ornaments across $n$ trees as follows: For the first tree, hang $n$ ornaments of that color. For the second tree, hang $n$ ornaments of a second color, different from the first color. If there are fewer than $n$ ornaments of this color, use ornaments of a third color to complete the set. Continue this pattern for the remaining trees, ensuring that each tree has $n$ ornaments, with at most $2$ different colors on each tree. Since there are $n$ different colors and we're distributing $n$ ornaments of each color across $n$ trees, we're guaranteed to have exactly $n$ ornaments of each color on each tree. Additionally, since we're using at most $2$ different colors on each tree, the conditions of the problem are met. Therefore, we've shown that it's possible to hang the ornaments on $n$ Christmas trees such that each tree has exactly $n$ ornaments, and the ornaments on every tree are of at most $2$ different colors.

[Note: The version of the problem I was given is with boxes and balls] Assume exactly $n$ distinct colors, since less distinct colors can't make our situation worse. Let $a_1, a_2, \dots, a_n$ be the number of marbles of each color. We use the following algorithm: While $a$ is not empty, do the following: Take the color with minimum $a$ value, and take the color with maximum $a$ value, and combine them into one box ($\text{mn}$ marbles of first color, and $n - \text{mn}$ marbles of second color), for this we need $\text{mx} + \text{mn} > n$, which we'll prove later. Now, remove every color from $a$ which has $0$ marbles. Proof for $\text{mx} + \text{mn} > n$: We will show this by induction. It is obviously true for before the first operation, since $\text{mx} \ge \text{avg} \ge n, \text{mn} \ge 1 \implies \text{mx} + \text{mn} > n$. Now, assume it is true before the $k$th operation. Then, we must have $\text{mx} + \text{mn} > n$. Now, since $\text{mx} > n - \text{mn},$ the color corresponding to $\text{mn}$ is the only color which becomes $0$, so the number of distinct colors decreases by exactly one, and the number of marbles decreases by exactly $n$, so if the average was $n$ before, it is $n$ now also, so $\text{mx} \ge \text{avg} = n, \text{mn} \ge 1 \implies \text{mn} + \text{mx} > n,$ done! Also, at each step our algorithm decreases the sum by $n$, so there is exactly $n$ iterations, and hence exactly $n$ boxes used, and it is easy to see that the way our algorithm filled the boxes is valid.

Claim: We can always guarantee that k colors are fully utilised when we fill k tree. Proof)Base case is easy to prove Lets assume it is true for k boxes. Let the remaining$n-k$ colors be $c_1,..c_n-k$. Observe that there will be an index such that $N(c_i) < n$.Therefore we would be done, but if there doesn't exist then it will imply that all are equal to n. We would be done due to this also. Therefore by our above claim, we will fill $n-1$ boxes and the last tree will be filled by ornaments of the same color

Consider the following algorithm to colour a tree: Take the colour present in least amount and hang all ornaments of that colour on a singular tree. (There are less than n such ornaments so we can definitely do this). Say that there are $k$ ornaments on the tree now. To hang ornaments on the remaining part of the tree, take ornaments of the colour that, among those with frequency $\ge n - k$, is present in the lowest frequency. (This again exists as there exists a colour with $\ge n$ ornaments.) Repeat this process on all trees. Clearly there are at most two colours used per tree, and each tree has $n$ ornaments. So this algorithm works.

(Solved version of problem that involved marbles and boxes instead of ornaments on trees) Generalize to $mn$ marbles and $m$ different colors. We will downwards induct on $m$, which is sufficient. Our base case of $m = 1$ is clearly true. For our induction, assume it is true for $m - 1$. By Pigeonhole, there is a color so that there are $\geq m$ marbles of that color, and similarly there is a color so that there are $\leq m$ marbles of that color. We can take all of the marbles of the color that has $\leq m$ marbles and put it in a box, and fill the remaining space(possibly none) with the color of marble with $\geq m$ marbles. This reduces the number of colors by $1$ and reduces the number of marbles by $m$, so we are done.