In football (american, not soccer) if you have possession of the ball you can score 3 points with a field goal, or 6 points with a touchdown, which can be followed by 1 or 2 extra points. Thus, for example, you cannot manage a total score of just 2 points. (As a matter of fact, you
could get this score with a "safety", but let's disregard this unlikely possibility and forget safeties.) What's the maximum unattainable score?
Another question: assuming you could only score field goals for 3 points and touchdowns for 7 points... what would then be the maximum unattainable score?
The 6-point touchdown with no extra points added doesn't do anything to go beyond the every-multiple-of-3 possibilities of the field goal. But combining multiples of 3, 7 and 8 will provide more than just multiples of 3.
Let's tackle the second problem first. After that we can see if the addition of 8 to the possibilities helps.
The GCD of 3 and 7 is 1. There is a form of the Euclidean algorithm that gives us the number of occurrences of each (of 3 and 7) that would be required to form 1, and to form zero. While it may seem obvious in this instance, let's just go through that algorithm, even if only to show how it's done for more complicated pairs of numbers:
7 1 0
3 0 1
1 1 -2
0 -3 7
The first line just says 7 = 1*7 + 0*3; the second says 3 = 0*7 + 1*3. Each successive line is obtained by dividing the previous number in the first column into the number above it and writing the remainder below it. (7 / 3 leaves remainder 1, written below the 3). The quotient of that division is used in multiplying the other two numbers on the divisor line and subtracting from the respective two numbers above them. So 1 - 2*0 = 1, which is placed in column 2 next to the 1 in column 1, and 0 - 2*1 = -2, placed in column 3 on that line. Similarly 1 goes into 3 three times leaving a remainder of zero.
The results are no surprise: 1 can be obtained with 1 seven and -2 threes. Zero is equivalent to -3 sevens plus 7 threes. We, also obviously, cannot get a score of 1 or 2.
To get a given score, we need to divide that score by the GCD (but this is 1 in this case) and use that many multiples of, in this case, 1 seven and -2 threes, and then use multiples of -3 sevens and 7 threes to make the number of threes positive. If that results in the number of sevens going negative, then there is no possibility of that score being attained with just 3's and 7's.
Obviously the least score that can be obtained by a combination of 3's and 7's is 10:
10 = 1*7 + 1*3
To get 11 we'd add one seven and take away 2 threes:
11 = 2*7 + (-1)*3
The negative is unsatisfactory, so we try adding -3 sevens and 7 threes:
11 = (-1)*7 + 6*3
so we see we can't get a score of 11 from 3's and 7's.
How about 12? Obviously it's 4*3, but to go with our framework:
12 = 3*7 + (-3)*3
12 = 0*7 + 4*3
Adding 1 seven and -2 threes then gives us
13 = 1*7 + 2*3
and then
14 = 2*7 + 0*3
and then
15 = 3*7 + (-2)*3
15 = 0*7 + 5*3
then
16 = 1*7 + 3*3
17 = 2*7 + 1*3
18 = 3*7 + (-1)*3
18 = 0*7 + 6*3
We can see the pattern that each time from here on that we need to add 7 threes, the 3 sevens that we have to subtract will not make the number of sevens negative, and so will be OK. That leaves 11 as the largest impossible score when the only scorings allowed are 3 and 7.
Back to the original problem: The allowing of a scoring of 8 makes a score of 11 possible, with 3+8. Ten is still possible as 7+3 and 9 is a multiple of 3. Eight is of course 8 and 7 is 7 and 6 is a multiple of 3. That leaves 5 as the highest impossible score in the original problem.
|
|
Posted by Charlie
on 2005-04-10 16:58:39 |
solution
