|
%I #49 Mar 03 2024 23:56:13
%S 0,1,1,3,4,6,9,11,15,18,22,26,30,35,39,45,50,56,63,69,77,84,92,100,
%T 108,117,125,135,144,154,165,175,187,198,210,222,234,247,259,273,286,
%U 300,315,329,345,360,376,392,408,425,441,459,476,494,513,531,551,570
%N Largest number of disjoint point triples that can be chosen from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.
%C A001840(n-1) = floor(n*(n+1)/6) is a trivial upper bound for a(n), which is not reached for n = 3, 5, 6, 8, 15, 17, 18, 20 but for all other n <= 21.
%C From _Jon E. Schoenfield_, Aug 16 2017: (Start)
%C If n is even, then the bottom three rows of points can be assembled into n-1 of the 3-point triangles; e.g., the full grid for n = 8 has 8*9/2 = 36 points, of which the 21 points in the bottom three rows can be assembled into 7 three-point triangles as follows, leaving the remaining 15 points in the same triangular arrangement as in the full grid for the n = 5 case:
%C .
%C Row 1: .
%C .
%C Row 2: . .
%C .
%C Row 3: . . .
%C .
%C Row 4: . . . .
%C .
%C Row 5: . . . . .
%C .
%C Row 6: 2---2 4---4 6---6
%C . \ / \ / \ /
%C Row 7: 1 2 3 4 5 6 7
%C . / \ / \ / \ / \
%C Row 8: 1---1 3---3 5---5 7---7
%C .
%C Thus, if n is even, then a(n) >= a(n-3) + n - 1.
%C Similarly, if n mod 3 = 2, then the bottom two rows of points can be assembled into (2n-1)/3 of the 3-point triangles; e.g., of the 36 points in the full grid for n = 8, the 15 points in the bottom two rows can be assembled into 5 three-point triangles as follows, leaving the remaining 21 points in the same triangular arrangement as in the full grid for the n=6 case:
%C .
%C Row 1: .
%C .
%C Row 2: . .
%C .
%C Row 3: . . .
%C .
%C Row 4: . . . .
%C .
%C Row 5: . . . . .
%C .
%C Row 6: . . . . . .
%C .
%C Row 7: 1 2---2 3 4---4 5
%C . / \ \ / / \ \ / / \
%C Row 8: 1---1 2 3---3 4 5---5
%C .
%C Thus, if n mod 3 = 2, then a(n) >= a(n-2) + (2n-1)/3.
%C Given the terms through a(21) = 77, the two lower bounds above and the upper bound a(n) <= floor(n(n+1)/6) are sufficient to establish that a(22) = 84, a(23) = 92, a(24) = 100, a(26) = 117, and a(28) = 135. (A solution with 108 three-point triangles can be constructed on the n = 25 grid.)
%C Conjecture: a(n) = floor((n(n+1) - floor(((n+3) mod 12)/6))/6); i.e., the upper bound floor(n(n+1)/6) can be reached unless n(n+1)/2 is a multiple of 3 and (n+3) mod 12 >= 6, in which case a(n) falls short of the upper bound by 1. (End)
%C a(31) = 165, a(33) = 187, a(34) = 198, a(35) = 210, a(36) = 222, a(37) = 234, a(38) = 247, and a(40) = 273. - _Rob Pratt_, Dec 19 2017
%C From _Jon E. Schoenfield_, Dec 21 2017: (Start)
%C If we refer to a triangular grid with n points on each side simply as an "n-triangle", then for any n > 13, the n-triangle can be broken into an (n-12)-triangle, a 12-triangle, and a parallelogram-shaped grid with 12 points on each of two opposite sides and n-12 points on each of the other two sides (with n-12 > 1). E.g., we can break the 21-triangle into (1) a 9-triangle, (2) a 12-triangle, and (3) a 9 X 12 parallelogram grid:
%C ___________
%C 1 ^
%C 1 1 |
%C 1 1 1 |
%C 1 1 1 1 |
%C 1 1 1 1 1 9
%C 1 1 1 1 1 1 |
%C 1 1 1 1 1 1 1 |
%C 1 1 1 1 1 1 1 1 |
%C 1 1 1 1 1 1 1 1 1__v
%C _________________
%C 2 3 3 3 3 3 3 3 3 3 ^
%C 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 12
%C 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
%C 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 ____v
%C | || |
%C |<---------12---------->||<-------9------->|
%C .
%C All points of a 2 X 12 parallelogram grid and all points of a 3 X 12 parallelogram grid can be assembled into 3-point triangles using the simple patterns
%C .
%C o o o o .
%C o . o . .
%C . . o o .
%C o o o . .
%C o . o o .
%C . . and o . .
%C o o o o .
%C o . o . .
%C . . o o .
%C o o o . .
%C o . o o .
%C . . o . .
%C .
%C respectively, so those patterns can be combined to assemble a k X 12 parallelogram completely into 3-point triangles for any k > 1. Thus, since both the 12-triangle and the (n-12) X 12 parallelogram grid can be completely assembled into 3-point triangles for any n > 13, we have, for n > 13, a(n) >= a(n-12) + a(12) + (n-12)*12/3, which reduces to a(n) >= a(n-12) + 4n - 22. In particular, if the trivial upper bound floor(n*(n+1)/6) is reached by a(n), then it is also reached by a(n+12k) for any positive integer k. Given a(1)..a(12), this is sufficient to prove that a(n) = floor(n*(n+1)/6) except when n mod 12 is 3, 5, 6, or 8; in those cases, a(n) >= floor(n*(n+1)/6) - 1. (End)
%C Theorem 1.1 of the Conway and Lagarias link indicates that all the points can be covered by 3-point triangles iff n mod 12 = 0, 2, 9, or 11. That fact, together with the above results for a(n) in the specific cases for n in [1, 3..8, 10] and the recursive lower bound a(n) >= a(n-12) + 4n - 22, is sufficient to prove that a(n) = floor(n*(n+1)/6) - d where d is 1 when n mod 12 is in [3, 5, 6, 8] and 0 otherwise. - _Jon E. Schoenfield_, Dec 26 2017
%H J. H. Conway and J. C. Lagarias, <a href="https://doi.org/10.1016/0097-3165(90)90057-4">Tiling with Polyominoes and Combinatorial Group Theory</a>, JCTA 53 (1990), 183-208.
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (2, 0, -1, -2, 2, 1, 0, -2, 1).
%F G.f.: x*(1 - x + x^2 - x^3 + x^4) / ((1 - x)^3*(1 + x + x^2)*(1 - x^2 + x^4)) (conjectured). - _Colin Barker_, Jul 08 2017
%F a(n) = floor(n*(n+1)/6) except when n mod 12 is 3, 5, 6, or 8; in those cases, a(n) = floor(n*(n+1)/6) - 1. - _Jon E. Schoenfield_, Dec 25 2017
%e From a 21 X 21 X 21 point grid up to 77 disjoint 2 X 2 X 2 triangles (aaa, bbb, ...) can be chosen. Selections like the one below with no point left are very rare compared to C(400, 77). 400 is the total number of 2 X 2 X 2 triangles in the 21-grid.
%e a
%e a a
%e c c b
%e d c b b
%e d d f f e
%e h h g f e e
%e i h g g k k j
%e i i l m m k j j
%e p p l l m n q q o
%e r p s t t n n q o o
%e r r s s t u w w x x v
%e y a a b b u u w z x v v
%e y y a c b d f f z z g g e
%e j j h c c d d f i k k g e e
%e l j h h m m n n i i k o o p p
%e l l w w q m r n s x x t o u p v
%e y z z w q q r r s s x t t u u v v
%e y y z f f a g g b h h c i i d j j e
%e k k l l f a a g b b h c c i d d j e e
%e m k n l o u u p v v q w w r x x s y y t
%e m m n n o o u p p v q q w r r x s s y t t
%t f[n_] := Floor[n (n +1)/6] - If[ !MemberQ[{3, 5, 6, 8}, Mod[n, 12]], 0, 1]; Array[f, 58] (* or *)
%t CoefficientList[ Series[(-x +x^2 -x^3 +x^4 -x^5)/((-1 +x)^3 (1 +x -x^3 +x^5 +x^6)), {x, 0, 57}], x] (* or *)
%t LinearRecurrence[{2, 0, -1, -2, 2, 1, 0, -2, 1}, {0, 1, 1, 3, 4, 6, 9, 11, 15}, 58] (* _Robert G. Wilson v_, Dec 26 2017 *)
%Y Cf. A001840, A289222, A289229.
%K nonn
%O 1,4
%A _Heinrich Ludwig_, Jul 08 2017
%E a(22)-a(26) from _Jon E. Schoenfield_, Aug 16 2017
%E a(27)-a(28) from _Rob Pratt_, Dec 19 2017
%E More terms from _Jon E. Schoenfield_, Dec 25 2017
|
