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?

To prove that the highest impossible score in this football league is 7 points, we can use a concept called "Frobenius coin problem" or "Frobenius number." The Frobenius number is defined as the largest number that cannot be expressed as the sum of non-negative multiples of two given numbers.

In this case, we can consider the field goal as one type of coin worth 5 points and the touchdown as another type of coin worth 3 points. The goal is to find the highest score that cannot be achieved using any combination of these two coins.

To approach this problem, we can use a technique called the "Chicken McNugget Theorem" or "Postage Stamp Problem." The Chicken McNugget Theorem states that for any two relatively prime positive integers, the greatest number that cannot be expressed as the sum of multiples of those two integers is given by the formula:

g = (a * b) - (a + b)

where a and b are the values of the two coins.

In this case, a = 5 (field goal points) and b = 3 (touchdown points). Since 5 and 3 are relatively prime (they have no common factors other than 1), we can apply the formula:

g = (5 * 3) - (5 + 3) = 15 - 8 = 7

Therefore, the highest impossible score is 7 points.

To prove that all higher scores can be achieved, we need to show that any number greater than 7 can be expressed as a combination of field goals and touchdowns.

To do this, we can use a greedy algorithm. We start with the highest-scoring option, which is the field goal. We keep adding field goals until the remaining score is a multiple of 3, at which point we can convert the remaining score into touchdowns.

Here's an example:

- If the score is 8, we can add one field goal (5 points) and convert the remaining 3 points into one touchdown.
- If the score is 9, we can add two field goals (10 points) and convert the remaining 1 point into a touchdown.
- If the score is 10, we can add two field goals (10 points) and leave the score as is since it is already a multiple of 3.

By following this approach, we can see that any number greater than 7 can be expressed as a combination of field goals and touchdowns. Therefore, all higher scores are possible in this football league.