ISL 2017 C6
by yayups, Nov 20, 2018, 4:53 AM
Yay I can do something other than geo 
We claim that the maximal number of colors is
. When solving the problem, the construction of the equality case was the most difficult part, whereas I found the bound to be fairly natural. We first present the equality case, then the bound.
We construct a scenario with
colors inductively. Suppose we can color a cube of size 
with 
colors such that the slices 
had the same set of colors, where we are viewing the cube as 
. Let a shell be the set of cubes with coordinates
![\[S=\{(x,y,z)\in\{0,\ldots,n-1\}^3:0\in\{x,y,z\}\}.\]](//latex.artofproblemsolving.com/a/f/c/afc0a8b5a7f850fcd386c90c0af223835aaa7203.png)
Also let 
, and define 
similarly. We will show that one can color a shell 
with 
colors such that the set of colors of 
are identical. Then, by stacking this shell on top of the cube (so the cube is now 
), we will get the desired configuration (namely the color set for 
will be the same set for 
and 
).
We will now color the shell in a way so that the slices all have the same color sets. Color the cubes of the form 
with different colors. Now, for 
that are distinct and not 
, identify
if and only if they have the same color. We will first show that the color set of 
is the same as the color set of 
(the others follow similarly). Note that we have a bijection from to that sends
where again, 
are all different from each other. Note that this bijection preserves color, so the color sets of and are the same. We now show that the color set of 
is the same as that of 
where 
(again the others follow similarly). We have the bijection from to given by
where 
and 
. Again, this bijection is color preserving, so we have the desired property that the slices 
of the shell have the same color sets. As said before, stacking 
such shells with decreasing size demonstrates equality of the bound of 
.
We now show that the number of colors is at most in a valid configuration. Note that swapping two parallel slices (say and 
) preserves the validity of the configuration. Suppose each group of parallel slices had a total of 
distinct color sets. Then permute slices so that the slices 
to 
are all distinct sets (same for 
and 
), and such that the slices all have the same color sets for 
.
Now, partition the cube into shells, starting with size (
), then size (union of 
), and so on till size 
. Note that the cubes in the 
th shell and onward (so the shells with size at most 
) are in the slice for some 
, so all colors there have shown up in shells to 
.
Lemma: The shell with size
can have at most 
colors that did not appear in the shells with larger size.
Proof of Lemma: Suppose we were able to add at least
new colors. Note that the set of new colors in each of the three orthogonal slices of size (call them the three faces, note they intersect) must be the same (a new color is one that did not appear in the shells of color bigger than ). But there must be some new color that is in one of the three faces since there are new colors (by pigeon-hole), so we have a contradiction. 
Therefore, at the shell of size, we add at most new colors, at the next shell (of size ) we add at most 
new colors, and so on until the shell of size 
where we add at most 
new colors (as noted before, all other shells add no new colors). Therefore, the total number of colors is at most
![\[n^2+(n-1)^2+\cdots+(n-m+1)^2\le f(n),\]](//latex.artofproblemsolving.com/b/6/c/b6c86b5180bbece63f875f01987315afd0c6ab53.png)
as desired. This completes the proof.
Comments:
I came up with the second part (showing the bound first), and tried then to reverse engineer the equality case. This proved to be quite difficult as thinking in 3D is hard, so I came up with the induction idea. It turns out, you can draw the information of the colors of on shell in 2D. This can be used to motivate the equivalence classes and bijection. Below is a picture of a shell with size
that is colored in accordance with the equality case (its the one I used when solving the problem). Note that the equality case is somewhat forced upon you (after some arbitrary choices, filling out the equality case for 
felt like a Sudoko puzzle or something).
ISL 2017 C6 wrote:
Let 
be a given integer. An 
cube is composed of 
unit cubes. Each unit cube is painted with one colour. For each 
box consisting of unit cubes (in any of the three possible orientations), we consider the set of colours present in that box (each colour is listed only once). This way, we get 
sets of colours, split into three groups according to the orientation.
It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of, the maximal possible number of colours that are present.
be a given integer. An 
cube is composed of 
unit cubes. Each unit cube is painted with one colour. For each 
box consisting of 
unit cubes (in any of the three possible orientations), we consider the set of colours present in that box (each colour is listed only once). This way, we get 
sets of colours, split into three groups according to the orientation.It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of
, the maximal possible number of colours that are present.We claim that the maximal number of colors is
. When solving the problem, the construction of the equality case was the most difficult part, whereas I found the bound to be fairly natural. We first present the equality case, then the bound.
We construct a scenario with
colors inductively. Suppose we can color a cube of size 
with 
colors such that the slices 
had the same set of colors, where we are viewing the cube as 
. Let a shell be the set of cubes with coordinates![\[S=\{(x,y,z)\in\{0,\ldots,n-1\}^3:0\in\{x,y,z\}\}.\]](http://latex.artofproblemsolving.com/a/f/c/afc0a8b5a7f850fcd386c90c0af223835aaa7203.png)
Also let 
, and define 
similarly. We will show that one can color a shell 
with colors such that the set of colors of 
are identical. Then, by stacking this shell on top of the cube (so the cube is now 
), we will get the desired configuration (namely the color set for 
will be the same set for 
and 
).We will now color the shell in a way so that the slices
all have the same color sets. Color the cubes of the form 
with different colors. Now, for 
that are distinct and not 
, identify
if and only if they have the same color. We will first show that the color set of 
is the same as the color set of 
(the others follow similarly). Note that we have a bijection from to that sends
where again, 
are all different from each other. Note that this bijection preserves color, so the color sets of and are the same. We now show that the color set of 
is the same as that of 
where 
(again the others follow similarly). We have the bijection from to given by
where 
and 
. Again, this bijection is color preserving, so we have the desired property that the slices 
of the shell have the same color sets. As said before, stacking such shells with decreasing size demonstrates equality of the bound of 
.
We now show that the number of colors is at most
in a valid configuration. Note that swapping two parallel slices (say and 
) preserves the validity of the configuration. Suppose each group of parallel slices had a total of 
distinct color sets. Then permute slices so that the slices 
to 
are all distinct sets (same for 
and 
), and such that the slices all have the same color sets for 
.Now, partition the cube into
shells, starting with size (
), then size (union of 
), and so on till size 
. Note that the cubes in the 
th shell and onward (so the shells with size at most 
) are in the slice for some 
, so all colors there have shown up in shells to 
.Lemma: The shell with size
can have at most 
colors that did not appear in the shells with larger size.Proof of Lemma: Suppose we were able to add at least
new colors. Note that the set of new colors in each of the three orthogonal slices of size (call them the three faces, note they intersect) must be the same (a new color is one that did not appear in the shells of color bigger than ). But there must be some new color that is in one of the three faces since there are new colors (by pigeon-hole), so we have a contradiction. 
Therefore, at the shell of size
, we add at most new colors, at the next shell (of size ) we add at most 
new colors, and so on until the shell of size 
where we add at most 
new colors (as noted before, all other shells add no new colors). Therefore, the total number of colors is at most![\[n^2+(n-1)^2+\cdots+(n-m+1)^2\le f(n),\]](http://latex.artofproblemsolving.com/b/6/c/b6c86b5180bbece63f875f01987315afd0c6ab53.png)
as desired. This completes the proof.
Comments:
I came up with the second part (showing the bound first), and tried then to reverse engineer the equality case. This proved to be quite difficult as thinking in 3D is hard, so I came up with the induction idea. It turns out, you can draw the information of the colors of on shell in 2D. This can be used to motivate the equivalence classes and bijection. Below is a picture of a shell with size
that is colored in accordance with the equality case (its the one I used when solving the problem). Note that the equality case is somewhat forced upon you (after some arbitrary choices, filling out the equality case for 
felt like a Sudoko puzzle or something).
April 2021
September 2020