Maths Olympiad Prep

Library / /31 of 36

Combinatorics Difficulty 6.4 National Olympiad Prove it Saudi Arabia

Let positive integer nn is given. The cube of size 2n+12n + 1 consists of (2n+1)3(2n + 1)^3 unit cubes. Each cube is either colored green or orange. It is known that within any 8 unit cubes that form a cube 2×2×22 \times 2 \times 2, there are at most 4 green cubes. Find the maximum number of green cubes.

Solution

(Solution of Yousif Alkhalawi, IMO 2025 team's candidate)
Since each cube 2×2×22 \times 2 \times 2, there are at least 4 orange unit cubes (here we call it by square) so we want to minimize the number of orange squares.

Construction: Let number the layer n×nn \times n of cubes from 1n1 \to n (bottom to top). For each layer, consider the coordinate of a single squares as (x,y)(x, y) for 1x,yn1 \le x, y \le n.
* For the odd layers, we color squares at (x,y)(x, y) orange if x,yx, y are both even. The number of orange squares is n2n^2.
* For the even layers, we color square at (x,y)(x, y) orange if xyxy is even. The number of orange squares is (2n+1)2(n+1)2=n(3n+2)(2n+1)^2 - (n+1)^2 = n(3n+2).

SAUDI ARABIAN IMO Booklet 2025
---
## Saudi Booklet 2025 — Page 22
22
Solution of Preselection tests
Figure 1

The cube 2×2×22 \times 2 \times 2 will have 1 orange square in odd layer and 3 orange squares in even layers so it always have 4 orange squares as desired. The total orange squares is (n+1)n2+n2(3n+2)=n2(4n+3)(n+1)n^2 + n^2(3n+2) = n^2(4n+3). Thus the number of green squares is
(2n+1)3n2(4n+3)=4n3+9n2+6n+1. (2n + 1)^3 - n^2(4n + 3) = 4n^3 + 9n^2 + 6n + 1.

We will prove this is the maximum number of green unit cubes by induction on nn. For the base case n=1n=1, in the cube of size 3, consider some 3 sub-cubes of size 2 at 3 opposite corners. The number of orange squares on these sub-cubes is at least 4×3=124 \times 3 = 12. Note that there is at most 1 square appears in all of 3 sub-cubes, and there are at most 3 other squares appear in 2 of 3 sub-cubes. So the number of orange square in big-cube is at least 1223=712 - 2 - 3 = 7.

For a cube of size 2n+12n+1, we consider the sub-cube of size 2n12n-1 in the top corner, denote it as Ω\Omega and the square in the opposite corner with it as XX. By induction, Ω\Omega need at least 4(n1)3+3(n1)34(n-1)^3 + 3(n-1)^3 orange squares so we need to prove in the rest of the big-cube, there are at least (4n3+3n2)(4(n1)3+3(n1)2)=12n26n+1(4n^3+3n^2) - (4(n-1)^3 + 3(n-1)^2) = 12n^2 - 6n + 1 orange squares. Note that to build up the original cubes, one can place n2n^2 sub-cubes of size 2 on each face of Ω\Omega and one sub-cubes of size 2 touching XX. So there are 3n2+13n^2+1 sub-cubes leads to the sum of orange square is at least 12n2+412n^2+4. To estimate the duplication, for each of 2n2n squares on the edge containing XX, it can be in 2 sub-cubes of size 2 and for square XX, it can be in 3 so the minimum is
4(3n2+1)3×2n1×3=12n26n+1. 4(3n^2 + 1) - 3 \times 2n - 1 \times 3 = 12n^2 - 6n + 1.
This finishes the proof. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.