here is a short proof that an 8x8x8 cube minus two corners cannot be tiled
with 1x1x3 blocks.
Label each unit cube with (x+y+z) modulo 3, where (x,y,z) are its
coordinates (each from 0 to 7). Then the numbers of cubes labelled with 0, 1
and 2 are 170, 171 and 171, respectively. WLOG, remove the corner (0,0,0).
Then there are 169 cubes left with label 0. Since each block covers exactly
one of each labels 0, 1 and 2, we cannot put more than 169 blocks into the
8x8x8 cube, no matter which unit cube is removed as the second one. qed
Helmut Postl
-----------------------------------------------------------------------

Ed,

The 8x8x8 cube can be tiled with 170 1x1x3 blocks with two unit cubes left
over, but only for certain locations of the two unit cubes. Up to symmetry,
there are only 18 different arrangements of the two unit cubes which work.

Suppose we label each row with 0, 1, ... 7. One cube can be placed at
(2,2,z), where z = 0 mod 3. The other goes at (a,b,z'), where (a,b) = (2,2),
(2,5) or (5,5), and (z,z') = (0,1), (0,4), (0,7), (3,1), (3,4) or (6,1). So
z' = 1 mod 3.

That these are the only possibilities can be seen by 3-color striping the
8x8x8 cube orthogonal to a major diagonal, then doing the same for each of
the other 3 diagonals. It's then easy to show that these 18 cases can in
fact be tiled. Start by tiling a tube on the outside, leaving a 4x4x8 column
in the middle, where the two key cubes are now on a long edge. Since any 4x4
"floor" minus a corner can be tiled, it's easy to solve where z-z' = 1 mod
3. This just leaves the cases (z,z') = (3,1) & (6,1). These can be solved by
considering how many cells in each floor are not part of a 1x1x3 block,
lying wholly in that floor.

Taking a step back, what is the "simplest" tiling problem for which striping
is not a sufficient constraint?

Thanks for all the work,
Cheers,
Andrew Buchanan