2
$\begingroup$

In the Frobenius Coin problem (or Chicken McNugget theorem) for $n>2$, do the numbers have to be pairwise relatively prime, or just relatively prime in totality?

$\endgroup$
  • $\begingroup$ Only relatively primein totality, for them to cover all values from some point on. The last uncovered value is denoted $g(a_1,...,a_n)$ and called the Frobenius number of the list of $a_k.$ There's something about this on wiki page for "coin problem". $\endgroup$ – coffeemath Feb 5 '15 at 10:28
2
$\begingroup$

They$\let\geq\geqslant\let\leq\leqslant$ need not be pairwise relatively prime. The reason why is essentially that Bézout's theorem works fine when we are only given that $\gcd(a_1,\ldots,a_n)=1$. Of course, it does not immediately follow that we can take the Bézout coefficients positive for sufficiently large numbers. Here's a quick way to see why:

Suppose we want to write $m\in\mathbb N$ as $x_1a_1+\cdots+x_na_n$ with $x_1,\ldots,x_n\geq0$. Bézout already gives us such $x_1,\ldots,x_n\in\mathbb Z$, but they can be negative. Now let $(q_k,r_k)$ be quotient and remainder when $x_k$ is divided by $\frac{a_1\cdots a_n}{a_k}$. Then

$$\begin{align*} m &= \sum_{k=1}^nq_k(a_1\cdots a_n)+r_ka_k\\ &= (q_1+\cdots+q_n)\cdot a_1\cdots a_n+\sum_{k=1}^nr_ka_k. \end{align*}$$ Because $r_k\leq\frac{a_1\cdots a_n}{a_k}-1$, we have $q_1+\cdots+q_n>0$ as soon as $m>\sum_{k=1}^na_k\left(\frac{a_1\cdots a_n}{a_k}-1\right)$.

Then $$m=a_1(a_2\cdots a_n(q_1+\cdots+q_n)+r_1)+\sum_{k=2}^nr_ka_k$$ where all coefficients are non-negative.

Note: this technique allows to prove that $$g(a_1,\ldots,a_n)\leq(n-1)a_1\cdots a_n-(a_1+\cdots+a_n).$$ This upperbound is sharp for $n=2$, but weak for $n>2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.