Diophantine Walk-a-thon

We often need to know, for integers x,y, the solutions to equations 
of the form axy+bx+cy=d where a,b,c,d are integers.  If we multiply 
both sides of the equation by a and add bc to both sides we get

                   (ax+c)(ay+b) = (ad+bc)

Then each factorization  uv = (ad+bc) gives a rational solution

                 x = (u-c)/a      y = (v-b)/a

The requirement for integer solutions is that (ad+bc) can be split into
factors uv such that u-c and v-b are both divisible by a.  Any solution 
must be of this form, so there are at most only finitely many integer
solutions.

One application of this is The Diophantine Walk-a-thon Problem:

  Two brothers are going to participate in a walk-a-thon, and they 
  have each received pledges for certain amounts of money per mile 
  (no fractional-cent pledges are accepted, and fractional miles will 
  not be counted).  To get their pledge drive started, the boys' 
  mother pledged 5 cents/mile to each of them.  On the eve of the 
  walk the two boys figure out that the maximum amount of money that 
  CANNOT be their combined total "earnings", regardless of how many 
  miles they each walk, is $576.57.  How much, per mile, had been 
  pledged?

The solution is based on that fact that, for any co-prime positive 
integers x and y, the maximum integer c such that ax+by=c has no 
solutions in non-negative integers a,b is xy-x-y.  Thus, given c, 
we need the solutions of xy-x-y = c.  Adding 1 to both sides allows 
us to factor this equation as (x-1)(y-1) = (c+1).  Since c=57657 
we know that 57658 must be the product of (x-1) and (y-1).  The 
prime factorization of 57658 is (2)(127)(227), so the only 
possible factorizations are

                  (x-1)    (y-1)      x       y
                  ------   ------   -----   -----
                    1      57658      2     57659
                    2      28829      3     28830
                  127        454    128       455
                  227        254    228       255

The first two can be ruled out because each boy received at least 
5 cents.  The fourth can be ruled out because 228 and 255 are not 
co-prime. Therefore, the third factorization gives the only possible 
answer: one brother had pledges of $1.28/mile and the other had 
pledges of $4.55/mile.

Another puzzle whose solution relies on the solution of a linear
diophantine equation is "The Beastly Urn" problem:  

  An urn contains 666 white marbles.  What is the minimum number 
  of marbles, some red and some green, that must be added so that 
  if all the marbles are then drawn out one-by-one, the expected 
  number of occurrances of a red followed immediately by a green 
  is exactly 1?

Let R,G,W denote the number of red, green, and white marbles,
respectively, and let T=R+G+W denote the total.  For any two 
consecutive draws in the sequence the probability of a red marble 
on the first AND a green on the second is given by the conditional
probability formula

  Pr{(1st red)AND(2nd green)}

                 =   Pr{1st red} Pr{(2nd green)|(1st red)}

Hence the probability is (R/T)(G/(T-1)).  Also, there are T-1 sets
of two consecutive draws, so the total expected number of such
occurrences is (T-1)[(R/T)(G/(T-1))] = RG/T.  We want this to equal
1, so we have RG/T=1, which gives  RG = R + G + 666.  Thus we have

                    RG - R - G = 666
and so

           (R-1)(G-1)  =  667  =  (23)(29)

Hence we must have R=24,G=30, or else R=30,G=24, and in either case
the total number of red and green marbles added to the 666 white
marbles is 54.