November 2016
<<October November December>>
You can solve this challenge by writing a computer program, but Motty Porat (Thanks!) sent us a great solution - solving it without a computer.
Here is his solution:
This challenge looks crazy, but some observations can simplify it.
First and foremost, to match two chefs, we don't have to check all their six permutations but only the sorted ones. That is, if chef1 divides the shifts to x1<y1<z1 (x1+y1+z1=N) and chef2 divides to x2<y2<z2, then:
— If they are equal in one dimension, they draw, e.g., 1,2,6 and 0,2,7
— Otherwise, the chef that surpasses the other in two dimensions wins, e.g., 2,3,4 beats 1,2,6 (because 2>1 and 3>2. It doesn't matter that they both contain 2, as it's in different places).
We can draw each chef on the XY plane, with the boundaries:
0 < x < y
y < z = N-x-y => 2y < N-x => y < (N-x)/2
I won't draw the boundaries yet, for convenience.
Fix chef1 (Jan) at some point. The chefs that lose to him (such as Feb) must satisfy exactly two of these relations:
x2 < x1
y2 < y1
z2 < z1 => N-x2-y2 < N-x1-y1 => x2+y2 > x1+y1
Let's assume that z1 = z7
(we'll check the other options too)
Thus x1+y1 = x7+y7.
Chefs 2-6 (Feb-June) must be in the green-only areas, because they lose to Jan and beat July. Similarly, chefs 8-12 (Aug-Dec) must be in the blue-only areas. Depending on the direction of chefs 1 & 7, the green areas lie beyond the left and right sides of the 1-7 square and the blue areas are above and below the square (case I), or vice versa. Since the year is cyclic, we can assume case I, w.l.o.g.
Corollary: All the pairs that draw, draw at the same dimension
Chefs that draw are equal in one dimension. We assumed that Jan & July have z1 = z7, and found that the valid points for Feb share neither x nor y coordinate with those of Aug, so they must have z2 = z8.
As for the direction between chefs 2 & 8, they again have two options: parallel to 1-7 (case I.a) or antiparallel (case I.b).
The valid areas for chefs 3-6 (and 9-12), are the intersection of the green (and blue) areas that are induced by the 1-7 square and by the 2-8 square.
If we place all the pairs in parallel (case I.a), then in order to take the minimal area, we should move just one unit down-left each time. The solution will look like this:
(The numbers are month, in Hex)
1 2 3 4 5 6 7 8 9 A B C
If we choose to apply case I.b, we can do it only once, and the solution will look the same but with rotated order, e.g.,
3 4 5 6 1 2 9 A B C 7 8
Now, at which dimension do the pairs draw?
We assumed that all the pairs drew at Z (z1=z7), and sketched the projection on the XY plane. Clearly, if we examine the other two options, the diamond shape of the solution won't change. But now let's see what the boundaries (0<=x<y<z, x+y+z=N) look like.
So the solution is: N = 42
Sous chefs:
5, 18, 19
4, 17, 21
3, 16, 23
2, 15, 25
1, 14, 27
0, 13, 29
11, 12, 19
10, 11, 21
9, 10, 23
8, 9, 25
7, 8, 27
6, 7, 29
And if you want to add another constraint that all N1,N2,N3 are non-zero, then the best solution (thanks, Aviv Nisgav) is
1,14,30
12,13,20
11,12,22
10,11,24
9,10,26
8, 9,28
7, 8,30
6,19,20
5,18,22
4,17,24
3,16,26
2,15,28