Problem

Source: All-Russian 1998

Tags: combinatorics



A cube of side length $n$ is divided into unit cubes by partitions (each partition separates a pair of adjacent unit cubes). What is the smallest number of partitions that can be removed so that from each cube, one can reach the surface of the cube without passing through a partition ?