|
| |
|
|
A289233
|
|
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.
|
|
2
|
|
|
|
0, 1, 1, 3, 4, 6, 9, 11, 15, 18, 22, 26, 30, 35, 39, 45, 50, 56, 63, 69, 77, 84, 92, 100, 108, 117, 125, 135, 144, 154, 165, 175, 187, 198, 210, 222, 234, 247, 259, 273, 286, 300, 315, 329, 345, 360, 376, 392, 408, 425, 441, 459, 476, 494, 513, 531, 551, 570
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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.
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:
.
Row 1: .
.
Row 2: . .
.
Row 3: . . .
.
Row 4: . . . .
.
Row 5: . . . . .
.
Row 6: 2---2 4---4 6---6
. \ / \ / \ /
Row 7: 1 2 3 4 5 6 7
. / \ / \ / \ / \
Row 8: 1---1 3---3 5---5 7---7
.
Thus, if n is even, then a(n) >= a(n-3) + n - 1.
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:
.
Row 1: .
.
Row 2: . .
.
Row 3: . . .
.
Row 4: . . . .
.
Row 5: . . . . .
.
Row 6: . . . . . .
.
Row 7: 1 2---2 3 4---4 5
. / \ \ / / \ \ / / \
Row 8: 1---1 2 3---3 4 5---5
.
Thus, if n mod 3 = 2, then a(n) >= a(n-2) + (2n-1)/3.
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.)
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)
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
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:
___________
1 ^
1 1 |
1 1 1 |
1 1 1 1 |
1 1 1 1 1 9
1 1 1 1 1 1 |
1 1 1 1 1 1 1 |
1 1 1 1 1 1 1 1 |
1 1 1 1 1 1 1 1 1__v
_________________
2 3 3 3 3 3 3 3 3 3 ^
2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 12
2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 |
2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 ____v
| || |
|<---------12---------->||<-------9------->|
.
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
.
o o o o .
o . o . .
. . o o .
o o o . .
o . o o .
. . and o . .
o o o o .
o . o . .
. . o o .
o o o . .
o . o o .
. . o . .
.
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)
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
|
|
|
LINKS
|
|
|
|
FORMULA
|
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
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
|
|
|
EXAMPLE
|
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.
a
a a
c c b
d c b b
d d f f e
h h g f e e
i h g g k k j
i i l m m k j j
p p l l m n q q o
r p s t t n n q o o
r r s s t u w w x x v
y a a b b u u w z x v v
y y a c b d f f z z g g e
j j h c c d d f i k k g e e
l j h h m m n n i i k o o p p
l l w w q m r n s x x t o u p v
y z z w q q r r s s x t t u u v v
y y z f f a g g b h h c i i d j j e
k k l l f a a g b b h c c i d d j e e
m k n l o u u p v v q w w r x x s y y t
m m n n o o u p p v q q w r r x s s y t t
|
|
|
MATHEMATICA
|
f[n_] := Floor[n (n +1)/6] - If[ !MemberQ[{3, 5, 6, 8}, Mod[n, 12]], 0, 1]; Array[f, 58] (* or *)
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 *)
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
