Difference between revisions of "Fujimura's problem"

From Polymath1Wiki
Jump to: navigation, search
(n=6)
m (fix OEIS link)
 
(13 intermediate revisions by 5 users not shown)
Line 3: Line 3:
 
:<math>\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}</math>
 
:<math>\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}</math>
  
which contains no equilateral triangles <math>(a+r,b,c), (a,b+r,c), (a,b,c+r)</math> with <math>r > 0</math>; call such sets ''triangle-free''.  (It is an interesting variant to also allow negative r, thus allowing "upside-down" triangles, but this does not seem to be as closely connected to DHJ(3).)  Fujimura's problem is to compute <math>\overline{c}^\mu_n</math>.  This quantity is relevant to a certain [[hyper-optimistic conjecture]].
+
which contains no equilateral triangles <math>(a+r,b,c), (a,b+r,c), (a,b,c+r)</math> with <math>r > 0</math>; call such sets ''triangle-free''.  (It is an interesting variant to also allow negative r, thus allowing "upside-down" triangles, but this does not seem to be as closely connected to DHJ(3).)  Fujimura's problem is to compute <math>\overline{c}^\mu_n</math> ([http://oeis.org/A157795 OEIS A157795]).  This quantity is relevant to a certain [[hyper-optimistic conjecture]].
 +
 
 +
We are also exploring issues raised by [[higher-dimensional Fujimura]].
 +
 
 +
The following table was formed mostly by computer searches for optimal solutions.  We also found human proofs for most of them (see below).
  
 
{|
 
{|
| n || 0 || 1 || 2 || 3 || 4 || 5
+
| n || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13
 
|-
 
|-
| <math>\overline{c}^\mu_n</math> || 1 || 2 || 4 || 6 || 9 || 12
+
| <math>\overline{c}^\mu_n</math> || 1 || 2 || 4 || 6 || 9 || 12 || 15 || 18 || 22 || 26 || 31 || 35 || 40 || 46
 
|}
 
|}
  
Line 82: Line 86:
 
== n=6 ==
 
== n=6 ==
  
:<math>15 \leq \overline{c}^\mu_6 \leq 17</math>:
+
:<math>\overline{c}^\mu_6 = 15</math>:
  
[Incomplete: need to add rotations of solution II.]
+
<math>\overline{c}^\mu_6 \geq 15</math> from the bound for general n.  
  
<math>15 \leq \overline{c}^\mu_6</math> from the bound for general n.
+
Note that there are ten extremal solutions to <math>\overline{c}^\mu_3</math>:
 
+
Note that there are ten extremal solutions to <math> \overline{c}^\mu_3 </math>:
+
  
 
Solution I: remove 300, 020, 111, 003<br>
 
Solution I: remove 300, 020, 111, 003<br>
 
Solution II (and 2 rotations): remove 030, 111, 201, 102<br>
 
Solution II (and 2 rotations): remove 030, 111, 201, 102<br>
 
Solution III (and 2 rotations): remove 030, 021, 210, 102<br>
 
Solution III (and 2 rotations): remove 030, 021, 210, 102<br>
Solution III' (and 2 rotations): remove 030, 120, 012, 201
+
Solution III' (and 2 rotations): remove 030, 120, 012, 201<br>
  
Also consider the same triangular lattice with the point 020 removed, making a trapezoid. Solutions based on I-III are:
+
Also consider the same triangular lattice with the point 020 removed, making a trapezoid. Solutions based on I-III are:  
  
 
Solution IV: remove 300, 111, 003<br>
 
Solution IV: remove 300, 111, 003<br>
 
Solution V: remove 201, 111, 102<br>
 
Solution V: remove 201, 111, 102<br>
 
Solution VI: remove 210, 021, 102<br>
 
Solution VI: remove 210, 021, 102<br>
Solution VI': remove 120, 012, 201
+
Solution VI': remove 120, 012, 201<br>
  
Suppose we can remove all equilateral triangles on our 7×7x7 triangular lattice with only 10 removals.
+
The on the 7x7x7 triangular lattice triangle 141-411-114 must have at least one point removed. Remove 141, noting by symmetry any logic that follows will also work for either of the other two points.
  
The triangle 141-411-114 must have at least one point removed. Remove 141, and note because of symmetry any logic that follows also applies to 411 and 114.
+
Suppose we can remove all equilateral triangles on our 7×7x7 triangular lattice with only 12 removals.
  
There are three disjoint triangles 060-150-051, 240-231-330, 042-132-033, so each must have a point removed.
+
Here, "top triangle" means the top four rows of the lattice (with 060 at top) and "bottom trapezoid" means the bottom three rows.
  
(Now only six removals remaining.)
+
At least 4 of those removals must come from the top triangle (the solutions of <math> \overline{c}^\mu_3</math> mentioned above).
  
The remainder of the triangle includes the overlapping trapezoids 600-420-321-303 and 303-123-024-006. If the solutions of these trapezoids come from V, VI, or VI', then 6 points have been removed. Suppose the trapezoid 600-420-321-303 uses the solution IV (by symmetry the same logic will work with the other trapezoid). Then there are 3 disjoint triangles 402-222-204, 213-123-114, and 105-015-006. Then 6 points have been removed. Therefore the remaining six removals must all come from the bottom three rows of the lattice.
+
The bottom trapezoid includes the overlapping trapezoids 600-420-321-303 and 303-123-024-006. If the solutions of these trapezoids come from V, VI, or VI', then 6 points have been removed. Suppose the trapezoid 600-420-321-303 uses the solution IV (by symmetry the same logic will work with the other trapezoid). Then there are 3 disjoint triangles 402-222-204, 213-123-114, and 105-015-006. Then 6 points have been removed. Therefore at least six removals must come from the bottom trapezoid.
  
Note this means the "top triangle" 060-330-033 must have only four points removed so it must conform to solution either I or II, because of the removal of 141.
+
To make a total of 12 removals there must be either:<br>
 +
Case A: 4 removals from the top triangle and 8 from the bottom trapezoid.<br>
 +
Case B: 5 removals from the top triangle and 7 from the bottom trapezoid.<br>
 +
Case C: 6 removals from the top triangle and 6 from the bottom trapezoid.<br>
  
Suppose the solution of the trapezoid 600-420-321-303 is VI or VI'. Both solutions I and II on the "top triangle" leave 240 open, and hence the equilateral triangle 240-420-222 remains. So the trapezoid can't be VI or VI'.
+
* Suppose case A is true.
  
Suppose the solution of the trapezoid 600-420-321-303 is V. This leaves an equilateral triangle 420-321-330 which forces the "top triangle" to be solution I. This leaves the equilateral triangle 201-321-222. So the trapezoid can't be V.
+
Because 141 is already removed, the solution to the top triangle must remove either solution I (remove 060, 330, 033), solution II (remove 060, 231, 132), solution IIb (remove 033, 150, 240) or solution IIc (remove 330, 051, 042)
  
Therefore the solution of the trapezoid 600-420-321-303 is IV. Since the disjoint triangles 402-222-204, 213-123-114, and 105-015-006 must all have points removed, that means the remaining points in the bottom three rows (420, 321, 510, 501, 312, 024) must be left open. 420 and 321 force 330 to be removed, so the "top triangle" is solution I. This leaves triangle 321-024-051 open, and we have reached a contradiction.
+
Suppose I is the solution for the top triangle.
  
:<math>15 \leq \overline{c}^\mu_6 \leq 16</math>:
+
Suppose 222 is open. Then 420, 321, 123, and 024 must all be removed. This leaves five disjoint triangles which require removals in the bottom trapezoid (150-600-105, 051-501-006, 222-402-204, 231-411-213, 132-312-114); therefore the bottom trapezoid needs at least 9 removals, but we can only make 8, therefore 222 is closed.
  
Here, "upper triangle" means the first four rows (with 060 at top) and "lower trapezoid" means the bottom three rows.
+
Suppose 411 is open. Then 213 and 015 must be removed. This leaves five disjoint triangles such that each triangle must have exactly one removal (420-150-123, 321-051,024, 600-510-501, 402-312-303, 204-114-105), so the remaining point (006) must be open, forcing 501 to be removed. This makes 600 and 510 open, and based on the triangles 600-240-204 and 510-150-114 both 204 and 114 must both be removed, but 204 and 114 are on the same disjoint triangle, contradicting the statement that each triangle must have exactly one removal. So 411 is closed.
  
Suppose 11 removals leave a triangle-free set.
+
This leaves six disjoint triangles each which must have at least one removal (420-123-150, 321-024-051, 510-213-240, 312-015-042, 501-204-231, 402-105-132). This forces 600 and 006 to be open. Based on the triangles 006-501-051 and 600-204-240, this forces 501 and 204 to be open. But then there are no removals from the triangle 501-204-231, which is a contradiction. Therefore the solution of the top triangle cannot be I.
  
First, suppose that 5 removals come from the upper triangle and 6 come from the lower trapezoid.
+
Suppose II is the solution for the top triangle.
  
Suppose the trapezoid 600-420-321-303 used solution IV. There are three disjoint triangles 402-222-204, 213-123-114, and 105-015-006. The remainder of the points in the lower trapezoid (420, 321, 510, 501, 402, 312, 024) must be left open. 024 being open forces either 114 or 015 to be removed.  
+
There are seven disjoint triangles (150-600-105, 051-501-006, 222-402-204, 240-510-213, 042-312-015, 330-420-321, 033-123-024), therefore of the three points remaining in the bottom trapezoid (411, 303, 114) exactly one must be removed.
  
Suppose 114 is removed. Then 213 is open, and with 312 open that forces 222 to be removed. Then 204 is open, and with 024 that forces 006 to be removed. So the bottom trapezoid is a removal configuration of 600-411-303-222-114-006, and the rest of the points in the bottom trapezoid are open. All 10 points in the upper triangle form equilateral triangles with bottom trapezoid points, hence 10 removals in the upper triangle would be needed, so 114 being removed doesn't work.
+
Suppose 411 is removed. Then 114 and 303 are open; 114 open forces 510 to be removed, forcing 213 to be open. 114 and 213 open force 123 to be closed, forcing 024 to be open. 024 open forces 222 to be closed, which forces 204 to be open, which leaves the triangle 213-303-204 open so we have a contradiction.
  
Suppose 015 is removed. Then 006-024 forces 204 to be removed. Regardless of where the removal in 123-213-114, the points 420, 321, 222, 024, 510, 312, 501, 402, 105, and 006 must be open. This forces upper triangle removals at 330, 231, 042, 060, 051, 132, which is more than the 5 allowed, so 015 being removed doesn't work, so the trapezoid 600-420-321-303 doesn't use solution IV.
+
By symmetry 114 also can't be removed. Therefore we must remove 303. This leaves 411 and 114 open, forcing 510 and 015 closed. 510 and 015 closed forces 312 and 213 open, forcing 222 closed. 222 closed forces 402 and 204 open. 402 and 204 open force 501 and 105 closed. 510 and 105 closed force 600 and 006 open, leaving equilateral triangles 600-204-240 and 402-006-042 open. Therefore 303 can't be removed, and so the solution of the top triangle can't be II.
  
Suppose the trapezoid 600-420-321-303 uses solution VI. The trapezoid 303-123-024-006 can't be IV (already eliminated by symmetry) or VI' (leaves the triangle 402-222-204). Suppose the trapezoid 303-123-024-006 is solution VI. The removals from the lower trapezoid are then 420, 501, 312, 123, 204, and 015, leaving the remaining points in the lower trapezoid open. The remaining open points is forces 10 upper triangle removals, so the trapezoid 600-420-321-303 doesn't use solution VI. Therefore the trapezoid 303-123-024-006 is solution V. The removals from the lower trapezoid are then 420, 510, 312, 204, 114, and 105. The remaining points in the lower trapezoid are open, and force 9 upper triangle removals, hence the trapezoid 303-123-024-006 can't be V, and the solution for 600-420-321-303 can't be VI.
+
Suppose IIb is the solution for the top triangle.
  
The solution VI' for the trapezoid 600-420-321-303 can be eliminated by the same logic by symmetry.
+
Suppose 024 is open. This forces 420, 321, and 222 closed. Five disjoint triangles remain (510-600-501, 231-411-213, 132-312-114, 123-303-105, 024-204-006) so each must have exactly one point removed, and the remaining points in the bottom trapezoid (402, 015) must be open. This forces 312, 411, 510, and 006 closed, which then force the the other points in their disjoint triangles open (600, 501, 231, 213, 132, 114, 204). The triangle 501-231-204 is therefore open, so we have a contradiction, therefore 024 is closed.
  
Therefore it is impossible for 5 removals come from the upper triangle and 6 come from the lower trapezoid.
+
Suppose 006 is open. This forces 600, 501 and 402 to be closed, and leaves five disjoint triangles (510-420-411, 321-231-222, 312-132-114, 303-213-204, 105-015-006) and so 123 must be open. This forces 222 closed, which forces 321 open, which forces 420 closed, which forced 510 and 411 open, which forces 213 closed, which forces 303 and 204 open, which forces 105 closed, which forces 015 and 006 to be open, leaving an open triangle at 411-015-051. Therefore we have a contradiction, so 006 is closed.
Therefore 4 removals come from the upper triangle and 7 come from the lower trapezoid.
+
  
At this point note the triangle 141-411-141 must have one point removed, so let it be 141 and note that any logic that follows is also true for a removal of 411 and 141 by symmetry.
+
Given 024 and 006 closed, now note there are six disjoint triangles (600-510-501, 402-312-303, 204-114-105, 420-330-321, 222-132-123, 411-231-213). Therefore the remaining point in the bottom trapezoid 015 must be open, forcing 510, 411, and 312 to be closed. Using the disjoint triangles this forces 600, 501, 402, 303 and 213 to be open, which then forces 420 and 321 to be closed. Both 420 and 321 are on the same disjoint triangle, therefore we have a contradiction, so IIb can't be solution.
  
This implies the upper triangle must have either solution I or II.
+
Note by symmetry, the same logic for IIb will apply for IIc. Therefore case A isn't true.
  
Suppose it has solution II. Note there are five disjoint triangles 600-510-501, 411-321-312, 402-222-204, 213-123-114, and 105-015-006.
+
* Suppose case B is true.
  
Suppose 420 and 024 are removed. Then, noting 303 must be open, 606 must be removed, leaving 510 open. 510-240 forces 213 to be removed, and 510-150 force 114 to be removed. 213 are 114 are in the same disjoint triangle. Hence both 420 and 024 both can't be removed.
+
The row 330-231-132-033 has ten possible solutions (excluding reflections, which by symmetry will be handled by the same logic):
  
So at least either 420 or 024 is open. Let it be 420, noting by symmetry identical logic will apply if 024 is removed. Then 321, 222, and 123 are removed based on 420 and the open spaces in the upper triangle. This leaves four disjoint triangles 600-501-510, 402-303-312, 213-033-015, 204-114-105. So 411 and 420 are open, forcing the removal of 510. This leaves 501 open, and 501-411 forces the removal of 402. 600-303, and 330 are then open, forming an equilateral triangle. Therefore 420 isn't open, therefore the upper triangle can't have solution II.
+
Case Q: open-open-open-open<br>
 +
Case R: closed-closed-closed-closed<br>
 +
Case S: closed-open-open-open<br>
 +
Case T: closed-open-closed-closed<br>
 +
Case U: open-closed-closed-closed<br>
 +
Case V: closed-open-closed-closed<br>
 +
Case W: closed-closed-open-open<br>
 +
Case X: closed-open-closed-open<br>
 +
Case Y: open-closed-closed-open<br>
 +
Case Z: closed-open-open-closed<br>
  
Therefore the upper triangle has solution I.
+
Consider all 10 cases. Note in all these cases we are still assuming 141 is removed.
  
Suppose 222 is open. 222 with open points in the upper triangle force 420, 321, 123, and 024 to be removed. This leaves four disjoint triangles 411-501-402, 213-303-204, 015-105-006, and 132-312-114. This would force 8 removals in the lower trapezoid, so 222 must be closed.
+
(Case Q) 330, 231, 132, 033 open forces 060, 150, 051, 240, 141, 042 closed, but the top triangle only allows 5 removals, so case Q forms a contradiction.
  
Therefore 222 is removed. There are six disjoint triangles 150-420-123, 051-321-024, 231-501-204, 132-402-105, 510-150-114, and 312-042-015. So 600, 411, 393, 114, and 006 are open. 600-240 open forces 204 to be removed and 600-150 open forces 105 to be removed. This forces 501 and 402 to be open, but 411 is open, so there is the equilateral triangle 501-411-402.
+
(Case R) 060-240-042 is left open, so case R forms a contradiction.
  
Therefore the solution of the upper triangle is not I, and we have a contradiction. So <math> \overline{c}^\mu_6 \neq 17 </math>.
+
(Case S) 231, 132, and 033 open force 031 and 042 removed, which means from 240, 150, 061 there must be exactly one removal.
 +
 
 +
Suppose 213 is open. Then 411 and 015 are closed, and five disjoint triangles are left where each triangle must have exactly one removal (600-420-402, 501-321-303, 312-222-213, 204-105-114, 123-024-033). So the two remaining points in the bottom trapezoid (510 and 006) must be open. 510 and 006 open force 303 closed, which forces 321 and 501 open, which forces 204 closed, which forces 114 and 103 open, which forces 402 and 312 closed, forcing 222 open, leaving 321-231-222 as an open triangle, so we have a contradiction.
 +
 
 +
Therefore 213 is closed. This leaves six disjoint triangles (600-420-402, 501-231-204, 303-033-006, 411-321-312, 222-132-123, 114-024-015) which each have exactly one removal. Therefore 510 from the bottom trapezoid is open. Note since one of 150 and 060 must be open, then one of 114 or 015 must be closed; therefore 024 is open. This forces 123 closed, forcing 222 to be open, forcing 321 to be closed, forcing 411 and 312 open, forcing 421 closed, forcing 600 and 402 open, forcing 303 closed, forcing 006 open, forcing 204 closed, forcing 501 open, leaving the triangle 600-510-501 open and a contradiction.
 +
 
 +
(Case T) 231 is closed, and 330, 132, and 033 open force 060, 150, and 042 closed. Since 141 is already closed we have five removals from the top triangle, so 240 and 051 are open.
 +
 
 +
Suppose 024 is open. This forces 321 and 123 closed, leaving five disjoint triangles (600-510-501, 402-312-303, 204-114-105, 420-240-222, 213-033-015). Therefore 006 and 411 remaining in the bottom trapezoid are open, forcing 501, 303 and 015 closed, forcing 600, 510, 312, 402, and 213 open, forcing 222 closed, forcing 420 open, leaving the open triangle 420-510-411, so we have a contradiction.
 +
 
 +
Therefore 024 is closed. There are now six disjoint triangles (510-600-501, 330-420-321, 312-402-303, 132-222-123, 033-213-015, 114-204-105). This leaves 411 and 006 open, which forces 015 and 501 closed, which forces 510 and 213 open, leaving the triangle 240-510-213 open, so we have a contradiction.
 +
 
 +
(Case U) Given the removals 231, 132, 033, and 141, the only possible removal to not leave any equilateral triangles in the top triangle is 060. So 330, 240, 150, 051, and 042 are open.
 +
 
 +
Suppose 420 is open. This forces 321, 222, and 123 closed. This leaves five disjoint triangles (600-330-303, 510-420-411, 204-105-114, 501-051-006, and 312-042-015), so we have a contradiction.
 +
 
 +
Therefore 420 is closed. This leaves six disjoint triangles (600-330-303, 501-051-006, 204-114-105, 510-240-213, 411-321-312, 222-042-024). 015 in the bottom trapezoid is therefore open, forcing 312 and 411 closed, but 312 and 411 are on the same disjoint triangle, so we have a contradiction.
 +
 
 +
(Case V) Given the removals 330, 132, and 033, the only possible removal to not leave any equilateral triangles in the top triangle is 060. So 150, 051, 240, 042, and 231 are open.
 +
 
 +
Suppose 420 is open. Then 222 and 123 are closed, and we are left with 6 disjoint triangles (150-600-105, 240-510-213, 231-501-204, 024-114-015, 042-402-006, 411-321-312). This exceeds our limit of 7 removals in the bottom trapezoid, so we have a contradiction.
 +
 
 +
Therefore 420 is closed. Again we are left with the same 6 disjoint triangles (150-600-105, 240-510-213, 231-501-204, 024-114-015, 042-402-006, 411-321-312). Therefore 222, 123, and 303 are open. This forces 321, 024, and 105 to be closed, which then forces 411 and 015 to be open, forming an open triangle at 051-411-015, so we have a contradiction.
 +
 
 +
(Case W) Given the removals 330 and 231 with 132 and 033 open, 132 and 033 open force 042 closed. Given 141 is already closed, that leaves one more removal on the top triangle, which must be one of 060-150-051, so 240 must be open.
 +
 
 +
Suppose 024 is open. This forces 123 to be closed, and leaves 6 disjoint triangles (600-510-501, 420-240-222, 411-321-312, 402-132-105, 213-033-015, 204-024-006). So 303 and 114 in the bottom trapezoid are left open, forcing 312 and 005 to be closed, forcing 204 and 321 to be open, forcing 600 and 501 to be closed. 600 and 501 are on the same disjoint triangle so we have a contradiction.
 +
 
 +
Therefore 024 is closed. Suppose 312 is open. This forces 114 to be closed, and leaevs 5 disjoint triangles (600-510-501, 411-321-312, 303-213-204, 222-132-123, 105-015-006). Therefore 402 in the bottom trapezoid is open, which forces 105 to be closed, which forces 015 and 006 to be open, which forces 213 and 303 to be closed, which are on the same disjoint triangle, so we have a contradiction.
 +
 
 +
Therefore 312 is closed. This leaves five disjoint triangles (510-240-213, 501-411-402, 222-132-123, 204-114-105, 303-033-006), and leaves 600, 420, 321, and 015 in the bottom trapezoid open. This forces 402 and 213 to be closed, which forces 510 and 411 to be open, leaving an open triangle at 510-420-411, so we have a contradiction.
 +
 
 +
(Case X) 330 and 132 closed and 231 and 033 open imply 051 is closed, and since 141 is closed and we have only one more removal in the top triangle it must be one of 240, 042, or 060. This leaves 150 open.
 +
 
 +
Suppose 321 is open. This forces 222 to be closed and leaves six disjoint triangles (600-420-402, 510-150-114, 411-321-312, 303-213-204, 105-015-006, 123-033-024), leaving 501 in the bottom trapezoid open. This forces 204 to be closed, which forces 303 to be open, leaving an open triangle at 501-321-303.
 +
 
 +
So 321 is closed. This leaves six disjoint triangles (600-420-402, 510-150-114, 501-231-204, 312-222-213, 123-033-024, 105-015-006) and leaves 303 and 411 in the bottom trapezoid open. This forces 213 and 006 to be closed, and forces 312, 222, 105, and 015 to be open. This forces 600 to be closed and 402 to be open, leaving an open triangle at 402-312-303. So we have a contradiction.
 +
 
 +
(Case Y) 330 and 033 are open, 330 and 033 open force 060 to be closed. With 141 closed there can be only one more removal, so suppose 150 is open (and note that if 150 was closed, we can use symmetry considering 051 to be open).
 +
 
 +
Suppose 600 is open. This forces 303 to be closed, and leaves six disjoint triangles (510-150-114, 420-330-321, 411-501-402, 222-312-213, 033-123-024, 015-105-006). So 204 in the bottom trapezoid is left open. 600 and 150 open implies 105 is closed, forcing 015 and 006 to be open, forcing 024 and 213 to be closed, forcing 312, 222, and 123 to be open, forcing 042 in the top triangle to be closed (so 051 and 240 are open). 051 and 015 open force 411 to be closed, which forces 501 to be open and leaves the open triangle 051-501-006.
 +
 
 +
So 600 is closed. This leaves six disjoint triangles (510-150-114, 420-330-321, 411-501-402, 222-312-213, 033-123-024, 015-105-006). 015 is the bottom trapezoid is then left open, forcing 312 and 411 to be closed. However, 312 and 411 are on the same disjoint triangle, so we have a contradiction.
 +
 
 +
(Case Z) 330, 141, and 033 are closed, and 231 and 132 are open. Suppose 051 is open (note that if this forms a contradiction, by symmetrical argument we can say both 150 and 051 are closed).
 +
 
 +
Suppose 114 is closed. This leaves six disjoint triangles (600-510-501, 402-312-303, 105-015-006, 411-231-213, 222-132-123, 321-051-024) and so 420 and 204 are open. This forces 501 to be closed, which forces 510 and 600 to be open, which forces 411 and 402 to be closed, which forces 213 and 303 to be open, leaving an open triangle at 213-303-204.
 +
 
 +
So 114 is open. Suppose 213 is closed. This leaves five disjoint triangles (600-420-402, 501-321-303, 411-051-015, 222-132-123, 204-024-006) and in the bottom trapezoid 510 and 105 are open. This forces 204 to be closed, forcing 024 and 006 to be open, forcing 015 to be closed, forcing 411 to be open, forcing 420 to be closed, forcing 402 to be open, leaving the open triangle 402-132-105.
 +
 
 +
So both 114 and 213 are open. Therefore 411 and 312 are closed. This leaves five disjoint triangles (600-510-501, 303-213-204, 105-015-006, 222-132-123, 321-051-024). The remaining points in the bottom trapezoid (420, 402) are then open, forcing 105 to be closed, forcing 015 and 006 to be open, forcing 024 to be closed. Also note 114 and 213 open force 123 to be closed, which forces 222 to be open, which forces 321 to be closed. 321 and 024 are on the same disjoint triangle, so we have a contradiction.
 +
 
 +
So 150 and 051 are both closed. However, this leaves the triangle 240-042-060 open, so case Z is impossible.
 +
 
 +
Since all ten solutions have been eliminated, case B is impossible.
 +
 
 +
* Suppose case C is true.
 +
 
 +
Suppose the trapezoid 600-420-321-303 used solution IV. There are three disjoint triangles 402-222-204, 213-123-114, and 105-015-006. The remainder of the points in the bottom trapezoid (420, 321, 510, 501, 402, 312, 024) must be left open. 024 being open forces either 114 or 015 to be removed.
 +
 
 +
Suppose 114 is removed. Then 213 is open, and with 312 open that forces 222 to be removed. Then 204 is open, and with 024 that forces 006 to be removed. So the bottom trapezoid is a removal configuration of 600-411-303-222-114-006, and the rest of the points in the bottom trapezoid are open. All 10 points in the top triangle form equilateral triangles with bottom trapezoid points, hence 10 removals in the top triangle would be needed (more than the 6 allowed), so 114 being removed doesn't work.
 +
 
 +
Suppose 015 is removed. Then 006-024 forces 204 to be removed. Regardless of where the removal in 123-213-114, the points 420, 321, 222, 024, 510, 312, 501, 402, 105, and 006 must be open. This forces top triangle removals at 330, 231, 042, 060, 051, 132, our remaining 6 removals on the top triangle. However, we have already removed 141, forcing one removal too many, so the trapezoid 600-420-321-303 doesn't use solution IV.
 +
 
 +
Suppose the trapezoid 600-420-321-303 uses solution VI. The trapezoid 303-123-024-006 can't be IV (already eliminated by symmetry) or VI' (leaves the triangle 402-222-204). Suppose the trapezoid 303-123-024-006 is solution VI. The removals from the bottom trapezoid are then 420, 501, 312, 123, 204, and 015, leaving the remaining points in the bottom trapezoid open. The remaining open points is forces 10 top triangle removals, so the trapezoid 600-420-321-303 doesn't use solution VI. Therefore the trapezoid 303-123-024-006 is solution V. The removals from the bottom trapezoid are then 420, 510, 312, 204, 114, and 105. The remaining points in the bottom trapezoid are open, and force 9 top triangle removals, hence the trapezoid 303-123-024-006 can't be V, and the solution for 600-420-321-303 can't be VI.
 +
 
 +
The solution VI' for the trapezoid 600-420-321-303 can be eliminated by the same logic by symmetry.
 +
 
 +
Therefore it is impossible for the bottom trapezoid to use only 6 removals.
 +
 
 +
We have determined cases A, B, and C to be impossible, therefore it impossible to form a triangle free configuration on the 7x7x7 lattice with only 12 removals. Therefore <math>\overline{c}^\mu_6 = 15</math>.
  
 
== n = 7 ==
 
== n = 7 ==
Line 163: Line 246:
 
<math>\overline{c}^\mu_{7} \leq 22</math>:
 
<math>\overline{c}^\mu_{7} \leq 22</math>:
  
Using the same eight extremal solutions to <math> \overline{c}^\mu_3 </math> as previous proofs:
+
Using the same ten extremal solutions to <math> \overline{c}^\mu_3 </math> as previous proofs:
  
 
Solution I: remove 300, 020, 111, 003<br>
 
Solution I: remove 300, 020, 111, 003<br>
Solution II: remove 030, 111, 201, 102<br>
+
Solution II (and 2 rotations): remove 030, 111, 201, 102<br>
 
Solution III (and 2 rotations): remove 030, 021, 210, 102<br>
 
Solution III (and 2 rotations): remove 030, 021, 210, 102<br>
 
Solution III' (and 2 rotations): remove 030, 120, 012, 201
 
Solution III' (and 2 rotations): remove 030, 120, 012, 201
Line 175: Line 258:
  
 
== n = 8 ==
 
== n = 8 ==
 
<math>\overline{c}^\mu_{8} \geq 22</math>:
 
 
 
 
008,026,044,062,107,125,134,143,152,215,251,260,314,341,413,431,440,512,521,620,701,800
 
  
 
== n = 9 ==
 
== n = 9 ==
  
<math>\overline{c}^\mu_{9} \geq 26</math>:
+
== n = 10 ==
  
027,045,063,081,126,135,144,153,207,216,252,270,315,342,351,360,405,414,432,513,522,531,603,630,720,801
+
== Computer data ==
 
+
== n = 10 ==
+
  
<math>\overline{c}^\mu_{10} \geq 29</math>:
+
From integer programming, we have
  
028,046,055,064,073,118,172,181,190,208,217,235,262,
+
* n=3, maximum 6 points, [http://abel.math.umu.se/~klasm/solutions-n=3-k=3-FUJ 10 solutions]
316,334,352,361,406,433,442,541,550,604,613,622,
+
* n=4, maximum 9 points, [http://abel.math.umu.se/~klasm/solutions-n=4-k=3-FUJ 1 solution]
721,730,901,1000
+
* n=5, maximum 12 points, [http://abel.math.umu.se/~klasm/solutions-n=5-k=3-FUJ 1 solution]
 +
* n=6, maximum 15 points, [http://abel.math.umu.se/~klasm/solutions-n=6-k=3-FUJ 4 solutions]
 +
* n=7, maximum 18 points, [http://abel.math.umu.se/~klasm/solutions-n=7-k=3-FUJ 85 solutions]
 +
* n=8, maximum 22 points, [http://abel.math.umu.se/~klasm/solutions-n=8-k=3-FUJ 72 solutions]
 +
* n=9, maximum 26 points, [http://abel.math.umu.se/~klasm/solutions-n=9-k=3-FUJ 183 solutions]
 +
* n=10, maximum 31 points, [http://abel.math.umu.se/~klasm/solutions-n=10-k=3-FUJ 6 solutions]
 +
* n=11, maximum 35 points, [http://abel.math.umu.se/~klasm/solutions-n=11-k=3-FUJ 576 solutions]
 +
* n=12, maximum 40 points, [http://abel.math.umu.se/~klasm/solutions-n=12-k=3-FUJ 876 solutions]
  
 
== General n ==
 
== General n ==
Line 222: Line 304:
 
The [[corners theorem]] tells us that <math>\overline{c}^\mu_n = o(n^2)</math> as <math>n \to \infty</math>.
 
The [[corners theorem]] tells us that <math>\overline{c}^\mu_n = o(n^2)</math> as <math>n \to \infty</math>.
  
By looking at those triples (a,b,c) with a+2b inside a Behrend set, one can obtain the lower bound <math>\overline{c}^\mu_n \geq n^2 \exp(-O(\sqrt{\log n}))</math>.
+
For any equilateral triangle (a+r,b,c),(a,b+r,c) and (a,b,c+r), the value y+2z forms an arithmetic progression of length 3.  A Behrend set is a finite set of integers with no arithmetic progression of length 3 (see [[http://arxiv.org/PS_cache/arxiv/pdf/0811/0811.3057v2.pdf this paper]]).  By looking at those triples (a,b,c) with a+2b inside a Behrend set, one can obtain the lower bound <math>\overline{c}^\mu_n \geq n^2 \exp(-O(\sqrt{\log n}))</math>.

Latest revision as of 21:25, 29 September 2015

Let [math]\overline{c}^\mu_n[/math] the largest subset of the triangular grid

[math]\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}[/math]

which contains no equilateral triangles [math](a+r,b,c), (a,b+r,c), (a,b,c+r)[/math] with [math]r \gt 0[/math]; call such sets triangle-free. (It is an interesting variant to also allow negative r, thus allowing "upside-down" triangles, but this does not seem to be as closely connected to DHJ(3).) Fujimura's problem is to compute [math]\overline{c}^\mu_n[/math] (OEIS A157795). This quantity is relevant to a certain hyper-optimistic conjecture.

We are also exploring issues raised by higher-dimensional Fujimura.

The following table was formed mostly by computer searches for optimal solutions. We also found human proofs for most of them (see below).

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13
[math]\overline{c}^\mu_n[/math] 1 2 4 6 9 12 15 18 22 26 31 35 40 46

n=0

[math]\overline{c}^\mu_0 = 1[/math]:

This is clear.

n=1

[math]\overline{c}^\mu_1 = 2[/math]:

This is clear.

n=2

[math]\overline{c}^\mu_2 = 4[/math]:

This is clear (e.g. remove (0,2,0) and (1,0,1) from [math]\Delta_2[/math]).

n=3

[math]\overline{c}^\mu_3 = 6[/math]:

For the lower bound, delete (0,3,0), (0,2,1), (2,1,0), (1,0,2) from [math]\Delta_3[/math].

For the upper bound: observe that with only three removals each of these (non-overlapping) triangles must have one removal:

  • set A: (0,3,0) (0,2,1) (1,2,0)
  • set B: (0,1,2) (0,0,3) (1,0,2)
  • set C: (2,1,0) (2,0,1) (3,0,0)

Consider choices from set A:

  • (0,3,0) leaves triangle (0,2,1) (1,2,0) (1,1,1)
  • (0,2,1) forces a second removal at (2,1,0) [otherwise there is triangle at (1,2,0) (1,1,1) (2,1,0)] but then none of the choices for third removal work
  • (1,2,0) is symmetrical with (0,2,1)

n=4

[math]\overline{c}^\mu_4=9[/math]:

The set of all [math](a,b,c)[/math] in [math]\Delta_4[/math] with exactly one of a,b,c =0, has 9 elements and is triangle-free. (Note that it does contain the equilateral triangle (2,2,0),(2,0,2),(0,2,2), so would not qualify for the generalised version of Fujimura's problem in which [math]r[/math] is allowed to be negative.)

Let [math]S\subset \Delta_4[/math] be a set without equilateral triangles. If [math](0,0,4)\in S[/math], there can only be one of [math](0,x,4-x)[/math] and [math](x,0,4-x)[/math] in S for [math]x=1,2,3,4[/math]. Thus there can only be 5 elements in S with [math]a=0[/math] or [math]b=0[/math]. The set of elements with [math]a,b\gt0[/math] is isomorphic to [math]\Delta_2[/math], so S can at most have 4 elements in this set. So [math]|S|\leq 4+5=9[/math]. Similar if S contain (0,4,0) or (4,0,0). So if [math]|S|\gt9[/math] S doesn’t contain any of these. Also, S can’t contain all of [math](0,1,3), (0,3,1), (2,1,1)[/math]. Similar for [math](3,0,1), (1,0,3),(1,2,1)[/math] and [math](1,3,0), (3,1,0), (1,1,2)[/math]. So now we have found 6 elements not in S, but [math]|\Delta_4|=15[/math], so [math]S\leq 15-6=9[/math].

Remark: curiously, the best constructions for [math]c_4[/math] uses only 7 points instead of 9.

n=5

[math]\overline{c}^\mu_5=12[/math]:

The set of all (a,b,c) in [math]\Delta_5[/math] with exactly one of a,b,c=0 has 12 elements and doesn’t contain any equilateral triangles.

Let [math]S\subset \Delta_5[/math] be a set without equilateral triangles. If [math](0,0,5)\in S[/math], there can only be one of (0,x,5-x) and (x,0,5-x) in S for x=1,2,3,4,5. Thus there can only be 6 elements in S with a=0 or b=0. The set of element with a,b>0 is isomorphic to [math]\Delta_3[/math], so S can at most have 6 elements in this set. So [math]|S|\leq 6+6=12[/math]. Similar if S contain (0,5,0) or (5,0,0). So if |S| >12 S doesn’t contain any of these. S can only contain 2 point in each of the following equilateral triangles:

(3,1,1),(0,4,1),(0,1,4)

(4,1,0),(1,4,0),(1,1,3)

(4,0,1),(1,3,1),(1,0,4)

(1,2,2),(0,3,2),(0,2,3)

(3,2,0),(2,3,0),(2,2,1)

(3,0,2),(2,1,2),(2,0,3)

So now we have found 9 elements not in S, but [math]|\Delta_5|=21[/math], so [math]S\leq 21-9=12[/math].

n=6

[math]\overline{c}^\mu_6 = 15[/math]:

[math]\overline{c}^\mu_6 \geq 15[/math] from the bound for general n.

Note that there are ten extremal solutions to [math]\overline{c}^\mu_3[/math]:

Solution I: remove 300, 020, 111, 003
Solution II (and 2 rotations): remove 030, 111, 201, 102
Solution III (and 2 rotations): remove 030, 021, 210, 102
Solution III' (and 2 rotations): remove 030, 120, 012, 201

Also consider the same triangular lattice with the point 020 removed, making a trapezoid. Solutions based on I-III are:

Solution IV: remove 300, 111, 003
Solution V: remove 201, 111, 102
Solution VI: remove 210, 021, 102
Solution VI': remove 120, 012, 201

The on the 7x7x7 triangular lattice triangle 141-411-114 must have at least one point removed. Remove 141, noting by symmetry any logic that follows will also work for either of the other two points.

Suppose we can remove all equilateral triangles on our 7×7x7 triangular lattice with only 12 removals.

Here, "top triangle" means the top four rows of the lattice (with 060 at top) and "bottom trapezoid" means the bottom three rows.

At least 4 of those removals must come from the top triangle (the solutions of [math] \overline{c}^\mu_3[/math] mentioned above).

The bottom trapezoid includes the overlapping trapezoids 600-420-321-303 and 303-123-024-006. If the solutions of these trapezoids come from V, VI, or VI', then 6 points have been removed. Suppose the trapezoid 600-420-321-303 uses the solution IV (by symmetry the same logic will work with the other trapezoid). Then there are 3 disjoint triangles 402-222-204, 213-123-114, and 105-015-006. Then 6 points have been removed. Therefore at least six removals must come from the bottom trapezoid.

To make a total of 12 removals there must be either:
Case A: 4 removals from the top triangle and 8 from the bottom trapezoid.
Case B: 5 removals from the top triangle and 7 from the bottom trapezoid.
Case C: 6 removals from the top triangle and 6 from the bottom trapezoid.

  • Suppose case A is true.

Because 141 is already removed, the solution to the top triangle must remove either solution I (remove 060, 330, 033), solution II (remove 060, 231, 132), solution IIb (remove 033, 150, 240) or solution IIc (remove 330, 051, 042)

Suppose I is the solution for the top triangle.

Suppose 222 is open. Then 420, 321, 123, and 024 must all be removed. This leaves five disjoint triangles which require removals in the bottom trapezoid (150-600-105, 051-501-006, 222-402-204, 231-411-213, 132-312-114); therefore the bottom trapezoid needs at least 9 removals, but we can only make 8, therefore 222 is closed.

Suppose 411 is open. Then 213 and 015 must be removed. This leaves five disjoint triangles such that each triangle must have exactly one removal (420-150-123, 321-051,024, 600-510-501, 402-312-303, 204-114-105), so the remaining point (006) must be open, forcing 501 to be removed. This makes 600 and 510 open, and based on the triangles 600-240-204 and 510-150-114 both 204 and 114 must both be removed, but 204 and 114 are on the same disjoint triangle, contradicting the statement that each triangle must have exactly one removal. So 411 is closed.

This leaves six disjoint triangles each which must have at least one removal (420-123-150, 321-024-051, 510-213-240, 312-015-042, 501-204-231, 402-105-132). This forces 600 and 006 to be open. Based on the triangles 006-501-051 and 600-204-240, this forces 501 and 204 to be open. But then there are no removals from the triangle 501-204-231, which is a contradiction. Therefore the solution of the top triangle cannot be I.

Suppose II is the solution for the top triangle.

There are seven disjoint triangles (150-600-105, 051-501-006, 222-402-204, 240-510-213, 042-312-015, 330-420-321, 033-123-024), therefore of the three points remaining in the bottom trapezoid (411, 303, 114) exactly one must be removed.

Suppose 411 is removed. Then 114 and 303 are open; 114 open forces 510 to be removed, forcing 213 to be open. 114 and 213 open force 123 to be closed, forcing 024 to be open. 024 open forces 222 to be closed, which forces 204 to be open, which leaves the triangle 213-303-204 open so we have a contradiction.

By symmetry 114 also can't be removed. Therefore we must remove 303. This leaves 411 and 114 open, forcing 510 and 015 closed. 510 and 015 closed forces 312 and 213 open, forcing 222 closed. 222 closed forces 402 and 204 open. 402 and 204 open force 501 and 105 closed. 510 and 105 closed force 600 and 006 open, leaving equilateral triangles 600-204-240 and 402-006-042 open. Therefore 303 can't be removed, and so the solution of the top triangle can't be II.

Suppose IIb is the solution for the top triangle.

Suppose 024 is open. This forces 420, 321, and 222 closed. Five disjoint triangles remain (510-600-501, 231-411-213, 132-312-114, 123-303-105, 024-204-006) so each must have exactly one point removed, and the remaining points in the bottom trapezoid (402, 015) must be open. This forces 312, 411, 510, and 006 closed, which then force the the other points in their disjoint triangles open (600, 501, 231, 213, 132, 114, 204). The triangle 501-231-204 is therefore open, so we have a contradiction, therefore 024 is closed.

Suppose 006 is open. This forces 600, 501 and 402 to be closed, and leaves five disjoint triangles (510-420-411, 321-231-222, 312-132-114, 303-213-204, 105-015-006) and so 123 must be open. This forces 222 closed, which forces 321 open, which forces 420 closed, which forced 510 and 411 open, which forces 213 closed, which forces 303 and 204 open, which forces 105 closed, which forces 015 and 006 to be open, leaving an open triangle at 411-015-051. Therefore we have a contradiction, so 006 is closed.

Given 024 and 006 closed, now note there are six disjoint triangles (600-510-501, 402-312-303, 204-114-105, 420-330-321, 222-132-123, 411-231-213). Therefore the remaining point in the bottom trapezoid 015 must be open, forcing 510, 411, and 312 to be closed. Using the disjoint triangles this forces 600, 501, 402, 303 and 213 to be open, which then forces 420 and 321 to be closed. Both 420 and 321 are on the same disjoint triangle, therefore we have a contradiction, so IIb can't be solution.

Note by symmetry, the same logic for IIb will apply for IIc. Therefore case A isn't true.

  • Suppose case B is true.

The row 330-231-132-033 has ten possible solutions (excluding reflections, which by symmetry will be handled by the same logic):

Case Q: open-open-open-open
Case R: closed-closed-closed-closed
Case S: closed-open-open-open
Case T: closed-open-closed-closed
Case U: open-closed-closed-closed
Case V: closed-open-closed-closed
Case W: closed-closed-open-open
Case X: closed-open-closed-open
Case Y: open-closed-closed-open
Case Z: closed-open-open-closed

Consider all 10 cases. Note in all these cases we are still assuming 141 is removed.

(Case Q) 330, 231, 132, 033 open forces 060, 150, 051, 240, 141, 042 closed, but the top triangle only allows 5 removals, so case Q forms a contradiction.

(Case R) 060-240-042 is left open, so case R forms a contradiction.

(Case S) 231, 132, and 033 open force 031 and 042 removed, which means from 240, 150, 061 there must be exactly one removal.

Suppose 213 is open. Then 411 and 015 are closed, and five disjoint triangles are left where each triangle must have exactly one removal (600-420-402, 501-321-303, 312-222-213, 204-105-114, 123-024-033). So the two remaining points in the bottom trapezoid (510 and 006) must be open. 510 and 006 open force 303 closed, which forces 321 and 501 open, which forces 204 closed, which forces 114 and 103 open, which forces 402 and 312 closed, forcing 222 open, leaving 321-231-222 as an open triangle, so we have a contradiction.

Therefore 213 is closed. This leaves six disjoint triangles (600-420-402, 501-231-204, 303-033-006, 411-321-312, 222-132-123, 114-024-015) which each have exactly one removal. Therefore 510 from the bottom trapezoid is open. Note since one of 150 and 060 must be open, then one of 114 or 015 must be closed; therefore 024 is open. This forces 123 closed, forcing 222 to be open, forcing 321 to be closed, forcing 411 and 312 open, forcing 421 closed, forcing 600 and 402 open, forcing 303 closed, forcing 006 open, forcing 204 closed, forcing 501 open, leaving the triangle 600-510-501 open and a contradiction.

(Case T) 231 is closed, and 330, 132, and 033 open force 060, 150, and 042 closed. Since 141 is already closed we have five removals from the top triangle, so 240 and 051 are open.

Suppose 024 is open. This forces 321 and 123 closed, leaving five disjoint triangles (600-510-501, 402-312-303, 204-114-105, 420-240-222, 213-033-015). Therefore 006 and 411 remaining in the bottom trapezoid are open, forcing 501, 303 and 015 closed, forcing 600, 510, 312, 402, and 213 open, forcing 222 closed, forcing 420 open, leaving the open triangle 420-510-411, so we have a contradiction.

Therefore 024 is closed. There are now six disjoint triangles (510-600-501, 330-420-321, 312-402-303, 132-222-123, 033-213-015, 114-204-105). This leaves 411 and 006 open, which forces 015 and 501 closed, which forces 510 and 213 open, leaving the triangle 240-510-213 open, so we have a contradiction.

(Case U) Given the removals 231, 132, 033, and 141, the only possible removal to not leave any equilateral triangles in the top triangle is 060. So 330, 240, 150, 051, and 042 are open.

Suppose 420 is open. This forces 321, 222, and 123 closed. This leaves five disjoint triangles (600-330-303, 510-420-411, 204-105-114, 501-051-006, and 312-042-015), so we have a contradiction.

Therefore 420 is closed. This leaves six disjoint triangles (600-330-303, 501-051-006, 204-114-105, 510-240-213, 411-321-312, 222-042-024). 015 in the bottom trapezoid is therefore open, forcing 312 and 411 closed, but 312 and 411 are on the same disjoint triangle, so we have a contradiction.

(Case V) Given the removals 330, 132, and 033, the only possible removal to not leave any equilateral triangles in the top triangle is 060. So 150, 051, 240, 042, and 231 are open.

Suppose 420 is open. Then 222 and 123 are closed, and we are left with 6 disjoint triangles (150-600-105, 240-510-213, 231-501-204, 024-114-015, 042-402-006, 411-321-312). This exceeds our limit of 7 removals in the bottom trapezoid, so we have a contradiction.

Therefore 420 is closed. Again we are left with the same 6 disjoint triangles (150-600-105, 240-510-213, 231-501-204, 024-114-015, 042-402-006, 411-321-312). Therefore 222, 123, and 303 are open. This forces 321, 024, and 105 to be closed, which then forces 411 and 015 to be open, forming an open triangle at 051-411-015, so we have a contradiction.

(Case W) Given the removals 330 and 231 with 132 and 033 open, 132 and 033 open force 042 closed. Given 141 is already closed, that leaves one more removal on the top triangle, which must be one of 060-150-051, so 240 must be open.

Suppose 024 is open. This forces 123 to be closed, and leaves 6 disjoint triangles (600-510-501, 420-240-222, 411-321-312, 402-132-105, 213-033-015, 204-024-006). So 303 and 114 in the bottom trapezoid are left open, forcing 312 and 005 to be closed, forcing 204 and 321 to be open, forcing 600 and 501 to be closed. 600 and 501 are on the same disjoint triangle so we have a contradiction.

Therefore 024 is closed. Suppose 312 is open. This forces 114 to be closed, and leaevs 5 disjoint triangles (600-510-501, 411-321-312, 303-213-204, 222-132-123, 105-015-006). Therefore 402 in the bottom trapezoid is open, which forces 105 to be closed, which forces 015 and 006 to be open, which forces 213 and 303 to be closed, which are on the same disjoint triangle, so we have a contradiction.

Therefore 312 is closed. This leaves five disjoint triangles (510-240-213, 501-411-402, 222-132-123, 204-114-105, 303-033-006), and leaves 600, 420, 321, and 015 in the bottom trapezoid open. This forces 402 and 213 to be closed, which forces 510 and 411 to be open, leaving an open triangle at 510-420-411, so we have a contradiction.

(Case X) 330 and 132 closed and 231 and 033 open imply 051 is closed, and since 141 is closed and we have only one more removal in the top triangle it must be one of 240, 042, or 060. This leaves 150 open.

Suppose 321 is open. This forces 222 to be closed and leaves six disjoint triangles (600-420-402, 510-150-114, 411-321-312, 303-213-204, 105-015-006, 123-033-024), leaving 501 in the bottom trapezoid open. This forces 204 to be closed, which forces 303 to be open, leaving an open triangle at 501-321-303.

So 321 is closed. This leaves six disjoint triangles (600-420-402, 510-150-114, 501-231-204, 312-222-213, 123-033-024, 105-015-006) and leaves 303 and 411 in the bottom trapezoid open. This forces 213 and 006 to be closed, and forces 312, 222, 105, and 015 to be open. This forces 600 to be closed and 402 to be open, leaving an open triangle at 402-312-303. So we have a contradiction.

(Case Y) 330 and 033 are open, 330 and 033 open force 060 to be closed. With 141 closed there can be only one more removal, so suppose 150 is open (and note that if 150 was closed, we can use symmetry considering 051 to be open).

Suppose 600 is open. This forces 303 to be closed, and leaves six disjoint triangles (510-150-114, 420-330-321, 411-501-402, 222-312-213, 033-123-024, 015-105-006). So 204 in the bottom trapezoid is left open. 600 and 150 open implies 105 is closed, forcing 015 and 006 to be open, forcing 024 and 213 to be closed, forcing 312, 222, and 123 to be open, forcing 042 in the top triangle to be closed (so 051 and 240 are open). 051 and 015 open force 411 to be closed, which forces 501 to be open and leaves the open triangle 051-501-006.

So 600 is closed. This leaves six disjoint triangles (510-150-114, 420-330-321, 411-501-402, 222-312-213, 033-123-024, 015-105-006). 015 is the bottom trapezoid is then left open, forcing 312 and 411 to be closed. However, 312 and 411 are on the same disjoint triangle, so we have a contradiction.

(Case Z) 330, 141, and 033 are closed, and 231 and 132 are open. Suppose 051 is open (note that if this forms a contradiction, by symmetrical argument we can say both 150 and 051 are closed).

Suppose 114 is closed. This leaves six disjoint triangles (600-510-501, 402-312-303, 105-015-006, 411-231-213, 222-132-123, 321-051-024) and so 420 and 204 are open. This forces 501 to be closed, which forces 510 and 600 to be open, which forces 411 and 402 to be closed, which forces 213 and 303 to be open, leaving an open triangle at 213-303-204.

So 114 is open. Suppose 213 is closed. This leaves five disjoint triangles (600-420-402, 501-321-303, 411-051-015, 222-132-123, 204-024-006) and in the bottom trapezoid 510 and 105 are open. This forces 204 to be closed, forcing 024 and 006 to be open, forcing 015 to be closed, forcing 411 to be open, forcing 420 to be closed, forcing 402 to be open, leaving the open triangle 402-132-105.

So both 114 and 213 are open. Therefore 411 and 312 are closed. This leaves five disjoint triangles (600-510-501, 303-213-204, 105-015-006, 222-132-123, 321-051-024). The remaining points in the bottom trapezoid (420, 402) are then open, forcing 105 to be closed, forcing 015 and 006 to be open, forcing 024 to be closed. Also note 114 and 213 open force 123 to be closed, which forces 222 to be open, which forces 321 to be closed. 321 and 024 are on the same disjoint triangle, so we have a contradiction.

So 150 and 051 are both closed. However, this leaves the triangle 240-042-060 open, so case Z is impossible.

Since all ten solutions have been eliminated, case B is impossible.

  • Suppose case C is true.

Suppose the trapezoid 600-420-321-303 used solution IV. There are three disjoint triangles 402-222-204, 213-123-114, and 105-015-006. The remainder of the points in the bottom trapezoid (420, 321, 510, 501, 402, 312, 024) must be left open. 024 being open forces either 114 or 015 to be removed.

Suppose 114 is removed. Then 213 is open, and with 312 open that forces 222 to be removed. Then 204 is open, and with 024 that forces 006 to be removed. So the bottom trapezoid is a removal configuration of 600-411-303-222-114-006, and the rest of the points in the bottom trapezoid are open. All 10 points in the top triangle form equilateral triangles with bottom trapezoid points, hence 10 removals in the top triangle would be needed (more than the 6 allowed), so 114 being removed doesn't work.

Suppose 015 is removed. Then 006-024 forces 204 to be removed. Regardless of where the removal in 123-213-114, the points 420, 321, 222, 024, 510, 312, 501, 402, 105, and 006 must be open. This forces top triangle removals at 330, 231, 042, 060, 051, 132, our remaining 6 removals on the top triangle. However, we have already removed 141, forcing one removal too many, so the trapezoid 600-420-321-303 doesn't use solution IV.

Suppose the trapezoid 600-420-321-303 uses solution VI. The trapezoid 303-123-024-006 can't be IV (already eliminated by symmetry) or VI' (leaves the triangle 402-222-204). Suppose the trapezoid 303-123-024-006 is solution VI. The removals from the bottom trapezoid are then 420, 501, 312, 123, 204, and 015, leaving the remaining points in the bottom trapezoid open. The remaining open points is forces 10 top triangle removals, so the trapezoid 600-420-321-303 doesn't use solution VI. Therefore the trapezoid 303-123-024-006 is solution V. The removals from the bottom trapezoid are then 420, 510, 312, 204, 114, and 105. The remaining points in the bottom trapezoid are open, and force 9 top triangle removals, hence the trapezoid 303-123-024-006 can't be V, and the solution for 600-420-321-303 can't be VI.

The solution VI' for the trapezoid 600-420-321-303 can be eliminated by the same logic by symmetry.

Therefore it is impossible for the bottom trapezoid to use only 6 removals.

We have determined cases A, B, and C to be impossible, therefore it impossible to form a triangle free configuration on the 7x7x7 lattice with only 12 removals. Therefore [math]\overline{c}^\mu_6 = 15[/math].

n = 7

[math]\overline{c}^\mu_{7} \leq 22[/math]:

Using the same ten extremal solutions to [math] \overline{c}^\mu_3 [/math] as previous proofs:

Solution I: remove 300, 020, 111, 003
Solution II (and 2 rotations): remove 030, 111, 201, 102
Solution III (and 2 rotations): remove 030, 021, 210, 102
Solution III' (and 2 rotations): remove 030, 120, 012, 201

Suppose the 8x8x8 lattice can be triangle-free with only 13 removals.

Slice the lattice into region A (070-340-043) region B (430-700-403) and region C (034-304-007). Each region must have at least 4 points removed. Note there is an additional disjoint triangle 232-322-223 that also must have a point removed. Therefore the points 331, 133, and 313 are open. 331-313 open means 511 must be removed, 331-133 open means 151 must be removed, and 133-313 open means 115 must be removed. Based on the three removals, the solutions for regions A, B, and C must be either I or II. All possible combinations for the solutions leave several triangles open (for example 160-520-124). So we have a contradiction, and [math] \overline{c}^\mu_7 \leq 22 [/math].

n = 8

n = 9

n = 10

Computer data

From integer programming, we have

General n

A lower bound for [math]\overline{c}^\mu_n[/math] is 2n for [math]n \geq 1[/math], by removing (n,0,0), the triangle (n-2,1,1) (0,n-1,1) (0,1,n-1), and all points on the edges of and inside the same triangle. In a similar spirit, we have the lower bound

[math]\overline{c}^\mu_{n+1} \geq \overline{c}^\mu_n + 2[/math]

for [math]n \geq 1[/math], because we can take an example for [math]\overline{c}^\mu_n[/math] (which cannot be all of [math]\Delta_n[/math]) and add two points on the bottom row, chosen so that the triangle they form has third vertex outside of the original example.

An asymptotically superior lower bound for [math]\overline{c}^\mu_n[/math] is 3(n-1), made of all points in [math]\Delta_n[/math] with exactly one coordinate equal to zero.

A trivial upper bound is

[math]\overline{c}^\mu_{n+1} \leq \overline{c}^\mu_n + n+2[/math]

since deleting the bottom row of a equilateral-triangle-free-set gives another equilateral-triangle-free-set. We also have the asymptotically superior bound

[math]\overline{c}^\mu_{n+2} \leq \overline{c}^\mu_n + \frac{3n+2}{2}[/math]

which comes from deleting two bottom rows of a triangle-free set and counting how many vertices are possible in those rows.

Another upper bound comes from counting the triangles. There are [math]\binom{n+2}{3}[/math] triangles, and each point belongs to n of them. So you must remove at least (n+2)(n+1)/6 points to remove all triangles, leaving (n+2)(n+1)/3 points as an upper bound for [math]\overline{c}^\mu_n[/math].

Asymptotics

The corners theorem tells us that [math]\overline{c}^\mu_n = o(n^2)[/math] as [math]n \to \infty[/math].

For any equilateral triangle (a+r,b,c),(a,b+r,c) and (a,b,c+r), the value y+2z forms an arithmetic progression of length 3. A Behrend set is a finite set of integers with no arithmetic progression of length 3 (see [this paper]). By looking at those triples (a,b,c) with a+2b inside a Behrend set, one can obtain the lower bound [math]\overline{c}^\mu_n \geq n^2 \exp(-O(\sqrt{\log n}))[/math].