The Coin-Exchange Problem

Section 10.4 The Coin-Exchange Problem

In this exercise, we will solve and extend a classical problem of Ferdinand Georg Frobenius (1849–1917). Suppose \(a\) and \(b\) are relatively prime

This means that the integers do not have any common factor.

positive integers, and suppose \(t\) is a positive integer. Consider the function

\begin{equation*} f(z) \ = \ \frac{ 1 }{ \left( 1 - z^{ a } \right) \left( 1 - z^{ b } \right) z^{t+1} } \, \text{.} \end{equation*}

🔗

Compute the residues at all nonzero poles of \(f\text{.}\)
🔗

🔗
Verify that \(\Res_{z=0}( f ) = N(t)\text{,}\) where

\begin{equation*} N(t) \ = \ \left| \left\{ (m,n) \in \Z : \, m,n \geq 0 , \, ma+nb = t \right\} \right| \text{.} \end{equation*}

🔗

🔗
Use the Residue Theorem, Theorem 9.2.2, to derive an identity for \(N(t)\text{.}\) (Hint: Integrate \(f\) around \(C[0,R]\) and show that this integral vanishes as \(R \to \infty\text{.}\))
🔗

🔗
Use the following three steps to simplify this identity to

\begin{equation*} N(t) \ = \ \frac{ t }{ a b } - \left\{ \frac{ b^{-1} t }{ a } \right\} - \left\{ \frac{ a^{-1} t }{ b } \right\} + 1 \,\text{.} \end{equation*}

Here, \(\{ x \}\) denotes the fractional part
²
The fractional part of a real number \(x\) is, loosely speaking, the part after the decimal point. More thoroughly, the greatest integer function of \(x\text{,}\) denoted by \(\lfloor x \rfloor\text{,}\) is the greatest integer not exceeding \(x\text{.}\) The fractional part is then \(\{ x \} = x - \lfloor x \rfloor\text{.}\)
of \(x\text{,}\) \(a^{-1} a \equiv 1\) (mod \(b\))
³
This means that \(a^{-1}\) is an integer such that \(a^{-1} a = 1 + kb\) for some \(k \in \Z\text{.}\)
, and \(b^{-1} b \equiv 1\) (mod \(a\)).

🔗
1. Verify that for \(b=1\text{,}\)
  
  \begin{align*} N(t) \amp \ = \ \left| \left\{ (m,n) \in \Z : \, m,n \geq 0 , \, ma+n = t \right\} \right| \\ \amp \ = \ \left| \left\{ m \in \Z : \, m \geq 0 , \, ma \leq t \right\} \right|\\ \amp \ = \ \left| \left[ 0 , \frac{t}{a} \right] \cap \Z \right| \ = \ \frac{t}{a} - \left\{ \frac{ t }{ a } \right\} + 1 \, \text{.} \end{align*}
  
  🔗
  
  🔗
2. Use this together with the identity found in Item 3 to obtain
  
  \begin{equation*} \frac{1}{a} \sum_{ k=1 }^{a-1} \frac{ 1 }{ ( 1 - e^{ 2 \pi i k/a } ) \, e^{ 2 \pi i kt/a } } \ = \ - \left\{ \frac{t}{a} \right\} + \frac{1}{2} - \frac{1}{2a} \, \text{.} \end{equation*}
  
  🔗
  
  🔗
3. Verify that
  
  \begin{equation*} \sum_{ k=1 }^{a-1} \frac{ 1 }{ ( 1 - e^{ 2 \pi i kb/a } ) \, e^{ 2 \pi i kt/a } } \ = \ \sum_{ k=1 }^{a-1} \frac{ 1 }{ ( 1 - e^{ 2 \pi i k/a } ) \, e^{ 2 \pi i k b^{-1} t/a } } \, \text{.} \end{equation*}
  
  🔗
  
  🔗
🔗
Prove that \(N(ab-a-b) = 0\text{,}\) and \(N(t) > 0\) for all \(t > ab-a-b\text{.}\)
🔗

🔗

Historical remark. Given relatively prime positive integers \(a_{1} , a_2, \dots , a_{n}\text{,}\) let’s call an integer \(t\) representable if there exist nonnegative integers \(m_{ 1 } , m_2, \dots , m_{ n }\) such that

\begin{equation*} t \ = \ m_1 \, a_1 + m_2 \, a_2 + \dots + m_n \, a_n \,\text{.} \end{equation*}

🔗

(There are many scenarios in which you may ask whether or not \(t\) is representable, given fixed \(a_{1} , a_2, \dots , a_{n}\text{;}\) for example, if the \(a_j\)’s are coin denomination, this question asks whether you can give exact change for \(t\text{.}\)) In the late 19th century, Frobenius raised the problem of finding the largest integer that is not representable. We call this largest integer the Frobenius number \(g ( a_{1} , \dots , a_{n} )\text{.}\) It is well known (probably at least since the 1880’s, when James Joseph Sylvester (1814–1897) studied the Frobenius problem) that \(g(a_{1},a_{2}) = a_{1} a_{2} - a_{1} - a_{2}\text{.}\) You verified this result in Item 5. For \(n>2\text{,}\) there is no nice closed formula for \(g ( a_{1} , \dots , a_{n} )\text{.}\) The formula in Item 4 is due to Tiberiu Popoviciu (1906–1975), though an equivalent version of it was already known to Peter Barlow (1776–1862).

🔗

Prev Top Next