Integer Constraints via Diophantine Equations

In this post, we study a simple yet instructive example of a linear Diophantine equation arising from a coin-counting problem.

Despite its elementary appearance, this problem showcases how number theory naturally encodes discrete constraints, a theme that appears repeatedly in optimization, algorithms, and quantitative finance.

This idea mirrors feasibility checks in optimization, algorithms, and quantitative modeling.

Problem

A man has $4.55 in change composed entirely of 10-cent coins and 25-cent coins.

  1. What is the maximum number of coins he can have?
  2. What is the minimum number of coins he can have?
  3. Is it possible for the number of 10-cent coins to equal the number of 25-cent coins?

Solution

Let

  • $x$ = number of 10-cent coins
  • $y$ = number of 25-cent coins

The total value in cents gives the equation

\[10x + 25y = 455.\]

Existence of Solutions

A linear Diophantine equation $ax + by = c$ has integer solutions if and only if $\gcd(a,b) \mid c.$

Euclidean Algorithm

Applying the Euclidean algorithm,

\[\begin{aligned} 25 &= 10(2) + 5, \\ 10 &= 5(2). \end{aligned}\]

Hence, $\gcd(10,25) = 5.$

General Integer Solution

From the first equation,

\[5 = 25 - 10(2).\]

Multiply both sides by $91$,

\[455 = 91(25) - 182(10).\]

This gives a particular integer solution, $x_0 = -182, \qquad y_0 = 91.$

The general integer solution of $10x + 25y = 455$ is

\[\boxed{ \begin{aligned} x &= -182 + 5t, \\ y &= 91 - 2t, \end{aligned} \qquad t \in \mathbb{Z}. }\]

Non-Negativity Constraints

Since coin counts must be non-negative,

\[x \ge 0 \;\Rightarrow\; -182 + 5t \ge 0 \;\Rightarrow\; t \ge 36.4,\] \[y \ge 0 \;\Rightarrow\; 91 - 2t \ge 0 \;\Rightarrow\; t \le 45.5.\]

Hence,

\[37 \le t \le 45.\]

Maximum and Minimum Number of Coins

The total number of coins is $x + y = (-182 + 5t) + (91 - 2t) = -91 + 3t.$

Therefore, the total number of coins is increasing in $t$.

It follows that:

  • the minimum number of coins occurs at the smallest admissible value of $t$,
  • the maximum number of coins occurs at the largest admissible value of $t$.

At $t = 37$ (minimum $t$),

\[x = 3, \quad y = 17, \quad x + y = 20.\]

At $t = 45$ (maximum $t$),

\[x = 43, \quad y = 1, \quad x + y = 44.\]

Equal Numbers of Coins

Let $x = y$. Then, $-182 + 5t = 91 - 2t$ which gives $7t = 273 \;\Rightarrow\; t = 39.$

Substituting $t = 39$, we have $x = y = 13.$

Thus, the answer is yes.

Final Answer

  • Maximum number of coins: $\boxed{44}$
  • Minimum number of coins: $\boxed{20}$
  • Equal numbers of coins possible: $\boxed{\text{Yes}}$

Note: The procedure of checking $\gcd(a,b)\mid c$, performing back substitution, and parameterising all solutions is the standard approach to linear Diophantine equations. This mirrors feasibility checks in integer optimization, cryptography, and algorithmic design.