Friday, May 20, 2005

Chickens and Primes

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.

9 comments:

  1. Doesn't this follow almost directly from the Chinese Remainder theorem?  

    Posted by Graham

    ReplyDelete
  2. how ? 

    Posted by Suresh

    ReplyDelete
  3. 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.  

    Posted by Graham

    ReplyDelete
  4. 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. 

    Posted by Suresh

    ReplyDelete
  5. 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?
     

    Posted by Anonymous

    ReplyDelete
  6. An email from Nick Reingold 
    Hi 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

    ReplyDelete
  7. 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

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

    Posted by Anonymous

    ReplyDelete
  8. The general problem

    given 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

    ReplyDelete
  9. 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

Disqus for The Geomblog