\documentstyle[12pt]{article}
\textwidth=6.25in
\textheight=9.0in
\topmargin=-10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9

\def\a{\alpha}
\def\le{\leq}
\def\pr{\prime}
\def\R{I\!\!R}
\def\Z{Z\!\!\!Z}
\def\N{I\!\!N}
\def\S{\cal S}
\def\G{\Gamma}
%\def\lf{\lfloor}
%\def\rf{\rfloor}
%\def\lc{\lceil}
%\def\rc{\rceil} 
\def\ds{\displaystyle}
\def\sm{\setminus}
\def\mod{\!\!\!\!\pmod}
\def\Liff{\Longleftrightarrow}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newenvironment{proof}{\noindent{\sc Proof: }}{\hfill $\Box$ \\}

\begin{document}
\begin{center}
{\bf ON A VARIATION OF THE COIN EXCHANGE
 PROBLEM FOR ARITHMETIC PROGRESSIONS} 
\vskip 20pt

{\bf Amitabha Tripathi} \\
{\smallit Department of Mathematics, Indian Institute of Technology, Hauz Khas, New Delhi - 110016, India} \\
{\tt atripath@maths.iitd.ac.in} \\
\end{center} 
\vskip 30pt

\centerline{\smallit Received: 3/21/02, Revised: 10/24/02, Accepted:
1/1/03, Published: 1/2/03}
\vskip 30pt

\centerline{\bf Abstract} 
\noindent Let $a_1,a_2,\ldots,a_k$ be relatively prime, positive integers arranged in increasing order. Let ${\G}^{\star}$ denote the positive integers in the set $\{\,a_1x_1+a_2x_2+\cdots+a_kx_k: x_j \ge 0\,\}$. Let 
\[ {\S}^{\star}(a_1,a_2,\ldots,a_k) \doteq \{\,n \notin {\G}^{\star}: n+{\G}^{\star} \subseteq {\G}^{\star}\,\}. \] 
We determine ${\S}^{\star}(a_1,a_2,\ldots,a_k)$ in the case where the $a_j$'s are in {\em arithmetic progression\/}. In particular, this determines $g(a_1,a_2,\ldots,a_k)$ in this particular case. 

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 
\smalltt 3 (2003), \#A01\hfill}
\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt 

\section*{\normalsize 1. Introduction}

Let $a_1,a_2,\ldots,a_k$ be relatively prime, positive integers arranged in increasing order. Let ${\G}$ denote $\{\,a_1x_1+ a_2x_2+ \cdots+a_kx_k: x_j \ge 0\,\}$, and let ${\G}^{\star} \doteq {\G} \sm \{0\}$. It is well known and easy to show that ${\G}^c \doteq {\N} \sm {\G}$ is a {\em finite\/} set. We use the classical notation $g(a_1,a_2,\ldots,a_k)$ to denote the {\em largest\/} number in ${\G}^c$.
 {\em J.J.\,Sylvester\/} \cite{Syl84} showed that $g(a_1,a_2)=a_1a_2-a_1-a_2$. In
later years, the number of elements in ${\G}^c$, denoted by
$n(a_1,a_2,\ldots,a_k)$, was also studied, and it was shown that
$n(a_1,a_2)=(a_1-1)(a_2-1)/2$. Another function related to this is the function
$s(a_1,a_2,\ldots,a_k)$ that denotes the sum of elements in ${\G}^c$. Introduced
in \cite{BS93a}, it was shown that
$s(a_1,a_2)=(a_1-1)(a_2-1)(2a_1a_2-a_1-a_2-1)/12$. \\

There is a neat formula for each of the functions $g$ and $n$ when the $a_j$'s are in
 {\em arithmetic progression\/}
(\cite{Bat58},\cite{Gra73},\cite{Rob56},\cite{Tri94}), but other results
obtained are mostly partial results
(\cite{Bra42},\cite{BS62},\cite{Hof66},\cite{NW72},\cite{Rob57},\cite{Rod78},
\cite{Rod79},\cite{Sel77},\cite{SB78})
and often not  as neat. Due to an obvious connection with making change
given money of different denominations, this problem is also known as the
{\em Coin Exchange Problem\/}. \\
\vskip 30pt 

\section*{\normalsize 2. Main Result}

\noindent We study a variation of the Coin Exchange Problem in this note. We denote
by\\ ${\S}^{\star}(a_1,a_2,\ldots,a_k)$ the set of all $n \in {\G}^c$ such that 
\[ n+{\G}^{\star} \subseteq {\G}^{\star}, \] 
and let $g^{\star}(a_1,a_2,\ldots,a_k)$ (respectively, $n^{\star}(a_1,a_2,\ldots,a_k)$ and $s^{\star}(a_1,a_2,\ldots,a_k)$) denote the {\em least\/} (respectively, the {\em number\/} and {\em sum\/} of) elements in ${\S}^{\star}$. Since $g(a_1,a_2,\ldots,a_k)$ 
is the {\em largest\/} element in $S^{\star}$, 
\[ g^{\star}(a_1,a_2,\ldots,a_k) \le g(a_1,a_2,\ldots,a_k), \]
and $n^{\star}(a_1,a_2,\ldots,a_k) \ge 1$, with equality if and only if $g^{\star}=g$. This problem arises from looking at the generators for the Derivation modules of certain
 curves \cite{PS90}, and has been extensively studied. \\

For each $j$, $1 \le j \le a_1-1$, let $m_j$ denote the {\em least\/} number in ${\G}$ congruent to $j\mod{a_1}$. Then $m_j-a_1$ is the largest number in ${\G}^c$ congruent to $j\mod{a_1}$, and no number less than this in this residue class can be in ${\S}^{\star}$, for they would differ by a multiple of $a_1$, an element in ${\G}^{\star}$. Therefore, 
\begin{equation}
{\S}^{\star}(a_1,a_2,\ldots,a_k) \subseteq \{\,m_j-a_1: 1 \le j \le a_1-1\,\}, 
\end{equation}
\begin{equation}
g^{\star}(a_1,a_2,\ldots,a_k) \le \left( \max_{1 \le j \le a_1-1}\: m_j \right) - a_1 = g(a_1,a_2,\ldots,a_k), 
\end{equation}
\begin{equation}
n^{\star}(a_1,a_2,\ldots,a_k) \le a_1-1,
\end{equation}
and 
\begin{equation}
s^{\star}(a_1,a_2,\ldots,a_k) \le \sum_{j=1}^{a_1-1}\:m_j - a_1(a_1-1).
\end{equation}
More precisely, 
\begin{equation}
m_j-a_1 \in {\S}^{\star}(a_1,a_2,\ldots,a_k) \Liff (m_j-a_1)+m_i \ge m_{j+i} \;\;
{\rm for}\;\;1 \le i \le a_1-1. 
\end{equation}
\vspace*{0.1in}

We shall explicitly evaluate the set ${\S}^{\star}$, and as a consequence, the functions $g$, $g^{\star}$, $n^{\star}$ and $s^{\star}$, when the $a_j$'s are in {\em arithmetic progression\/}. We write $a_j=a+(j-1)d$ for $1 \le j \le k$, and assume $\gcd(a,d)=1$. In this case, we denote the functions $g$, $g^{\star}$, $n^{\star}$ and $s^{\star}$ by $g(a,d;k)$, $g^{\star}(a,d;k)$, $n^{\star}(a,d;k)$ and $s^{\star}(a,d;k)$, respectively. To determine ${\S}^{\star}(a,d;k)$,
 we recall Lemma 2 from \cite{Tri94}. \\
\\
{\bf Lemma:} 
For each $t$, $1 \le t \le a-1$, the least integer in ${\Gamma}^{\star}$ congruent to $dt \mod{a}$ is given by $a(1+[\frac{t-1}{k-1}])+dt$. \\
\\
{\bf Theorem:} 
Let $a,d$ be relatively prime, positive integers, and let $k \ge 2$. If $\,a-1=q(k-1)+r$, with $1 \le r \le k-1$, then  
\[ {\S}^{\star}(a,d;k) = \left\{ \,a\left[ \frac{x-1}{k-1} \right]+dx: a-r \le x \le a-1\,\right\}. \]
\vspace*{0.1in}

\begin{proof}
Fix $k \ge 2$. Throughout this proof, and elsewhere, by $x \bmod{m}$ we mean $x-x[\frac{x}{m}]$. By $(1)$ and Lemma, 
\[ {\S}^{\star}(a,d;k) \subseteq \left\{\,a\left[ \frac{x-1}{k-1} \right]+dx: 1 \le x \le a-1\,\right\}. \]
From $(5)$, $n=a[\frac{x-1}{k-1}]+dx \in {\S}^{\star}$ if and only if for each $y$ with $1 \le y \le a-1$, 
\footnotesize
\[ a\left( 1+\left[\frac{((x+y) \bmod{a})-1}{k-1}\right] \right)+d((x+y)\bmod{a})
\le \left\{ a\left[\frac{x-1}{k-1}\right]+dx \right\} +  
    \left\{ a\left( 1+\left[ \frac{y-1}{k-1}\right] \right)+dy \right\}, \]
\normalsize
or, 
\begin{equation}
a\left[\frac{((x+y)\bmod{a})-1}{k-1}\right] + d((x+y)\bmod{a}) \le a\left\{ \left[\frac{x-1}{k-1}\right] + \left[\frac{y-1}{k-1}\right] \right\}+d(x+y). 
\end{equation}
\vspace*{0.1in}

Suppose $2 \le k \le a-1$. Let $a-1=q(k-1)+r$, with $1 \le r \le k-1$. Unless $x=a-1$, $x+y \le a-1$ for at least one $y$, for such a $y$, $(6)$ reduces to proving the inequality 
\[ \left[ \frac{x+y-1}{k-1} \right] \le \left[ \frac{x-1}{k-1} \right] + \left[ \frac{y-1}{k-1} \right]. \] 
If we now write $x=q_1(k-1)+r_1$, $y=q_2(k-1)+r_2$, with $1 \le r_1,r_2 \le k-1$, the reduced inequality above fails to hold precisely when $r_1+r_2 \ge k$. Given $x$, and hence $r_1$, the choice $y=r_2=k-r_1$ will thus ensure that $(6)$ fails to hold provided $x+y \le a-1$. However, such a choice for $y$ is not possible precisely when $x \ge q(k-1)+1=a-r$, so that $(6)$ always holds in only these cases. Finally, it is easy to verify that $(6)$ holds if $x=a-1$. This shows ${\S}^{\star}=\{\,a[\frac{x-1}{k-1}]+dx: a-r \le x \le a-1\,\}$ if $2 \le k \le a-1$. 

If $k \ge a$, $(6)$ reduces to $d((x+y)\bmod{a}) \le d(x+y)$. Thus, ${\S}^{\star}=\{\,dx: 1 \le x \le a-1\,\}$, as claimed, since $r=a-1$ and $[\frac{x-1}{k-1}]=0$ in this case. This completes the proof. 
\end{proof}
\vspace*{0.2in}

\noindent{\bf Corollary:}
If $a,d$ be relatively prime, positive integers, $k \ge 2$, and $a-1=q(k-1)+r$, with $1 \le r \le k-1$, then 
\[ g(a,d;k) = aq+d(a-1), \]
\[ g^{\star}(a,d;k) = aq+d(a-r), \]
\[ n^{\star}(a,d;k) = r, \]
and 
\[ s^{\star}(a,d;k) = aqr+\frac{1}{2}dr(2a-r-1). \] 
\vskip 30pt

\noindent{\Large \bf Acknowledgements}
\vspace*{0.1in}

\noindent The author wishes to thank Professor R.\,Balasubramanian for introducing him to the problem, and Dr.\,C.S.\,Yogananda for arranging a copy of the eighth reference. \\
\vskip 30pt

%\nocite{Tri89}
%\nocite{Syl84}
%\nocite{Rob56}

%\bibliographystyle{plain}
%\bibliography{at}

\begin{thebibliography}{99}

\bibitem{Bat58}
Bateman, P.T.,
Remark on a {R}ecent {N}ote on {L}inear {F}orms,
{\it American Mathematical Monthly} {\bf 65} (1958),
517-518.

\bibitem{Bra42}
Brauer, A.,
On a {P}roblem of {P}artitions,
{\it American Journal of Mathematics} {\bf 64} (1942), 299-312.

\bibitem{BS62}
Brauer, A. and Shockley, J.E.,
On a problem of {F}robenius,
{\it Crelle} {\bf 211} (1962), 215-220.

\bibitem{BS93a} Brown, T.C. and Shiue, P.J.,
 A remark related to the {F}robenius problem,
{\it Fibonacci Quarterly}, {\bf 31} (1993), 31-36.



\bibitem{Gra73}
Grant, D.D.,
On linear forms whose coefficients are in {A}rithmetic progression,
{\it Israel Journal of Mathematics} {\bf 15} (1973), 204-209.

\bibitem{Hof66}
Hofmeister, G.R.,
Zu einem {P}roblem von {F}robenius,
{\it Norske Videnskabers Selskabs Skrifter} {\bf 5} (1966), 1-37.

\bibitem{NW72}
Nijenhuis, A. and Wilf, H.S.,
Representations of integers by linear forms in non negative integers,
{\it Journal of Number Theory} {\bf 4} (1972), 98-106.


 

\bibitem{PS90} Patil, D.P. and Singh, Balwant,
Generators for the derivation modules and the relation ideals of certain
curves, {\it Manuscripta Mathematica} {\bf 68} (1990), 327-335.

\bibitem{Rob56}
Roberts, J.B.,
Note on {L}inear {F}orms,
{\it Proceedings of the American Mathematical Society} {\bf 7} (1956), 465-469.


\bibitem{Rob57}
Roberts, J.B.,
On a {D}iophantine problem,
{\it Canadian Journal of Mathematics} {\bf 9} (1957), 219-222.

\bibitem{Rod78}
R{\"{o}}dseth, {\"{O}}.J.,
On a linear {D}iophantine problem of {F}robenius,
{\it Crelle} {\bf 301} (1978), 171-178.


\bibitem{Rod79}
R{\"{o}}dseth, {\"{O}}.J.,
On a linear {D}iophantine problem of {F}robenius {II},
{\it Crelle} {\bf 307/308} (1979), 431-440.

\bibitem{Sel77}
Selmer, E.S.,
On the linear {D}iophantine problem of {F}robenius,
{\it Crelle} {\bf 293/294} (1977), 1-17.

\bibitem{SB78}
Selmer, E.S. and Beyer, {\"{O}}.,
On the linear {D}iophantine problem of {F}robenius in three variables,
{\it Crelle} {\bf 301} (1978), 161-170.

\bibitem{Syl84}
Sylvester, J.J.,
Mathematical questions with their solutions,
{\it The Educational Times} {\bf 41} (1884), 21.



\bibitem{Tri94} Tripathi, A.,
The {C}oin {E}xchange {P}roblem for {A}rithmetic {P}rogressions,
{\it American Mathematical Monthly } {\bf 101} (1994), no. 10, 779-781.

%\begin{thebibliography}{12345}

\end{thebibliography}
\end{document}