Solution:  1 × 3 × 6, 1 × 4 × 4, and 2 × 2 × 2. 

Assume that the dimensions of the block are a × b × c. Because each cube has six faces, the total number of faces in the block is 6abc. Further, the number of painted faces is equal to the surface area, 2(ab + ac + bc). Since half the faces are painted and half are unpainted, then double this number will give the total number of faces in the block, 4(ab + ac + bc). All this information leads to the following equation:

6abc=4(ab+ac+bc)

Trial-and-error can then be used to find the solutions to this equation.

Assume a < b < c, that is, a is the smallest edge of the block. If a = 3, then the equation above becomes 18bc = 4(3b + 3c + bc), which can be simplified to 7bc = 6(b + c). But this yields an impossibility, because bc > b + c for all values of b, c > 2, and it must be the case that b, c > 2 since we assumed that a was the smallest edge. Similar results occur if a > 3, as well.

So then check a = 1. The equation reduces to 6bc = 4(b + c + bc), or bc = 2(b + c). If this equation looks vaguely familiar, perhaps it should. It’s the condition for the perimeter of a rectangle to equal its area, a problem that is known to have only two solutions, namely a 3 × 6 rectangle and a 4 × 4 square. So, if you started with a block measuring 1 × 3 × 6 or 1 × 4 × 4, cutting it into unit cubes would result in precisely half of the total faces having paint on them.

If a = 2, you’d have 12bc = 4(2b + 2c + bc), so 8bc = 8(b + c) and therefore bc = b + c. The only solution in positive integers to this equation is the pair (2, 2), and all of a sudden we can kick ourselves for using equations instead of our heads. It’s obvious that a 2 × 2 × 2 cube cut in half along every axis produces eight unit cubes, each of which is painted on three of its six faces. If half of the faces on each unit cube are painted, then half of the faces in the entire block must be painted.