ON A VARIATION OF THE COIN EXCHANGE PROBLEM FOR ARITHMETIC PROGRESSIONS

Amitabha Tripathi

Department of Mathematics, Indian Institute of Technology, Hauz Khas, New Delhi - 110016, India

                        atripath@maths.iitd.ac.in

Received: 3/21/02, Revised: 10/24/02, Accepted: 1/1/03, Published: 1/2/03

Abstract

Let a_{1}, a_{2}, …, a_{k} be relatively prime, positive integers arranged in increasing order. Let Γ^{⋆} denote the positive integers in the set { a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{k}x_{k} : x_{j} ≥ 0 }. Let

S^{⋆}(a_{1}, a_{2}, …, a_{k}) ≐ { n ∉ Γ^{⋆} : n + Γ^{⋆} ⊆ Γ^{⋆} }.

We determine S^{⋆}(a_{1}, a_{2}, …, a_{k}) in the case where the a_{j}’s are in arithmetic progression. In particular, this determines g(a_{1}, a_{2}, …, a_{k}) in this particular case.

1. Introduction

Let a_{1}, a_{2}, …, a_{k} be relatively prime, positive integers arranged in increasing order. Let Γ denote { a_{1}x_{1}+a_{2}x_{2}+⋯+a_{k}x_{k} : x_{j} ≥ 0 }, and let Γ^{⋆} ≐ Γ\{0}. It is well known and easy to show that Γ^{c} ≐ IN \ Γ is a finite set. We use the classical notation g(a_{1}, a_{2}, …, a_{k}) to denote the largest number in Γ^{c}. J.J. Sylvester [15] showed that g(a_{1}, a_{2}) = a_{1}a_{2}−a_{1}−a_{2}. In later years, the number of elements in Γ^{c}, denoted by n(a_{1}, a_{2}, …, 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}, …, a_{k}) that denotes the sum of elements in Γ^{c}. Introduced in [4], it was shown that s(a_{1}, a_{2}) = (a_{1} − 1)(a_{2} − 1)(2a_{1}a_{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 arithmetic progression ([1],[5],[9],[16]), but other results obtained are mostly partial results ([2],[3],[6],[7],[10],[11], [12],[13],[14]) 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 Coin Exchange Problem.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A01 2

2. Main Result

We study a variation of the Coin Exchange Problem in this note. We denote by S^{⋆}(a_{1}, a_{2}, …, a_{k}) the set of all n ∈ Γ^{c} such that

n + Γ^{⋆} ⊆ Γ^{⋆},

and let g^{⋆}(a_{1}, a_{2}, …, a_{k}) (respectively, n^{⋆}(a_{1}, a_{2}, …, a_{k}) and s^{⋆}(a_{1}, a_{2}, …, a_{k})) denote the least (respectively, the number and sum of) elements in S^{⋆}. Since g(a_{1}, a_{2}, …, a_{k}) is the largest element in S^{⋆},

g^{⋆}(a_{1}, a_{2}, …, a_{k}) ≤ g(a_{1}, a_{2}, …, a_{k}),

and n^{⋆}(a_{1}, a_{2}, …, a_{k}) ≥ 1, with equality if and only if g^{⋆} = g. This problem arises from looking at the generators for the Derivation modules of certain curves [8], and has been extensively studied.

For each j, 1 ≤ j ≤ a_{1} − 1, let m_{j} denote the least number in Γ congruent to j (mod a_{1}). Then m_{j} − a_{1} is the largest number in Γ^{c} congruent to j (mod a_{1}), and no number less than this in this residue class can be in S^{⋆}, for they would differ by a multiple of a_{1}, an element in Γ^{⋆}. Therefore,

S^{⋆}(a_{1}, a_{2}, …, a_{k}) ⊆ { m_{j} − a_{1} : 1 ≤ j ≤ a_{1} − 1 },  (1)
g^{⋆}(a_{1}, a_{2}, …, a_{k}) ≤ ( max_{1≤j≤a_{1}−1} m_{j}) − a_{1} = g(a_{1}, a_{2}, …, a_{k}),  (2)
n^{⋆}(a_{1}, a_{2}, …, a_{k}) ≤ a_{1} − 1,  (3)

and

s^{⋆}(a_{1}, a_{2}, …, a_{k}) ≤ ∑_{j=1}^{a_{1}−1} m_{j} − a_{1}(a_{1} − 1).  (4)

More precisely,

m_{j} − a_{1} ∈ S^{⋆}(a_{1}, a_{2}, …, a_{k}) ⟺ (m_{j} − a_{1}) + m_{i} ≥ m_{j+i} for 1 ≤ i ≤ a_{1} − 1. (5)

We shall explicitly evaluate the set S^{⋆}, and as a consequence, the functions g, g^{⋆}, n^{⋆} and s^{⋆}, when the a_{j}’s are in arithmetic progression. We write a_{j} = a + (j − 1)d for 1 ≤ j ≤ k, and assume gcd(a, d) = 1. In this case, we denote the functions g, g^{⋆}, n^{⋆} and s^{⋆} by g(a, d; k), g^{⋆}(a, d; k), n^{⋆}(a, d; k) and s^{⋆}(a, d; k), respectively. To determine S^{⋆}(a, d; k), we recall Lemma 2 from [16].

Lemma: For each t, 1 ≤ t ≤ a − 1, the least integer in Γ^{⋆} congruent to dt (mod a) is given by a(1 + [\frac{t−1}{k−1}]) + dt.

Theorem: Let a, d be relatively prime, positive integers, and let k ≥ 2. If a − 1 = q(k − 1) + r, with 1 ≤ r ≤ k − 1, then

S^{⋆}(a, d; k) = \{ a [\frac{x − 1}{k − 1}] + dx : a − r ≤ x ≤ a − 1 \} .

Proof: Fix k ≥ 2. Throughout this proof, and elsewhere, by x mod m we mean x − x[\frac{x}{m}]. By (1) and Lemma,

S^{⋆}(a, d; k) ⊆ \{ a [\frac{x − 1}{k − 1}] + dx : 1 ≤ x ≤ a − 1 \} .

From (5), n = a[\frac{x−1}{k−1}] + dx ∈ S^{⋆} if and only if for each y with 1 ≤ y ≤ a − 1,

a (1 + [\frac{((x + y) mod a) − 1}{k − 1}]) + d((x + y) mod a) ≤ \{a [\frac{x − 1}{k − 1}] + dx\} + \{a (1 + [\frac{y − 1}{k − 1}]) + dy\} ,

or,

a [\frac{((x + y) mod a) − 1}{k − 1}] + d((x + y) mod a) ≤ a \{[\frac{x − 1}{k − 1}] + [\frac{y − 1}{k − 1}]\} + d(x + y). (6)

Suppose 2 ≤ k ≤ a−1. Let a−1 = q(k −1)+r, with 1 ≤ r ≤ k −1. Unless x = a−1, x + y ≤ a − 1 for at least one y, for such a y, (6) reduces to proving the inequality

[\frac{x + y − 1}{k − 1}] ≤ [\frac{x − 1}{k − 1}] + [\frac{y − 1}{k − 1}] .

If we now write x = q_{1}(k − 1) + r_{1}, y = q_{2}(k − 1) + r_{2}, with 1 ≤ r_{1}, r_{2} ≤ k − 1, the reduced inequality above fails to hold precisely when r_{1} + r_{2} ≥ 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 ≤ a − 1. However, such a choice for y is not possible precisely when x ≥ 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^{⋆} = \{ a[\frac{x−1}{k−1}] + dx : a − r ≤ x ≤ a − 1 \} if 2 ≤ k ≤ a − 1.

If k ≥ a, (6) reduces to d((x+y) mod a) ≤ d(x+y). Thus, S^{⋆} = { dx : 1 ≤ x ≤ a−1 }, as claimed, since r = a − 1 and [\frac{x−1}{k−1}] = 0 in this case. This completes the proof. □

Corollary: If a, d be relatively prime, positive integers, k ≥ 2, and a − 1 = q(k − 1) + r, with 1 ≤ r ≤ k − 1, then

g(a, d; k) = aq + d(a − 1),

g^{⋆}(a, d; k) = aq + d(a − r),
n^{⋆}(a, d; k) = r,

and

s^{⋆}(a, d; k) = aqr + \frac{1}{2}dr(2a − r − 1).

Acknowledgements

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.

References

[1] Bateman, P.T., Remark on a Recent Note on Linear Forms, American Mathematical Monthly 65 (1958), 517-518.

[2] Brauer, A., On a Problem of Partitions, American Journal of Mathematics 64 (1942), 299-312.

[3] Brauer, A. and Shockley, J.E., On a problem of Frobenius, Crelle 211 (1962), 215-220.

[4] Brown, T.C. and Shiue, P.J., A remark related to the Frobenius problem, Fibonacci Quarterly, 31 (1993), 31-36.

[5] Grant, D.D., On linear forms whose coefficients are in Arithmetic progression, Israel Journal of Mathematics 15 (1973), 204-209.

[6] Hofmeister, G.R., Zu einem Problem von Frobenius, Norske Videnskabers Selskabs Skrifter 5 (1966), 1-37.

[7] Nijenhuis, A. and Wilf, H.S., Representations of integers by linear forms in non negative integers, Journal of Number Theory 4 (1972), 98-106.

[8] Patil, D.P. and Singh, Balwant, Generators for the derivation modules and the relation ideals of certain curves, Manuscripta Mathematica 68 (1990), 327-335.

[9] Roberts, J.B., Note on Linear Forms, Proceedings of the American Mathematical Society 7 (1956), 465-469.

[10] Roberts, J.B., On a Diophantine problem, Canadian Journal of Mathematics 9 (1957), 219-222.

[11] Rödseth, Ö.J., On a linear Diophantine problem of Frobenius, Crelle 301 (1978), 171-178.

[12] Rödseth, Ö.J., On a linear Diophantine problem of Frobenius II, Crelle 307/308 (1979), 431-440.

[13] Selmer, E.S., On the linear Diophantine problem of Frobenius, Crelle 293/294 (1977), 1-17.

[14] Selmer, E.S. and Beyer, Ö., On the linear Diophantine problem of Frobenius in three variables, Crelle 301 (1978), 161-170.

[15] Sylvester, J.J., Mathematical questions with their solutions, The Educational Times 41 (1884), 21.

[16] Tripathi, A., The Coin Exchange Problem for Arithmetic Progressions, American Mathematical Monthly 101 (1994), no. 10, 779-781.