A certain football league has the following scoring system:
- each field goal counts for 5 points
- each touchdown counts for 3 points
The only way to score points is with some combination of field goals
and touchdowns.
They have noticed that not every score is possible in this league
(for example 1, 2, 4...); in fact they think that they know the
highest score that is impossible to make. I have figured out that this
is 7 points, but I would like to know why. How can I prove that this
score is impossible and that all higher scores are possible?
Generally when two integers, say p and q, are relatively prime (have no common divisor) then there exists integers u and v such that for "any" integer n
n = up + vq
Here p and q are 5 and 3. If the numbers are not relatively prime then the only numbers that can be written like this are all multiples of the gcd of the two numbers.
I know there is some rule that after a certain number all of the positive numbers can be written using only positive integers, but I don't recall it offhand. It should be in an elementary number theory text somewhere; I know I've seen it in several places, but I can't recall it right now.
To prove that 7 points is the highest score that is impossible to make in this football league, we can use a mathematical concept called the Frobenius coin problem. This problem is often used to find the largest number that cannot be expressed as a combination of certain integers.
In this case, we have two possible scores: field goal (5 points) and touchdown (3 points). Let's assume that we can express any score greater than or equal to 8 using these two scores.
First, let's look at the possible scores we can make using only field goals. We can have 0, 5, 10, 15, 20, and so on. These scores are multiples of 5.
Next, let's consider the possible scores using only touchdowns. We can have 0, 3, 6, 9, 12, and so on. These scores are multiples of 3.
Now, let's look at the possible combinations of field goals and touchdowns. We can combine the multiples of 5 and 3 to get scores such as 0, 3, 5, 6, 9, 10, 12, 15, 18, 20, and so on. We can see that any number that can be expressed as 3x + 5y, where x and y are positive integers or zero, can be achieved.
But what about the number 7? We can try to express it as 3x + 5y, but we cannot find any combination of x and y that satisfies this equation. Therefore, 7 is the largest score that is impossible to make using only field goals and touchdowns.
To prove that all higher scores are possible, we can use the concept of relatively prime numbers. Two integers, such as 5 and 3 in this case, are relatively prime if they have no common divisors other than 1. When two numbers are relatively prime, it is guaranteed that every integer greater than the product of these two numbers can be expressed as their combination.
In this case, 5 and 3 are relatively prime since their only common divisor is 1. According to the Frobenius coin problem, once we pass the number 5 * 3 - 5 - 3 = 7, all higher scores can be expressed using a combination of field goals and touchdowns.
Therefore, the number 7 is the largest score that is impossible to make in this football league, and all higher scores are possible to achieve.