On a Generalization of the Coin Exchange Problem for Three Variables

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

               atripath@maths.iitd.ac.in

Sujith Vijay Department of Mathematics Rutgers University – New Brunswick Piscataway, NJ 08854 USA

                sujith@math.rutgers.edu

Abstract

Given relatively prime and positive integers a_{1}, a_{2}, …, a_{k}, let Γ denote the set of nonnegative integers representable by the form a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{k}x_{k}, and let Γ^{⋆} denote the positive integers in Γ. Let S^{⋆}(a_{1}, a_{2}, …, a_{k}) denote the set of all positive integers n not in Γ for which n + Γ^{⋆} is contained in Γ^{⋆}. The purpose of this article is to determine an algorithm which can be used to obtain the set S^{⋆} in the three variable case. In particular, we show that the set S^{⋆}(a_{1}, a_{2}, a_{3}) has at most two elements. We also obtain a formula for g(a_{1}, a_{2}, a_{3}), the largest integer not representable by the form a_{1}x_{1} + a_{2}x_{2} + a_{3}x_{3} with the x_{i}’s nonnegative integers.