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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4