A designer took a wooden cube $5 \times 5 \times 5$, divided each face into unit squares and painted each square black, white or red so that any two squares with a common side have different colours. What is the least possible number of black squares? (Squares with a common side may belong to the same face of the cube or to two different faces.) (8 points) Mikhail Evdokimov
Problem
Source: Tournament of Towns Spring 2016 Junior A-Level
Tags: combinatorics, geometry, 3D geometry
rafayaashary1
23.02.2017 08:54
I can get it in $18$, but proving optimality is a whole different matter. My thoughts so far: Observation is that there are only two ways to color a square grid with two colors so that no two of the same color "touch." Now, we can break the surface of the cube into "domains" where two squares are in the same domain iff they are cofacial and there is a path entirely in said face that contains no black square. Now, each domain can be assigned a 'parity' based on whether the induced red/white checkerboard coloring on the $5\times 5$ square that contains it has more red or more white squares (parity must be homogenous throughout a domain by the initial observation). Two domains are said to be adjacent iff they are distinct, and there is an edge of the cube that they both border. In fact, it is easily checked that two adjacent domains must differ in parity (caution that two cofacial domains by definition are nonadjacent). It follows that in order for the problem condition to hold, the domain adjacency graph must admit a $2$-coloring. The rigor ends here. The idea is that we split two opposing faces into $4$ domains each by placing black squares on the diagonals. It is easy to see that the resulting domain adjacency graph is a tree, which then of course must admit a $2$-coloring, as desired. Now, a note on the lower bound. Trivially we need at least $8$ black squares; one for each vertex. Actually, we can bring up the bound even further to $11$, since we need at least one nontrivial "block" (domain creation or adjacent domain separation) since the original domain adjacency graph is an octahedron, and thus contains (quite a few) $K_3$. The real question is if such incremental observations can bring the bound all the way up to $18$ (seems tedious), if this method cannot be completed, or if there is a better construction that $18$.
MellowMelon
23.02.2017 20:12
[asy][asy]
pair d1 = rotate(270)*(1,0);
pair d2 = rotate(150)*(1,0);
pair d3 = rotate(30)*(1,0);
for (int i = 0; i <= 5; i += 1) {
draw((i*d1)--(i*d1+5*d2));
draw((i*d2)--(i*d2+5*d3));
draw((i*d3)--(i*d3+5*d1));
if (i > 0) {
draw((i*d1)--(i*d1+5*d3));
draw((i*d2)--(i*d2+5*d1));
draw((i*d3)--(i*d3+5*d2));
}
}
pair getTopFace(real x, real y) {
return -0.5*d1 + x*d2 + y*d3;
}
pair getRightFace(real x, real y) {
return -0.5*d2 + x*d3 + y*d1;
}
pair getLeftFace(real x, real y) {
return -0.5*d3 + x*d1 + y*d2;
}
draw(getTopFace(0, 0)--getLeftFace(0, 0)--getRightFace(0, 0)--cycle, blue);
draw(getTopFace(0, 1)--getTopFace(1, 1)--getTopFace(1, 0)--getLeftFace(0, 1)--getLeftFace(1, 1)--getLeftFace(1, 0)--getRightFace(0, 1)--getRightFace(1, 1)--getRightFace(1, 0)--cycle, blue);
draw(getTopFace(0, 2)--getTopFace(2, 2)--getTopFace(2, 0)--getLeftFace(0, 2)--getLeftFace(2, 2)--getLeftFace(2, 0)--getRightFace(0, 2)--getRightFace(2, 2)--getRightFace(2, 0)--cycle, blue);
draw(getTopFace(4, 4.5)--getTopFace(4, 4)--getTopFace(4.5, 4), blue);
draw(getTopFace(3, 4.5)--getTopFace(3, 3)--getTopFace(4.5, 3), blue);
draw(getTopFace(4, -0.5)--getTopFace(4, 0)--getTopFace(4.5, 0), blue);
draw(getTopFace(3, -0.5)--getTopFace(3, 1)--getTopFace(4.5, 1), blue);
draw(getTopFace(0, 4.5)--getTopFace(0, 4)--getTopFace(-0.5, 4), blue);
draw(getTopFace(1, 4.5)--getTopFace(1, 3)--getTopFace(-0.5, 3), blue);
draw(getRightFace(4, 4.5)--getRightFace(4, 4)--getRightFace(4.5, 4), blue);
draw(getRightFace(3, 4.5)--getRightFace(3, 3)--getRightFace(4.5, 3), blue);
draw(getRightFace(4, -0.5)--getRightFace(4, 0)--getRightFace(4.5, 0), blue);
draw(getRightFace(3, -0.5)--getRightFace(3, 1)--getRightFace(4.5, 1), blue);
draw(getRightFace(0, 4.5)--getRightFace(0, 4)--getRightFace(-0.5, 4), blue);
draw(getRightFace(1, 4.5)--getRightFace(1, 3)--getRightFace(-0.5, 3), blue);
draw(getLeftFace(4, 4.5)--getLeftFace(4, 4)--getLeftFace(4.5, 4), blue);
draw(getLeftFace(3, 4.5)--getLeftFace(3, 3)--getLeftFace(4.5, 3), blue);
draw(getLeftFace(4, -0.5)--getLeftFace(4, 0)--getLeftFace(4.5, 0), blue);
draw(getLeftFace(3, -0.5)--getLeftFace(3, 1)--getLeftFace(4.5, 1), blue);
draw(getLeftFace(0, 4.5)--getLeftFace(0, 4)--getLeftFace(-0.5, 4), blue);
draw(getLeftFace(1, 4.5)--getLeftFace(1, 3)--getLeftFace(-0.5, 3), blue);
[/asy][/asy]
Constructing 18 is just putting two X-shapes of black squares on opposite faces.
MellowMelon
24.02.2017 12:42
Here's an extension which is only slighly harder and just as fun: suppose we color the squares in 4 colors red, green, blue, and black. Two squares with the same color cannot touch even at a vertex. What is the minimum number of black squares?
Tahsinkhan
31.03.2024 17:25
I dont see any construction with 18 but 20 of them. How is the construction done?