Decorating And Cutting A Cake Fairly Imagine an N x N square cake you are tasked with decorating with N types of toppings (colors). You then with to share the cake equally amongst N friends. All pieces must be rectangular and have same the area. It's also only fair that no matter what kind of piece your friends have, they each have the exact same type of toppings. How should you decorate the cake so that no matter how you cut it, it's always a fair division?
For example below, the 4 x 4 case of 4 different colors for 4 friends:

Take any equal area rectangular cut and each will contain all four different colors:
  

It's not hard to see that any cut that's equal is a fair division by the definition above. Call any N x N coloring of this kind a fair division coloring.
Below are fair division colorings for 2 x 2, 3 x 3, and 5 x 5, 7 x7, and 9 x 9:
  
For N=p, p a prime, the coloring is trivial. However, I found it is impossible for N=6 and N=8. I used brute force methods and found that any coloring of 6 different colors for the 6 x 6 grid, there will exist a cut that doesn't create a "fair" division. The same is true for N=8.
My question: is there a general rule to determine for what N a fair division coloring of the square exists?
EDIT: I am absolutely confident this kind of problem has been studied before, but I'm not sure where to find a paper on this. I appreciate any and all thoughts on where I can look.
 A: Any square of size $n=pq$ with $p<q$ and $q$ not divisible by $p$ has no fair division colouring (so the only $n$ that have colourings are the primes and possibly some prime powers).
Let me first prove the case with $p=2$.
Proof:
Suppose $n=2m$, with $m$ odd. There are dissections which have the following rectangles at the top left corner: (shown for $m=5$, but holds for general $m$)
a                     b                     c
 X X X X X . . . . .   X X X X X X X X X X   O X X X X X . . . .
 X X X X X . . . . .   . . . . . . . . . .   O X X X X X . . . .
 . . . . . . . . . .   . . . . . . . . . .   O . . . . . . . . .
 . . . . . . . . . .   . . . . . . . . . .   O . . . . . . . . .
 . . . . . . . . . .   . . . . . . . . . .   O . . . . . . . . .
 . . . . . . . . . .   . . . . . . . . . .   O . . . . . . . . .

Let the colour of the top left corner square be red. There can be no other red square at any of the X's in dissections a and b above. Therefore the X rectangle in dissection c must have its red square at its bottom right corner (row $2$, column $m+1$).
Consider the dissections d and e below where there are vertical rectangles along the top row.
d                     e                     f                     
 A A B B C C D D E E   A B B C C D D E E F   R X X X X X X X X X  
 A A B B C C D D E E   A B B C C D D E E F   X X X X X R X X X X  
 A A B B C C D D E E   A B B C C D D E E F   1 2 3 4 5 6 . . . .  
 A A B B C C D D E E   A B B C C D D E E F   1 2 3 4 5 6 . . . .  
 A A B B C C D D E E   A B B C C D D E E F   1 2 3 4 5 6 . . . .  
 . . . . . . . . . .   A . . . . . . . . F   . . . . . . . . . .  
 . . . . . . . . . .   A . . . . . . . . F   . . . . . . . . . .  
 . . . . . . . . . .   A . . . . . . . . F   . . . . . . . . . .  

In figure f, there can be no red at locations marked 1 or 2 because of dissection d.
Dissection e forces a red at a location marked 3.
Dissection d eliminates red from locations marked 4.
Dissection e forces a red at a location marked 5.
Dissection d causes a contradiction cause it has a rectangle containing reds in column 5 and column 6.
This generalises to all odd $m$ -- the reds are forced to occur in the odd-numbered columns, and the last one clashes with the red in column $m+1$.
This proof generalises further. Suppose $n=pq$, with $p<q$.
The first part still works, and shows that there must be a red in column q+1, on one of the rows 2 to p.
The second part generalises too, and instead of two dissections you use $p$ dissections, establishing $q\times p$ rectangles at any x-coordinate along the top row, to prove that every column with a number $1$ mod $p$ must contain a red square in one of the top $q$ rows, which will conflict with the red in column $q+1$, unless $p|q$.
Therefore, any square of size $n=pq$ with $p<q$ and $p\not|q$ has no fair division colouring.

So this proves that any composite that is not a prime power has no fair division colouring (such $n$ can always be written as a product of coprime numbers, where one is smaller than the other).
There are clearly fair division colourings when $p$ is prime, and the fair division colouring given for $n=9$ should generalise to $n=p^2$.
The only undecided cases left are the prime powers $p^k$ with $k>2$. You've already shown that $n=8$ fails, so not all prime powers have colourings.
Edit: I'm fairly sure that prime powers $p^k$ with $k>2$ will not have fair division colourings, and that it can be proved in a similar way as the above proof using only the four rectangle shapes $1\times p^k$ and $p\times p^{k-1}$ in both orientations. I may try to construct the proof later.
A: Just an observation
Suppose such a coloring works for some $n$. Let $p$ and $q$ pe integers such that $q>p$ and $p\cdot q=n$ Consider the following $2$ rectangles ($ABCD$ and $AB'C'D'$, in the corner):
(image didnt work)
(Note that $AB'=AD=p$ and $B'B=D'D=q-p$ and $A,D,D'$ are on a line and $A,B,B'$ are on a line and $O$ is the intersection of $B'C'$ and $CD$ )
This means that rectangles $B'BCO$ and $DD'C'O$ have the same $p(q-p)$ colors inside them.
Now consider the rectangle $D'XYZ$ such that $X$ is on the line $AD$ and $Y,Z$ are on the line $BC$ and $D'X=p$. If $2p>q$, this means that $D'XYZ$ intersects $B'BCO$, thus leading to a contradiction, because $DD'C'O$ is inside $D'XYZ$ so $DD'C'O$ already has the colors in $B'BCO$.
Thus, the coloring is NOT possible for any $n$ such that there exist $p,q$ $p\cdot q=n$ and $2p>q>p$ (or $2n>q^2>n$)
This idea can probably lead to some better results. For example, using this observation, $6$ is clearly not valid, while $10$ might be valid. Also, prime powers might be valid too.
