Given an $n \times n \times n$ grid of unit cubes, a cube is good if it is a sub-cube of the grid and has side length at least two. If a good cube contains another good cube and their faces do not intersect, the first good cube is said to properly contain the second. What is the size of the largest possible set of good cubes such that no cube in the set properly contains another cube in the set?
Problem
Source: Canada RepĂȘchage 2016/3
Tags: combinatorics, counting
15.11.2016 16:13
any idea
16.11.2016 12:51
Let the progeny of a cube be defined as the largest cube properly contained within it. Let a large cube be a proper cube of sidelength 4 or greater. We shall show that there exists a set of maximal order of good cubes which do not pairwise properly contain each other consisting of no large cubes. Start with any maximal pairwise-non-properly-containing set of good cubes. Take any cube of largest size among them. If it's small, we're done. Otherwise, remove this cube and add its progeny (note that the progeny is still big enough to be considered good, and since it is properly contained in the removed cube it couldn't have been in the original set). If any cube in the original set properly contains the progeny, it must be strictly larger than our removed cube, a contradiction. If the progeny properly contains any cube, the removed cube also properly contained it, a contradiction. Otherwise, iterating this process generates sets of cubes of the same order, which fulfil the pairwise-non-properly-containing property, of successively smaller total sidelength. Eventually, this process must stop and we've generated a set of no large cubes. Note that this set has an order no larger than the set of all 2x2 and 3x3 cubes. It's readily apparent that this set fulfils the pairwise-non-properly-containing property (what a mouthful!), so it is the maximal such set. Its order is $(n-1)^3+(n-2)^3$.