Difference between revisions of "Fujimura.tex"

From Polymath1Wiki
Jump to: navigation, search
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
\section{Fujimura's problem}\label{fujimura-sec}
 
\section{Fujimura's problem}\label{fujimura-sec}
  
This is where we will discuss upper and lower bounds on Fujimura's problem. Please edit at
+
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.)
  
http://michaelnielsen.org/polymath1/index.php?title=Fujimura.tex
+
The table in Figure \ref{lowFujimura} was formed mostly by computer searches for optimal solutions. We also found human proofs for most of them (see {\tt http://michaelnielsen.org/polymath1/index.php?title=Fujimura's\_problem}).
 +
 
 +
\begin{figure}
 +
\centerline{
 +
\begin{tabular}{l|llllllllllllll}
 +
$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}
 +
\end{figure}
 +
 
 +
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 {\tt http://arxiv.org/PS\_cache/arxiv/pdf/0811/0811.3057v2.pdf}). 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 by a `corners theorem' of Ajtai and Szemeredi \cite{ajtai} that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$.
 +
 
 +
An explicit lower bound is $3(n-1)$, made of all points in $\Delta_n$ with exactly one coordinate equal to zero. 
 +
 
 +
An explicit upper bound comes from counting the triangles. There are $\binom{n+2}{3}$ 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 $\overline{c}^\mu_n$.

Latest revision as of 06:46, 27 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 table in Figure \ref{lowFujimura} was formed mostly by computer searches for optimal solutions. We also found human proofs for most of them (see {\tt http://michaelnielsen.org/polymath1/index.php?title=Fujimura's\_problem}).

\begin{figure} \centerline{ \begin{tabular}{l|llllllllllllll} $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} \end{figure}

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 {\tt http://arxiv.org/PS\_cache/arxiv/pdf/0811/0811.3057v2.pdf}). 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 by a `corners theorem' of Ajtai and Szemeredi \cite{ajtai} that $\overline{c}^\mu_n = o(n^2)$ as $n \rightarrow \infty$.

An explicit lower bound is $3(n-1)$, made of all points in $\Delta_n$ with exactly one coordinate equal to zero.

An explicit upper bound comes from counting the triangles. There are $\binom{n+2}{3}$ 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 $\overline{c}^\mu_n$.