Have you ever had an annoying mathematical headworm, a puzzle that starts buzzing around in your head and won't go away till you solve it ? Well, if you have, and don't like the feeling, don't read further.
Via think again ! comes this intriguing puzzle. The original involves KFC and puzzled managers and is far more colorful. The pared-down version presented here is:
Given two relatively co-prime numbers A and B, show that there exists a number M such that all numbers N > M can be expressed as non-negative integer combinations of A and B (i.e for all N > M, there exist p, q non-negative integers such that N = pA + qB). Find this M = f(A, B).
Note that the coprime condition is critical else only multiples of gcd(A, B) can be expressed at all, and the statement is trivially false.
Doesn't this follow almost directly from the Chinese Remainder theorem?
ReplyDeletePosted by Graham
how ?
ReplyDeletePosted by Suresh
One of the consequences of CRT I remember learning is that any integer can be expressed as pA + qB. Only, p and q may be negative. So, do some futzing around mod AB, and you can show that so long as N > AB - max(A,B) you can make both p and q non-negative.
ReplyDeletePosted by Graham
ok. there is an elementary proof that is a bit stronger. the answer is AB - A - B, which is slightly stronger than what you propose.
ReplyDeletePosted by Suresh
Another interesting version is how many can't you represent as such. In particular this is the coin exchange problem. If you had coins of denomination A and B, which is the largest number you can't change and how many can't you change? How about if you had k denominations?
ReplyDeletePosted by Anonymous
An email from Nick Reingold
ReplyDeleteHi Suresh,
The problem at your blog is very classical. Here's one approach:
Consider 0*B, 1*B, 2*B, ..., (A-1)*B. Since (A,B)=1, these are distinct
(mod A). Take N>(A-1)*(B-1)=(A-1)*B-A+1. Suppose that N=j*B (mod A),
with 0<=j<=A-1. If N<j*B then N+A<=j*B<=(A-1)*B, so N<=(A-1)*B-A,
which is impossible. So N>=j*B, and so can be written as k*A+j*B for
some k>=0.
On the other hand, (A-1)*B-A clearly cannot be written this way.
Thus f(M)=(A-1)*(B-1).
Posted by Nick Reingold
Given positive integers a, b, ..., z whose gcd is 1. It is not hard to show that all sufficiently large n can be written as an integral non-negative linear combination of a, b, ..., z
ReplyDeleteDo you guys know of a formula computing the largest n which cannot be written that way?
Posted by Anonymous
The general problem
ReplyDeletegiven n positive integers a_1, a_2, ..., a_n whose gcd is 1, find the largest integer which cannot be written as a nonnegative integer combination of them
is known as the Frobenius problem. It is also known as the coin problem (what is the largest amount you can't make change for).
There is no simple formula known for n > 3. If n is part of the input, the problem is NP-hard. Ravi Kannan gave a non-trivial polynomial-time algorithm for fixed n (polynomial in the number of bits used to represent the a_i). MathWorld has some more information.
Posted by David Applegate
Ciao Suresh ! Non potevi esprimere meglio il tuo pensiero riguardo a Chickens and Primes . Complimenti per il tuo blog, è davvero bello! Continua a tenerlo aggiornato! Se ti va di visitare il mio sito che riguarda scommesse clicca su questo link: qui troverai solo scommesse !
ReplyDelete