In Austrian Rules Football touchdowns count for 7 points and

In Austrian Rules Football, touchdowns count for 7 points and field goals count for 5 points. There are no point-afters, safeties, etc. and no other ways to score. Determine the lowest score N such that N and every score larger than N are attainable in Austrian Rules football. Then prove that your answer is correct using regular mathematical induction.

Solution

N = 24

Proof by induction:

Base case : For N = 24; 24 = (2) * 5 + (2) * 7

Inductive Step:

Now suppose a number n>=24 can be written as (a) * 5 + (b) * 7 where a and b are non-negative integers.To complete the proof, we just need to proove that n+1 can be written as (a\') * 5 + (b\') * 7 where a\' and b\' are non-negative integers.

We have 1 = (3) * 5 + (-2) * 7 = (-4) * 5 + (3) * 7.

Therefore if b >= 2, n +1 = (a+3) * 5 + (b-2) * 7, else if a >=4, n+1 = (a-4) * 5 + (b+3) * 7. The case where both b < 2 and a < 4 cannot occur because the largest such number is (4-1) * 5 + (2-1) * 7 = 22.

We also need to proove that 24 is the smallest such number.

23 = (-1) * 5 + (4) * 7

23 = (6) * 5 + (-1) * 7

If we try to increase the corfficient of 5, the coefficient of 7 has to be decreased by 5; If we try to increase the corfficient of 7, the coefficient of 5 has to be decreased by 7. In both cases one of the coefficients will be negative. Thus 23 cannot be written as (a) * 5 + (b) * 7, where a and b are both non negative. Thus 24 is the smallest such N.