Impossible Numbers
-
My friend posed the following question to me, that a friend of his was given in her math class: Suppose in a simplified game of (American) football that the only possible amount of points one can score at a time are 3 or 7. What is the highest score that is impossible to achieve? For example, 17 is a possible score (7 + 7 + 3) but 11 is not (there is no combination of 3's and 7's you can add together to get 11). Of course, since this is given in the context of a game, there can be no negative scores, so (7 + 7 - 3) doesn't work. I wrote a small program to brute-force the solution, and searching up to 1000 I found the maximum impossible score is 11. However, I am not able to prove it. This problem reminds me of some things we did in Number Theory class but it's been a while and I've hence forgotten a lot of it. Any pointers?
-- Marcus Kwok
-
My friend posed the following question to me, that a friend of his was given in her math class: Suppose in a simplified game of (American) football that the only possible amount of points one can score at a time are 3 or 7. What is the highest score that is impossible to achieve? For example, 17 is a possible score (7 + 7 + 3) but 11 is not (there is no combination of 3's and 7's you can add together to get 11). Of course, since this is given in the context of a game, there can be no negative scores, so (7 + 7 - 3) doesn't work. I wrote a small program to brute-force the solution, and searching up to 1000 I found the maximum impossible score is 11. However, I am not able to prove it. This problem reminds me of some things we did in Number Theory class but it's been a while and I've hence forgotten a lot of it. Any pointers?
-- Marcus Kwok
It's trivial to show that the score can never be 11, so you now just have to prove that all numbers greater than 11 can be scored. All numbers after 11 fall into one of 3 series: 12 + 3n + 0 = {12, 15, 18, ...} 12 + 3n + 1 = 13 + 3n = {13, 16, 19, ...} 12 + 3n + 2 = 14 + 3n = {14, 17, 20, ...} So, now just show that 12 (4 field goals), 13 (2 field goals and a touchdown), and 14 (2 touchdowns) can be scored, then all other numbers can be scored by tacking on more field goals (3n).
-
It's trivial to show that the score can never be 11, so you now just have to prove that all numbers greater than 11 can be scored. All numbers after 11 fall into one of 3 series: 12 + 3n + 0 = {12, 15, 18, ...} 12 + 3n + 1 = 13 + 3n = {13, 16, 19, ...} 12 + 3n + 2 = 14 + 3n = {14, 17, 20, ...} So, now just show that 12 (4 field goals), 13 (2 field goals and a touchdown), and 14 (2 touchdowns) can be scored, then all other numbers can be scored by tacking on more field goals (3n).
-
Fantastic! Thanks. Of course, now that I know the answer, it seems so obvious :badger:
-- Marcus Kwok
thanks: https://movied.org
-
My friend posed the following question to me, that a friend of his was given in her math class: Suppose in a simplified game of (American) football that the only possible amount of points one can score at a time are 3 or 7. What is the highest score that is impossible to achieve? For example, 17 is a possible score (7 + 7 + 3) but 11 is not (there is no combination of 3's and 7's you can add together to get 11). Of course, since this is given in the context of a game, there can be no negative scores, so (7 + 7 - 3) doesn't work. I wrote a small program to brute-force the solution, and searching up to 1000 I found the maximum impossible score is 11. However, I am not able to prove it. This problem reminds me of some things we did in Number Theory class but it's been a while and I've hence forgotten a lot of it. Any pointers?
-- Marcus Kwok
thanks: https://movied.org
-
It's trivial to show that the score can never be 11, so you now just have to prove that all numbers greater than 11 can be scored. All numbers after 11 fall into one of 3 series: 12 + 3n + 0 = {12, 15, 18, ...} 12 + 3n + 1 = 13 + 3n = {13, 16, 19, ...} 12 + 3n + 2 = 14 + 3n = {14, 17, 20, ...} So, now just show that 12 (4 field goals), 13 (2 field goals and a touchdown), and 14 (2 touchdowns) can be scored, then all other numbers can be scored by tacking on more field goals (3n).
thanks: https://movied.org