I have a word problem that goes like this:
If I have a dart game and only 4 points or 9
points can be scored on each dart. What is
the largest score that is NOT possible to
obtain? I have an unlimited number of darts.
The only impossible scores are
1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 19, and 23
All other scores are possible. Thus 23
is the largest impossible score.
Edwin
Then I got this email:
In a message dated 7/14/2006 10:58:06 AM Eastern
Standard Time, devnull@algebra.com writes:
Thanks so much. All you did was make a list of
what scores you could not combine 4 and 9 together
with each other and themselves right?
---------
No, I did this instead:
Let N be expressible as 4x + 9y, where x and y are
non-negative integers:
4x + 9y = N
4x + 8y + y = N
Divide thru by 4
x + 2y + y/4 = N/4
x + 2y = N/4 - y/4 = (N-y)/4
The left side is a positive integer so the right side
must be too, say it's = A
(N-y)/4 = A
N-y = 4A
y = N-4A
Substitute in
4x + 9y = N
4x + 9(N-4A) = N
4x + 9N - 36A = N
4x = 36A - 8N
x = 9A - 2N
Since x and y ar non-negative,
x > -1 and y > -1
9A - 2N > -1 and N - 4A > -1
9A > 2N-1 and -4A > -N - 1
A > (2N-1)/9 and A < (N+1)4
(2N-1)/9 < A < (N+1)/4
So there will always be a solution if there is a
non-negative integer A between (2N-1)/9 and (N+1)/4
If these differ by more than 1 then there definitely
will be a solution, for there is always an integer
between any two numbers which differ by more than 1.
If they differ by 1 or less there may or may not be
a solution.
There will always be a solution if there is an
integer between them, though.
Then to guarantee a solution, then, the difference
must be > 1
(N+1)/4 - (2N-1)/9 > 1
9(N+1) - 4(2N-1) > 36
9N + 9 - 8N + 4 > 36
N + 13 > 36
N > 23
So we know there will always be a solution for
any N > 23
because there will always be a non-negative
integer A such that
(2N-1)/9 < A < (N+1)/4
since there is always an integer between two
real numbers which differ by more than 1.
So the largest integer which cannot be expresses
as 4x+9y must be 23 or less. We will see if 23
can be so expressed:
(2N-1)/9 < A < (N+1)/4
(2·23-1)/9 < A < (23+1)/4
5 < A < 6
No, 23 cannot be expressed as 4x+9y because
there is no integer between 5 and 6. Therefore
23 must be the largest integer that can not be
so expressed, since all larger integers can be.
It was not necessary for me to find the lower
integers that could not be expressed as 4x+9y,
but I just entered the two expressions
Y1 = (2N-1)/9 and Y2 = (N+1)/4
(except for the TI-83 you have to use X, not N)
in my TI-83 and picked out the cases of N where
there was no integer between
them.
Edwin
