Fall 2016, problem 33
Comments
Using Michel's naming, our starting point is that Nk <= n and N1 >= n.
A. If Nk = n, then we can fill completely a single box with all objects of color k, and all objects of color k are packed.
B. If not, then we have Nk < n : The smallest group of objects of the same color, which is of color k by definition, is of less -strict- than n objects. Based on this, we can put all objects of color k in a single box (Nk < n), and complement this box with n - Nk objects of color N1. This is easy because there are more than n objects of color 1 (N1 >= n), so no problem to find n - Nk of them. With this method, we have filled completely 1 box with 2 colors only, and all objects of color k are packed.
Even A or B lead us to the following situation: We now have 1 filled box with at most 2 colors, k-1 empty boxes, n(k-1) objects, and k-1 colors left. This is exactly the initial situation, with k-1 and n, plus this filled box.
By decreasing recurrence on k, at each step, we reorder the number of colored objects left unpacked, we apply the same method (with situations A or B), and we reach the final situation where we have: k-1 boxes filled with at most 2 colors, 1 empty box, n objects, and 1 single color left. Then the last box can be (and is to be) filled with this single color.
By recurrence, we have demonstrated a method through which the nk objects are packed in the k boxes so that each box holds objects (n objects) of at most two colors.
The problem tells us that at most two colours may be packed in each box, however it didn't tell us if they must be at least 2 different colours in each box.
Let put the problem that way, if we use a matrix A with the following dimension:
A = n x k
All the elements of the matrix are evidentily, n.k = number of objects , and we'll give for each different colour a letter. There is as much colour as there is boxes, hence we can stock in each box 1 colour no matter k or n.
We can use for instance n=3 et k=3
a b c a = first colour
A= a b c b = second one
a b c c= third one
We'll find the same result for every n and k positive integers.
Now if they must be at least AND at most 2 different colours: There is 2 options
1) k mod 2 = 0 2) k mod 2 != 0
1) k mod 2 = 0
pair each colomn by 2 and switch randomly colour between them
2) k mod 2 !=0
For this one, 1 column will have only one colour and use the same technique as 1) for the rest of it.
Sorry for the faults i'm not a native speaker and i really hope that you can understand my "demonstration" asbolutly not rigourous.
Have a nice day
Using Michel's naming, we can state that: A. If Nk = n, since each Ni >= Nk by definition, it is easy to demonstrate that each Ni = n, and we can apply the trivial solution of 1 single color per box. B. If not, then we have both situations where Nk < n (The smallest group of objects of the same color, which is of color k by definition, is of less -strict- than n objects). And the other situation is that, at the same time, N1 > n (The greatest group of objects of the same color, which is of color 1 by definition, is of more -strict- than n objects). Based on this, we can put all objects of color k in a single box (Nk < n), and complement this box with n - Nk objects of color N1. This is easy because there are more than n objects of color 1, so no problem to find n - Nk of them. This leads us to the following situation: We now have k-1 empty boxes, n(k-1) objects, and k-1 colors left. This is exactly the initial situation, with k-1 and n. By decreasing recurrence on k, we reach the final situation where we have: 1 empty box, n objects, and 1 single color. Then the last box can be (and is to be) filled with a single color. By recurrence, we have demonstrated a method through which the nk objects can be packed in the k boxes so that each box holds objects (n objects) of at most two colors.
First we call Ni the number of objects coloured i . Clearly Sigma from 1 toK(Ni) is equal toNxK If all the Ni are equal, then we are done because Ni=N and each box contains objects of the same colour.
If they are not equal then WLOG we order them with N1 larger than N2 itself larger than N3 etc...Clearly N1 is larger than N and NK is smaller than N.
We now follow this procedure:
-In box BK put the NK objects coloured K and complete with N-NK objects coloured 1;Then Box BK is coplete and contains two colours only. -Then if there are more than N objects coloured 1, complete the next boxes BK-1, BK-2 etc... until the number of objects coloured 1 is less than N -Then take in turn N2 and complete the box containing the smallest number and start the process as above
The process stops when there is only one colour whose number of objects is larger than N. Let us call this colour m then the surplus N-Nm can be shared with the remaining boxes which are not full.
In so doing all boxes will be full with at most two colours; (Bm contains only colour m but some objects of Bm can be exchanged with Bm+1 so that the two boxes contain strictly two colours m and m+1.
As I do not master Latex, I did not use mathematical symbols like subscripts etc... so You have to bear with me and consider that NK is not NxK but Nsubscript K !
Proof is by induction on k, the result being obvious when k=1. Assume we can always solve the k-1 box problem.
For the k box problem, let c be the color with the fewest number of objects, and r be the color with the greatest number of objects. There are at most n ojects colored c, and at least n colored r. Place all of the objects colored c into a box, then fill the rest of the box with objects colored r. There are now n(k-1) objects remaining, coming in one of k-1 colors, and k-1 boxes to be filled. By the inductive hypothesis, this can be done.