# Difference between revisions of "Fujimura's problem"

Let $\overline{c}^\mu_n$ the largest subset of the triangular grid

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

which contains no equilateral triangles. Fujimura's problem is to compute $\overline{c}^\mu_n$. This quantity is relevant to a certain "hyper-optimistic" version of DHJ(3).

## n=0

It is clear that $\overline{c}^\mu_0 = 1$.

## n=1

It is clear that $\overline{c}^\mu_1 = 2$.

## n=2

It is clear that $\overline{c}^\mu_2 = 4$ (e.g. remove (0,2,0) and (1,0,1) from $\Delta_2$).

## n=3

Deleting (0,3,0), (0,2,1), (2,1,0), (1,0,2) from $\Delta_3$ shows that $\overline{c}^\mu_3 \geq 6$. In fact $\overline{c}^\mu_3 = 6$: just note (3,0,0) or something symmetrical has to be removed, leaving 3 triangles which do not intersect, so 3 more removals are required.

## n=4

[Cleanup required here]

$\overline{c}^\mu_4=9:$

The set of all $(a,b,c)$ in $\Delta_4$ with exactly one of a,b,c =0, has 9 elements and doesn’t contain any equilateral triangles.

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

could you give your explicit list for removals from \overline{c}^\mu_4? I am unable to reproduce a triangle-free configuration from your description.

For example, (4,0,0) (0,4,0) (0,0,4) (2,1,1) (1,1,2) (1,2,1) leaves the triangle (2,2,0) (0,2,2) (2,0,2).

## n=5

[Cleanup required here]

$\overline{c}^\mu_5=12$

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

Let $S\subset \Delta_5$ be a set without equilateral triangles. If $(0,0,5)\in S$, 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 $\Delta_3$, so S can at most have 6 elements in this set. So $|S|\leq 6+6=12$. 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 $|\Delta_5|=21$, so $S\leq 21-9=12$.

## General n

[Cleanup required here]

A lower bound for $\overline{c}^\mu_n$ is 3(n-1), made of all points in $\Delta_n$ with exactly one coordinate equal to zero.

A trivial upper bound is

$\overline{c}^\mu_{n+1} \leq \overline{c}^\mu_n + n+2$

since deleting the bottom row of a equilateral-triangle-free-set gives another equilateral-triangle-free-set.