soccerisgreat said:
1. In a dart game, only 4 points or 9 points can be scored on each dart. What is the largest score that it is NOT possible to obtain? (Assume that you have an unlimited number of darts.)
This should give you a clue as how to proceed.
Stamp Combinations
Here is the same problem with different numbers that will allow you to work out your own.
If a stamp machine were to dispense only stamps of values m cents and n cents, m less than n, how many exact postage values in cents cannot be made and what is the highest value not attainable?
If m and n have a common factor, there will always be an infinite number of values that cannot be made. Thus, m and n need be relatively prime.
For illustrative purposes, consider an example with the stamp values of m = 4 cents and n = 7 cents.
Create a table starting with 1, writing consecutive numbers in rows with n numbers to a row, stopping with m rows (m < n). All obtainable numbers are now marked off. They consist of 1) the multiples of n (the last column), 2) the remaining (n - 1) multiples of m (4, 8, 12, 16, 20, and 24 in the example), and 3) the numbers directly below each marked multiple of m, obtainable by adding to the multiple of an appropriate multiple of n. We end up with the following table, the / following a number meaning it has been crossed out.
.1.....2.....3.....4/.....5.....6.....7/
.8/....9....10...11/...12/...13...14/
15/..16/..17...18/...19/...20/..21/
22/..23/..24/..25/...26/..27/...28/
for a total of 9 unattainable values and 17 as the highest unattainable value.
If m and n have no common factor, the table contains marks in every column; then all numbers larger than those appearing in the table are obtainable, and the answer to the problem is the quantity of unmarked numbers.
The expression giving the number of unattainable numbers directly is N = (n - 1)(m - 1)/2. For our m = 4 and n = 7 example, N = (4 - 1)(7 - 1)/2 = 3x6/2 = 9.
The expression giving the highest unattainable number directly is H = 2N - 1 = mn - (m + n) = n(m - 1) - m. For our example, H = 7(4) - (7 + 4) = 17.
Considering the case where m = 3 and n = 10:
.1.....2.....3/.....4.....5....6/.....7.....8....9/....10/
11...12/..13/...14...15/..16/...17...18/..19/...20/
21/..22/..23...24/...25/..26/..27/. .28/..29/...30/
for a total of 9 unattainable whole number values, verifiable by N = (3 - 1)(10 - 1)/2 = 2x9/2 = 9, the highest being 2(9) - 1 = 17.
Consider the case where m = 5 and n = 11.
After crossing out the numbers according to the rules of engagement, I was left with 20 uncrossed numbers. Using the expressions for the highest and total unavailable values, N = (5 - 1)(11 - 1)/2 = 4x10/2 = 20 and H = 2(20) - 1 = 39.
Considering m = 5 and n = 7 cent stamps, we derive
.1......2......3......4.....5/......6.......7/
.8......9....10/....11...12/.....13.....14/
15/...16...17/....18....19/....20/....21/
22/...23...24/....25/...26/....27/....28/
29/...30/...31/...32/...33/....34/....35/
Counting, we find 12 impossible postage amounts, the highest being 23 cents. Verifying, the unobtainable N = (n - 1)(m - 1)/2 = (6)(4)/2 = 12 and the highest unobtainable postage becomes H = mn - (m + n) = 5(7) - (5+7) = 35 -12 = 23.
The expressions for calculating the total number of unattainable values and the highest unattainable value derives from the following. Several values of m and n were examined to arrive at the following data.
For n = 7...........N........H.......N..........H......N..........H
m = 3................6........11
m = 4....................................9..........17
m = 5.......................................................12.........23
For n = 11.........N........H.......N..........H......N..........H
m = 3...............10.......19
m = 5..................................20.........39
m = 7.......................................................30.........59
For n = 13.........N........H.......N..........H......N..........H
m = 5...............24......47
m = 7..................................36.........71
m = 11.....................................................60........119
We can now create straight line relationships of the form y = mx + b for each value of n. Letting m be the x value and N and H the y value, we obtain
For n = 7 N = 3m - 3 and h = 6m - 7
For n = 11, N = 5m - 5 and H = 10m -11
For n = 13 N = 6m - 6 and h = 12m - 13
Careful examination of these expressions and the associated data reveal that, for each value of n, the slope in the N expressions is (n-1)/2 while the y intercept is -(n-1)/2. Similarly, for each value of n, the slope of the H expressions is (n-1) while the y intercept is -n. In general then, substituting these expressions for the slope and y intercept in place of the specific numbers derived for specific values of n, we can express the N value by N = (n-1)m/2 - (n-1)/2 which when expanded and simplified results in N = (n-1)(m-1)/2. We can also express the H value by H = (n-1)m - n.
