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