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?

Graham

ReplyDeletePosted by

how ?

Suresh

ReplyDeletePosted by

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.

Graham

ReplyDeletePosted by

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.

Suresh

ReplyDeletePosted by

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?

Anonymous

ReplyDeletePosted by

Nick Reingold

ReplyDeleteAn email from Nick ReingoldHi 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

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

Anonymous

ReplyDeleteDo you guys know of a formula computing the largest n which cannot be written that way?

Posted by

The general problem

David Applegate

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

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