% Lines beginning with a percent sign are comments.

\documentclass[12pt]{article}

% set paragraph formatting 

\parindent=0pt
\parskip=10pt

% define some environments

\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}

\newenvironment{proof}{{\bf Proof\ }}{\hfill\rule{5pt}{5pt}}
\newenvironment{definition}{{\bf Definition\ }}{}

% specify the author, title, and date (optional)

\author{Gregory Quenell}
\title{A Putnam problem on integer sums}
\date{January 22, 2004}

% end of the preamble

\begin{document}

\maketitle

\section{Introduction}
\label{introductionsection}

Problem A-1 of the 2003 William Lowell Putnam Mathematical Competition
(\cite{putnam03}) reads as follows

\begin{quotation}
\noindent
Let $n$ be a fixed positive integer. How many ways are there to write
$n$ as a sum of positive integers, $n = a_1 + a_2 + \cdots + a_k$,
with $k$ an arbitrary positive integer and 
$a_1 \leq a_2 \leq \cdots \leq a_k \leq a_1 + 1$?  
For example, with $n=4$ there are four ways: 
$4$, $2+2$, $1+1+2$, $1+1+1+1$.
\end{quotation}

In this brief note, we will experiment with sums of the form given in
Problem~A-1, guess how many such sums 
there are for each positive integer $n$, and eventually
prove that our guess is correct.

\section{Notation}

For a positive integer $n$, let $S(n)$ denote the number of ways that
$n$ can be written as a sum $n = a_1 + a_2 + \cdots + a_k$ with 
\begin{eqnarray}
a_1 \leq a_2 \leq \cdots \leq a_k \leq a_1 + 1
\label{sumcondition}
\end{eqnarray}
where the $a_i$ are all positive integers.  Note that condition
(\ref{sumcondition}) implies that every $a_i$ is either equal to $a_1$
or to $a_1 + 1$, so $S(n)$ is just the number of ways that $n$ can be
written as a sum
\begin{eqnarray}
n = (a_1 + a_1 + \cdots + a_1) + ((a_1 + 1) + (a_1 + 1) + \cdots +
(a_1 + 1))
\label{sumform}
\end{eqnarray}
where $a_1$ is some positive integer.  We make the following
definition.

\begin{definition}
A sum will be called {\sl neighboring} if it has the form of the sum
in (\ref{sumform}).
\end{definition}

\section{Experimental data}
\label{datasection}

For small values of $n$, we can determine $S(n)$ simply by listing all
the ways we can write $n$ as a sum of the form (\ref{sumform}).

\begin{itemize}
\item
For $n=1$, we can write only the trivial sum $1 = 1$.

\item
For $n=2$, there are two neighboring sums: $2 = 2$ and $2 = 1 + 1$.

\item
For $n=3$, we have
\begin{eqnarray*}
3 & = & 3 \\
  & = & 2 + 1 \\
  & = & 1 + 1 + 1
\end{eqnarray*}
for a total of three neighboring sums.

\item
For $n=4$, the four neighboring sums are
given in the statement of the problem in section
\ref{introductionsection}

\item
For $n=5$, we have
\begin{eqnarray*}
5 & = & 5 \\
  & = & 3 + 2 \\
  & = & 2 + 2 + 1 \\
  & = & 2 + 1 + 1 + 1 \\
  & = & 1 + 1 + 1 + 1 + 1
\end{eqnarray*}
for a total of five neighboring sums.
(No neighboring sum for $5$ could include a $4$, because it would then
have to include either a $3$ or another $4$).
\end{itemize}

We summarize these data in the table below.

\begin{center}
\begin{tabular}{|r||c|c|c|c|c|}
\hline
$n$ & $1$ & $2$ & $3$ & $4$ & $5$ \\
\hline
$S(n)$ & $1$ & $2$ & $3$ & $4$ & $5$  \\
\hline
\end{tabular}
\end{center}

\section{Two conjectures}

The obvious conjecture from the data we collected in
section \ref{datasection} is

\begin{conjecture}
For each positive integer $n$, the number of ways to write $n$ as a
neighboring sum is $n$.
\label{snconjecture}
\end{conjecture}

Looking more closely at the data, we notice another pattern.
For each 
$n \in \{ 1, 2, 3, 4, 5 \}$, each of the neighboring sums 
we wrote down has a different number of terms. 
Since the number of terms in a sum for $n$
cannot exceed $n$, this leads to another conjecture.

\begin{conjecture}
Given a positive integer $n$, for each positive integer $k \leq n$,
there is exactly one way to write $n$ as neighboring sum with $k$
terms. 
\label{termconjecture}
\end{conjecture}

Why should this be so?  Consider $n=5$, say, and suppose we want to
write $5$ as a neighboring sum with three terms.  Then each of the
three terms has to be approximately $5/3$.  Since $5/3$ is between $1$
and $2$, we guess that 
each of the three terms in the neighboring sum will be either
$1$ or $2$.  We get $5 = 2 + 2 + 1$.  If we want to write $5$ and a
two-term neighboring sum, we know each of the terms will be either $2$
or $3$, since $5/2$ lies between $2$ and $3$.  Clearly $5 = 2 + 3$ is
the sum we want.

To turn this idea into a proof of Conjecture~\ref{termconjecture}, we
will need a standard theorem about integer division.

\section{The Division Algorithm}

% Note that the left-hand double quotes are backquotes, and
% the right-hand double quotes are apostrophes.

Despite the word ``algorithm'' in its name, the Division Algorithm is
actually a theorem.  It says (see \cite[page 5]{NZM91}, for example)

\begin{theorem}[The Division Algorithm]
Given a positive integer $a$ and an integer $b$, there exist 
unique integers
$q$ and $r$ with $0 \leq r < a$ such that $b = qa + r$.
\label{divisionalgorithm}
\end{theorem}

Using Theorem~\ref{divisionalgorithm}, we can prove
Conjecture~\ref{termconjecture}, which we state a little more
precisely as

\begin{theorem}
Given a positive integer $n$ and a positive integer $k \leq n$, there
is a unique neighboring sum for $n$ with $k$ terms.
\label{termtheorem}
\end{theorem}

\begin{proof}
Given $n$ and $k$ as in the statement of the theorem, 
use the Division Algorithm to
write $n = kq + r$ with $0 \leq r < k$.  Since $n \geq k$ and 
$r < k$, it follows that $kq = n-r$ is positive,
and so $q \geq 1$.  

We rewrite the equation 
$n = kq + r$ as
\begin{eqnarray}
n & = & \underbrace{q + q + \cdots + q}_{k {\rm\ terms}} +
        \underbrace{1 + 1 + \cdots + 1}_{r {\rm\ terms}} \\
  & = & \underbrace{q + q + \cdots + q}_{k-r {\rm\ terms}} +
        \underbrace{(q+1) + (q+1) + \cdots + (q+1)}_{r {\rm\ terms}}
\label{qneighboringsum}
\end{eqnarray}
Since $q$ is a positive integer, line 
(\ref{qneighboringsum}) expresses $n$ as a neighboring sum with $k$
terms. 

To see that this expression is unique, suppose $n$ and $k$ are as in
the statement of the theorem, and that
\begin{eqnarray}
n & = & \underbrace{q + q + \cdots + q}_{k-r {\rm\ terms}} +
      \underbrace{(q+1) + (q+1) + \cdots + (q+1)}_{r {\rm\ terms}} 
\label{unprimed} \\
\nonumber  & \mbox{and} & \\
n & = & \underbrace{q' + q' + \cdots + q'}_{k-r' {\rm\ terms}} +
      \underbrace{(q'+1) + (q'+1) + \cdots + (q'+1)}_{r' {\rm\ terms}}
\label{primed}
\end{eqnarray}
are two neighboring sums for $n$.
Then from (\ref{unprimed}), we have
\begin{eqnarray}
n = (k-r)q + r(q+1) = kq + r
\label{divalgunprimed}
\end{eqnarray}
and from (\ref{primed}), we have
\begin{eqnarray}
n = (k-r')q' + r'(q'+1) = kq' + r'
\label{divalgprimed}
\end{eqnarray}
Lines (\ref{divalgunprimed}) and (\ref{divalgprimed}) imply that
$n = kq + r = kq' + r'$ where $0 \leq r < k$ and $0 \leq r' < k$.  But
the numbers $q$ and $r$ in the Division Algorithm are uniquely
determined, so we must have $q = q'$ and $r = r'$. 
Thus expressions (\ref{unprimed}) and (\ref{primed}) 
are identical.
\end{proof}


\section{Conclusion}

From Theorem~\ref{termtheorem} we get the following corollary, which
is the same as Conjecture~\ref{snconjecture}.

\begin{corollary}
For each positive integer $n$, there are exactly $n$ ways to write $n$
as a neighboring sum.
\end{corollary}

\begin{proof}
By Theorem~\ref{termtheorem}, for each $k \in \{ 1, 2, \dots, n \}$,
there is exactly one way to write $n$ as a neighboring sum with $k$
terms.  Since there are $n$ elements in the set $\{ 1, 2, \dots, n
\}$, there are a total of $n$ ways to write $n$ as a neighboring sum.
\end{proof}

We remark that neighboring sums are closely related to maximally even
sets (see \cite{clough86} for a definition), and that
Theorem~\ref{termtheorem} can be used to construct an algorithm
(\cite{quenell04}) that
generates maximally even sets.

\begin{thebibliography}{9}

\bibitem{clough86}
Clough, John and Gerald Myerson, ``Musical scales and the generalized
circle of fifths,'' {\it American Mathematical Monthly} 93(9), 1986,
pp. 695-701.

\bibitem{NZM91}
Niven, Ivan, Herbert Zuckerman, and Hugh Montgomery, {\it An
Introduction to the Theory of Numbers}, fifth edition, John Wiley \&
Sons, Inc., 1991.

\bibitem{putnam03}
The Sixty-Fourth William Lowell Putnam Mathematical Competition,
administered by the Mathematical Association of America, Washington DC.

\bibitem{quenell04}
Quenell, Gregory, ``Recursive smooth sums and maximally even sets,''
in preparation.

\end{thebibliography}

\end{document}