Difference between revisions of "Fujimura.tex"

From Polymath1Wiki
Jump to: navigation, search
Line 1: Line 1:
 
\section{Fujimura's problem}\label{fujimura-sec}
 
\section{Fujimura's problem}\label{fujimura-sec}
 +
Let $\overline{c}^\mu_n$ be the size of the largest subset of the trianglular grid
 +
$$\Delta_n := \{(a,b,c)\in \mathbb{Z}^3_+ : a+b+c = n\}$$
 +
which contains no equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ with $r>0$.  These are upward-pointing equilateral triangles.  We shall refer to such sets as 'triangle-free'.
 +
(Kobon Fujimura is a prolific inventor of puzzles, and in [http://www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm this] puzzle asked the related question of eliminating all equilateral triangles.)
  
This is where we will discuss upper and lower bounds on Fujimura's problem. Please edit at
+
The following table was formed mostly by computer searches for optimal solutions. We also found human proofs for most of them (see [http://michaelnielsen.org/polymath1/index.php?title=Fujimura's_problem here]).
  
http://michaelnielsen.org/polymath1/index.php?title=Fujimura.tex
+
\begin{figure}\centerline{
 +
\begin{tabular}[l|lllllllllllll]
 +
$n$                        & 0 & 1 & 2 & 3 & 4 &  5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 & 13\\
 +
\hline $\overline{c}^\mu_n$ & 1 & 2 & 4 & 6 & 9 & 12 & 15 & 18 & 22 & 26 & 31 & 35 & 40 & 46
 +
\end{tabular}\label{lowFujimura}\caption{Fujimura numbers}}
 +
 
 +
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 of $\overline{c}^\mu_n \geq n^2 exp(-O(\sqrt{\log n}))$.
 +
 
 +
It can be shown that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$, but the details are outside the scope of this paper.

Revision as of 10:46, 10 July 2009

\section{Fujimura's problem}\label{fujimura-sec} Let $\overline{c}^\mu_n$ be the size of the largest subset of the trianglular grid $$\Delta_n := \{(a,b,c)\in \mathbb{Z}^3_+ : a+b+c = n\}$$ which contains no equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ with $r>0$. These are upward-pointing equilateral triangles. We shall refer to such sets as 'triangle-free'. (Kobon Fujimura is a prolific inventor of puzzles, and in this puzzle asked the related question of eliminating all equilateral triangles.)

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

\begin{figure}\centerline{ \begin{tabular}[l|lllllllllllll] $n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\ \hline $\overline{c}^\mu_n$ & 1 & 2 & 4 & 6 & 9 & 12 & 15 & 18 & 22 & 26 & 31 & 35 & 40 & 46 \end{tabular}\label{lowFujimura}\caption{Fujimura numbers}}

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 of $\overline{c}^\mu_n \geq n^2 exp(-O(\sqrt{\log n}))$.

It can be shown that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$, but the details are outside the scope of this paper.