\documentclass[12pt]{article} %\usepackage{isolatin1} \usepackage{amsmath} \usepackage{amsthm} %\usepackage{listings} \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 %% \begin{document} \vspace*{-40pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A07} \vskip 40pt \begin{center} {\bf PARTITIONS INTO SUM-FREE SETS} \vskip 20pt {\bf Peter F. Blanchard}\\ {\smallit Miami University, Hamilton, OH 45011, USA}\\ {\tt blanchpf@muohio.edu}\\ \vskip 10pt {\bf Frank Harary}\footnote{Frank passed away January 4, 2005. The date 1-4-'05 is a triple of the type studied in this paper.}\\ {\smallit New Mexico State University, Las Cruces, NM 88003, USA}\\ {\tt fnh@crl.nmsu.edu}\\ \vskip 10pt {\bf Rog\'{e}rio Reis}\\ {\smallit Universidade do Porto, DCC-FC \& LIACC, Porto, Portugal}\\ {\tt rvr@ncc.up.pt}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 10/23/04, Revised: 7/11/05, Accepted: 2/4/06, Published: 3/9/06} \centerline{\bf Abstract} \vskip 20pt \noindent We define a sum as a set $\{x,y,z\}$ of distinct natural numbers such that $x+y=z$, and let $N_m=\{1,2,\ldots,m\}$. We introduce a new sequence $h(n)$ defined as the smallest $s$ such that there is no partition of $N_s$ into $n$ sum-free parts. We determine $h(n)$ for $n=3,4$ after easily noting that $h(1)=3$ and $h(2)=9$. We find that $h(3)=24$ and $h(4)=67$ using a computer program. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A07\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt %\lstset{language=C, basicstyle=\ttfamily} \newtheorem{thm}{Theorem} \newtheorem*{nnthm}{Theorem} \newtheorem*{conj}{Conjecture} \section*{\normalsize 1. Introduction} \label{sec:intr} In this paper we investigate a variation on a celebrated theorem of Issai Schur. In what follows, $N = \{1,2,3,\ldots\}$ refers to the set of positive integers, and $N_m = \{1,2,3,\ldots,m\}$ denotes an initial segment of length $m$. A {\it finite coloring} of a set $A$ is simply a partition of $A$ into finitely many disjoint subsets: $A = A_1\cup A_2\cup\cdots \cup A_m$. One thinks of the elements of $A_i$ as having color $i$. Alternately, such a partition defines a function $\pi: A\to N_n$. The color classes then are the inverse images $A_i = \pi^{-1}(i)$. We will also refer to this as an $m$-coloring of $A$. Any set $B\subseteq A_i$ is referred to as {\it monochromatic}, as all of its elements are of the same color. Ramsey Theory on the natural numbers has a long and varied history. Nine pages into Graham, Rothschild, and Spencer's \cite{graham80:_ramsey_theor} standard reference on the subject, one finds the theorems of Van der Waerden, Schur, and Rado listed among the 'Super Six'. Each concerns colorings of $N$ and asserts the existence of some type of monochromatic set in any finite coloring of $N_n$ if $n$ is sufficiently large. Briefly, Van der Waerden's theorem asserts the existence of monochromatic arithmetic progressions, Schur's theorem asserts the existence of monochromatic solutions to $x+y-z=0$, and Rado's theorem extends Schur's theorem to systems of linear equations. \begin{nnthm}[Schur's Theorem] For any $m>0$, there is a finite natural number $s=s(m)$ so that for any finite coloring $\pi: N_s \to N_m$ there exist $x,y$ so that $\{x,y,x+y\}$ is monochromatic. \end{nnthm} The standard derivation of Schur's Theorem from Ramsey's Theorem is as follows: Given an $m$-coloring $\pi: [n] \to [m]$, construct an $m$-coloring $\pi^\prime: K_{n+1} \to [m]$ of a complete graph on the vertices $[1,n+1]$ so that each edge $ij$ is colored $\pi(j-i)$, i.e. $\pi^\prime(ij) = \pi(j-i)$. If $n$ is large enough, Ramsey's theorem asserts the existence of vertices $a,b,c$, such that $\pi^\prime(ab) = \pi^\prime(bc) = \pi^\prime(ac)$. Now $(b-a) + (c-b) = (c-a)$ gives the required monochromatic solution $x+y=z$ where $x=b-a, y=c-b$, and $z = c-a$. In this case, nothing prevents $x=y$. Indeed, in the case of $2$ colors, $s(2) = 5$, and it is not hard to see $3/4$ of all $2$-colorings of $[1,5]$ have monochromatic solutions of the form $x+x=z$. In the following theorem, we explore here the case in which $x\neq y$. \begin{thm} \label{maintheorem} For any $m>0$, there is a finite natural number $h=h(m)$ so that for any finite coloring $\pi: N_h \to N_m$ there exist $x\neq y$ so that $\{x,y,x+y\}$ is monochromatic. Moreover, $h(1) = 3$, $h(2) = 9$, $h(3) = 24$, and $h(4) = 67$. \end{thm} In Section 3 we discuss the three smallest values in the context of combinatorial games. Sections 2 and 3 for computing $h(m)$. Sections 6 and 7 concern values of $h(m)$ for $m\geq 4$, while Section 8 contains further discussion relating values $h(m)$ to combinatorial games. The appendix contains {\tt C}-language computer code implementing the algorithm discussed earlier. \vskip 30pt \section*{\normalsize 2. Proof of Theorem \ref{maintheorem}} \label{sec:two} \begin{proof} Ramsey's theorem \cite{graham80:_ramsey_theor} guarantees the existence of a number $t = R(l;m)$ so that any $m$-coloring of (the edges of) a complete graph $K_t$ must have a monochromatic collection of edges forming a complete graph on $l$ vertices. In particular, given, $m>0$, let $t = R(4;m)$. We claim that $h(m) \leq t - 1$. For any $m$-coloring $\pi:[t-1]\to [m]$, define an $m$-coloring $\pi^\prime: K_{t}\to [m]$ by $\pi^\prime(ij) = \pi(|j-i|)$. Here $ij$ represents the edge of $K_q$ connecting vertices $i$ and $j$. $\pi^\prime$ is well-defined as $1\leq |j-i|\leq t-1$. By Ramsey's theorem, there is a set $\{w,x,y,z\}$ of vertices forming a monochromatic $K_4$. Since the edges are monochromatic in the coloring $\pi^\prime$, it follows that the differences $x-w,y-x,y-w,z-y,z-x,z-w$ are monochromatic for $\pi$. If $w-x = y-x= z-y=a$ then $y-w = 2a$ and $z-w = (z-y) + (y-w)$ yields the monochromatic triple $\{a,2a,3a\}$. Otherwise, either $x-w\neq y-x$ yields the monochromatic triple $\{x-w,y-x,y-w\}$ or $z-y\neq y-x$, yields $\{y-x,z-y,z-x\}$. \end{proof} \vskip 30pt \section*{\normalsize 3. The Three Smallest $h$-numbers} \label{sec:smallest} Consider a two person game, with players $A$ and $B$, that begins with a small number of empty columns in which $A$ places number $1$ in any column, then $B$ places number $2$ in either column, etc. The column in which a number is placed must not be the sum of two numbers above. The last player who can move is the winner $W$. Here is an example of a game with 3 columns, in which player $A$ places $1$ in column $C_1$ and wins because eventually player $B$ cannot place number $12$ in any column. Note that $3'$ means that $3$ is forced to be placed in a different column, and $8^{\star}$ means $8$ is forced in a unique column. \begin{center} \begin{tabular}[c]{c|c|c} $\mathbf{C_1}$ & $\mathbf{C_2}$ & $\mathbf{C_3}$\\\hline $1$ & $3'$ & $4$\\ $2$ & $5$ & $6$\\ $7$ & $9$ & $8^{\star}$\\ $10$ & & $11$ \end{tabular} \end{center} This game is completed since number $12$ cannot be placed, so $W=A$. We define a sum as a set $\{x,y,z\}$ of distinct natural numbers such that $x+y=z$. In this context we think of $h(n)$ as the smallest $m$ such that there is no partition of $N_m$ into $n$ sum-free parts. Trivially, \begin{equation} \label{eq:1} h(1)=3 \end{equation} with the only solution: \begin{center} \begin{tabular}[c]{c} $\mathbf{C_1}$\\\hline $1^{\star}$\\ $2^{\star}$ \end{tabular} \,. \end{center} In the same way it is easy to verify that \begin{equation} \label{eq:2} h(2)=9 \end{equation} and in this case also there is only one solution: \begin{center} \begin{tabular}[c]{l|l} $\mathbf{C_1}$ & $\mathbf{C_2}$ \\\hline $1$ & $3^{\star}$\\ $2$ & $5^{\star}$\\ $4$ & $6^{\star}$\\ $8^{\star}$ & $7$ \end{tabular}\,. \end{center} This shows that $h(2)>8$. Only a few cases must be considered to see that $h(2)=9$. Let $\pi:N_9\rightarrow N_2$ be a placement in the 2 columns. If $1$ and $2$ are in two different columns we are quickly done. If $\pi(1)=1$, $\pi(2)=2$ and $\pi(i)=1$ for any $i\geq 4$, then $\pi(i\pm 1)=2$ leads to the sum $\{2,i-1,i+1\}$ in the same column. Avoiding $\pi(i)=1$ leads to $\pi(4)=\pi(5)=\pi(6)=2$ which fails, because then the sum $\{2,4,6\}$ would be in in the same column. Thus let $\pi(1)=\pi(2)=1$ so $\pi(3)$ must be $2$. If $\pi(4)=1$, then to avoid sums $\{1,4,5\}$ and $\{2,4,6\}$, $\pi(5)=\pi(6)=2$ are forced, and then because $3$, $5$ and $6$ are in column $2$, we would need $\pi(8)=\pi(9)=1$, but then the sum $\{1,8,9\}$ would be in column $1$. Continuing to assume $\pi(1)=\pi(2)=1$ and $\pi(3)=2$, if $\pi(4)=2$, then to avoid the sum $\{3,4,7\}$ in the second column, $\pi(7)=1$ is forced, which in turn forces $\pi(6)=\pi(8)=2$, but now we would get either $\{3,6,9\}$ or $\{2,7,9\}$ in the same column. It was proven similarly that for $c=3$ columns the maximum possible length of the game is $23$, so \begin{equation} \label{eq:3} h(3)=24. \end{equation} All three examples of such games are \begin{center} \begin{tabular}[c]{ccccc} \begin{tabular}[c]{c|c|c} $\mathbf{C_1}$ & $\mathbf{C_2}$ & $\mathbf{C_3}$\\\hline $1$ & $3'$ & $9^{\star}$\\ $2$ & $5'$ & $10^{\star}$\\ $4$ & $6$ & $12^{\star}$\\ $8'$ & $7$ & $13^{\star}$\\ $11$ & $19^{\star}$ & $14$\\ $16$ & $21'$ & $15$\\ $22^{\star}$ & $23^{\star}$ & $17'$\\ & & $18$\\ & & $20$\\ && \end{tabular} &\ & \begin{tabular}[c]{c|c|c} $\mathbf{C_1}$ & $\mathbf{C_2}$ & $\mathbf{C_3}$\\\hline $1$&$3'$&$9^{\star}$\\ $2$&$5'$&$10^{\star}$\\ $4$&$6$&$12^{\star}$\\ $8'$&$7$&$13^{\star}$\\ $11$&$19^{\star}$&$14$\\ $17$&$21^{\star}$&$15$\\ $22^{\star}$&$23^{\star}$&$16$\\ &&$18'$\\ &&$20$\\ && \end{tabular}&\ & \begin{tabular}[c]{c|c|c} $\mathbf{C_1}$ & $\mathbf{C_2}$ & $\mathbf{C_3}$\\\hline $1$&$3'$&$9^{\star}$\\ $2$&$5'$&$10^{\star}$\\ $4$&$6$&$12^{\star}$\\ $8'$&$7$&$13^{\star}$\\ $11$&$19^{\star}$&$14$\\ $22^{\star}$&$21'$&$15$\\ &$23^{\star}$&$16$\\ &&$17$\\ &&$18$\\ &&$20$ \end{tabular} \end{tabular} \end{center} These examples can be simply represented by their column sequences: $$\begin{array}[c]{c} \left[ 11212221331333313323212 \right]\\ \left[ 11212221331333331323212 \right]\\ \left[ 11212221331333333323212 \right] \end{array}$$ \vskip 30pt \section*{\normalsize 4. Brute Force Approach} A brute force approach to the problem is very easy to state: a program that tries every possible different choice of placement of each integer, with a depth-first search for example, that covers all possible game configurations. The longest one is the answer to our question. To be sure that the answer we are getting from the computer, is right, and not only a bunch of different game configurations, we only need to verify that the program does not skip any possibility. That is the purpose of the following two sections. It is easy to see that the whole game configuration can be represented by the sequence of columns chosen by the players to place the numbers, as those numbers are determined by the natural order of $N$. With this observation the longest games for the problem $c=3$ can be completely described by the strings above. As usual denote the Kleene closure \cite{kleene56:_repres} of $A$ by $A^{\star}$; game descriptions can be seen as members of $N_n^{\star}$, that is, the set of sequences of elements of $N_n$. To simplify the representation, and because we will need computationally fast implementations of these data structures, let us assume we have an upper bound for the maximum length of the game for a given $n$. Let us represent that limit by $\mathtt{L}$. Then, we concatenate a string of zeros to a string description of a game, so that the result always has length $\mathtt{L}$. Now we can see a game description as a member of $$(\{0\}\cup N_n)^{\mathtt{L}}.$$ This can be easily and efficiently represented in a computer data structure. Here brute force means to generate all the possible elements of $$(\{0\}\cup N_n)^{\mathtt{L}}\cap (N_n)^{\star}\{0\}^{\star}$$ that stand for legal configurations of the game. The problem is that the cost of computing whether an integer is placeable in a given column is too high. A direct evaluation from the data of the game configuration, for the $m$th placement will have to compute in the worst case $(m-1)(m-2)$ additions and comparisons, for a configuration with all previous placements in the same column. We can estimate an average of $n(\frac{m}{n})^2$, supposing an even distribution of placements by the different columns. This is clearly too much for a computation that, in the case $n=4$, is going to be repeated a number of times that we only know\footnote{Assuming that the solution already known for the problem is indeed the longest.} to be bounded by $4^{67}.$ A solution for this problem is to use another data structure, that can store the ``forbidden values'' for each column, and that can be calculated in an incremental way. For each column we can store the values that can be obtained by adding two of the members of the column. We call that data structure {\tt Base} and use it so that {\tt Base[i][j]} is $0$ means that the number {\tt j} can be ``legally'' placed in column {\tt i+1}. Testing whether a move is legal is now much more efficient as its order is $O(m)$. But the backtracking of a move will still take too much time. We are already storing in {\tt Base[col][i]} not simply a $1$ when the integer {\tt i} is ``forbidden'' in that {\tt col}, but the number of different ways it is possible to write it as a sum of two elements of the same column. In this way, backtracking will be easier when one of the contributing parcels of {\tt i} is to be removed from column {\tt col} as we only need subtract $1$ from this value. We keep, in another data array, the list of integers that each {\tt i} contributes to ``outcast,'' then backtracking can be done with minimal computational effort, that is, $O(m)$. \vskip 30pt \section*{\normalsize 5. Trimming the Tree} \label{sec:trimming-tree} We can significantly improve the computational speed by pruning the search tree whenever we know that all new solutions will be permutations of the ones already found. Without loss of generality we can place the number $1$ in column $C_1$ and save time by reducing the tree to $1/n$ (in this case $1/4$). But this method can be generalized, resulting in a much more effective pruning. Let us consider again the domain $$(\{0\}\cup N_n)^{\mathtt{L}}\cap N_n^{\star}\{0\}^{\star}.$$ Our depth-first descent corresponds to the lexicographic enumeration. We denote by $[a/b]s$ the application of the substitution of $a$ for each $b$ in the string $s$. Then we observe that for any string $$s = a_1a_2\cdots a_{m-1}a_m a_{m+1}\cdots a_k$$ let $$s'=[(max\{a_1,\ldots, a_{m-1}\}+1)/a_m,a_m/(max\{a_1,\ldots, a_{m-1}\}+1)]s$$ if $a_m > 1 + max\{a_1,\ldots, a_{m-1}\}$, then $$s'\\ \#define MAX(X,Y) ((X>Y)?X:Y)\\ \#define MIN(X,Y) ((X>Y)?Y:X) \#define COLS 4\\ \#define L 68 // upper bound to exptd sols\\ \#define LL 64 // lower bound intrstng sols \#define excludedp(N) (Base[0][N]\&Base[1][N]\&Base[2][N]\&Base[3][N]\&Base[4][N]) \#define colp(X) (!Base[X][wmax+1]) short int Base[COLS][L+1], wsol[L];\\ int nums[L+1][L+1], wmax = 0, max=0; void updatesol()\{\vskip -10pt \hskip 10pt int i, max=0;\vskip -10pt \hskip 10pt static lprint = 0; \hskip 10pt max = wmax;\vskip -10pt \hskip 15pt if(max > LL \&\& max >= lprint)\{\vskip -10pt \hskip 20pt for(i=1;i<=max;i++) printf("\%d",wsol[i]+1);\vskip -10pt \hskip 20pt printf(" \%d\{\}n",wmax+1); lprint = max;\vskip -10pt \hskip 15pt \}\vskip -10pt \hskip 5pt fflush(stdout);\vskip -10pt \} int add\_col(int col)\{\vskip -10pt \hskip 5pt int i, j=1, sum, ex=0;\vskip -10pt \hskip 5pt wsol[++wmax] = col;\vskip -10pt \hskip 5pt if (wmax >= max) updatesol(); \hskip 5pt for(i=1;i< MIN(wmax,L-wmax) ;i++)\{ \vskip -10pt \hskip 10pt sum = wmax + i ;\vskip -10pt \hskip 10pt if ((wsol[i]==col))\{\vskip -10pt \hskip 15pt nums[wmax][j++] = sum;\vskip -10pt \hskip 15pt Base[col][sum]++;\vskip -10pt \hskip 15pt if((sum < MAX(LL,max)) \&\& excludedp(sum)) \vskip -10pt \hskip 20pt ex++;\vskip -10pt \hskip 10pt \}\vskip -10pt \hskip 5pt \}\vskip -10pt \hskip 5pt return(ex);\vskip -10pt \} void del\_col(void)\{\vskip -10pt \hskip 5pt int i=1, col; \hskip 5pt col = wsol[wmax];\vskip -10pt \hskip 5pt while (nums[wmax][i])\{\vskip -10pt \hskip 10pt Base[col][nums[wmax][i]]$--$;\vskip -10pt \hskip 10pt nums[wmax][i++] = 0;\vskip -10pt \hskip 5pt \}\vskip -10pt \hskip 5pt wmax$--$;\vskip -10pt \} void brute\_force(int b)\{\vskip -10pt \hskip 5pt int i; \hskip 5pt for(i=0;i<= MIN(COLS-1,b+1);i++)\vskip -10pt \hskip 10pt if(colp(i))\{\vskip -10pt \hskip 15pt if(!add\_col(i))\vskip -10pt \hskip 20pt brute\_force(MAX(i,b));\vskip -10pt \hskip 15pt del\_col();\vskip -10pt \hskip 10pt \}\vskip -10pt \} int main(int argc, char **argv)\{\vskip -10pt \hskip 5pt int i, j;\vskip -10pt \hskip 5pt char *p; \hskip 5pt for(i=0;i