Each face of a $7 \times 7 \times 7$ cube is divided into unit squares. What is the maximum number of squares that can be chosen so that no two chosen squares have a common point? A. Chukhnov
Problem
Source: Tuymaada 2013, Day 2, Problem 5 Juniors
Tags: geometry, 3D geometry, combinatorics proposed, combinatorics
22.07.2013 23:20
Subdivide each unit square $1\times 1$, on each face, into four small squares (cells) $1/2 \times 1/2$. To each unit square associate the cells with which it has at least one point in common.Thus, a square in a corner of a face will have associated $1\cdot 4 + 4\cdot 2 + 3\cdot 1 = 15$ cells, while any other square will have associated $1\cdot 4 + 4\cdot 2 + 4\cdot 1 = 16$ cells. Any two of the chosen squares will have to have disjoint associated sets of cells. Since in total there are $4\cdot 6\cdot 7^2 = 1176$ cells, denoting by $x$ the number of chosen corner squares and by $y$ the number of the other chosen squares, we want to maximize $x+y$, under the condition $15x + 16 y \leq 1176$. Let us also notice that if a corner square is chosen, then none of the other two squares in the same corner can be chosen anymore, therefore $x\leq 8$. Since $1176 = 8\cdot 15 + 66\cdot 16$, it follows $\max\{x+y \mid 15x + 16 y \leq 1176\} = 8 + 66 = 74$ (with the entire surface of the cube thus partitioned into disjoint associated sets of cells to the chosen squares). A model is easy to realize, with pairs of opposed faces of the types $F_1, F_2, F_3$ below, having $16$, $12$, respectively $9$ squares chosen, thus with a total of $2\cdot 16 + 2\cdot 12 + 2\cdot 9 = 74$ chosen squares. $F_1 = \begin{tabular} {| c | c | c | c | c | c | c |} \hline \cdot & & \cdot & & \cdot & & \cdot \\ \hline & & & & & & \\ \hline \cdot & & \cdot & & \cdot & & \cdot \\ \hline & & & & & & \\ \hline \cdot & & \cdot & & \cdot & & \cdot \\ \hline & & & & & & \\ \hline \cdot & & \cdot & & \cdot & & \cdot \\ \hline \end{tabular} $ $ F_2 = \begin{tabular} {| c | c | c | c | c | c | c |} \hline & & & & & & \\ \hline \cdot & & \cdot & & \cdot & & \cdot \\ \hline & & & & & & \\ \hline \cdot & & \cdot & & \cdot & & \cdot \\ \hline & & & & & & \\ \hline \cdot & & \cdot & & \cdot & & \cdot \\ \hline & & & & & & \\ \hline \end{tabular} $ $ F_3 = \begin{tabular} {| c | c | c | c | c | c | c |} \hline & & & & & & \\ \hline & \cdot & & \cdot & & \cdot & \\ \hline & & & & & & \\ \hline & \cdot & & \cdot & & \cdot & \\ \hline & & & & & & \\ \hline & \cdot & & \cdot & & \cdot & \\ \hline & & & & & & \\ \hline \end{tabular}$
25.07.2013 21:54
I would like to correct a typographical error in the official solutions and say that the author of this problem --- Anton Chukhnov
25.07.2013 22:32
Since A. Golovanov is the name appearing in the solutions booklet, I will need more than just a blanket statement for replacement to be done. Maybe you could contact Alexander, and ask him to post in this thread a personal request towards the replacement of authorship.
26.07.2013 14:47
Yes, it is a problem by Anton Chukhnov.
26.07.2013 14:59
Correction made, thanks.