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.

Return to MathPages Main Menu