Сломанный калькулятор – 2
У вас есть сильно сломанный калькулятор. Работают только клавиши 4, 7 и +. Несмотря на это, всё же можно ввести некоторые числа. Например:
15 = 7 + 4 + 4
25 7 7 = 7 4 XNUMX + XNUMX XNUMX XNUMX + XNUMX XNUMX + XNUMX XNUMX.
CHALLENGE
Этот калькулятор не может составить числа 1, 2, 3, 5 и 6. Найдите наибольшее число, которое этот калькулятор не может составить.

РАЗВЕДКА
Замените 4 и 7 другими парами чисел. Опишите некоторые закономерности, которые вы наблюдаете.
Заметки
ВЫЗОВ И ИССЛЕДОВАНИЕ
Это сложнее, чем то, что происходит в игре «Сломанный калькулятор – 1». Математическая теорема, лежащая в основе этого, ласково называется теоремой Макнаггета. Предположим, у вас есть два взаимно простых числа n и m, то есть их наибольший общий делитель равен 1. Теорема гласит, что ровно половину чисел от 1 до (n – 1) x (m – 1) можно представить в виде сумм положительных кратных n и m, и что начиная с (n – 1) x (m – 1) можно представить каждое последующее число.
Применив эту теорему к числам 4 и 7, мы знаем, что можем получить половину чисел вплоть до (4 – 1) x (7 – 1) = 18, и что после этого мы можем получить все числа. Давайте посмотрим, как это работает в этом частном случае.
- 1 = Невозможно
- 2 = невозможно
- 3 = невозможно
- 4 = 4
- 5 = невозможно
- 6 = невозможно
- 7 = 7
- 8 = 4 + 4
- 9 = невозможно
- 10 = невозможно
- 11 = 4 + 7
- 12 = 4 + 4 + 4
- 13 = невозможно
- 14 = 7 + 7
- 15 = 4 + 4 + 7
- 16 = 4 + 4 + 4 + 4
- 17 = невозможно
- 18 = 4 + 7 + 7
Даже не разбираясь в сложной теории чисел, отважный исследователь может заметить, что половина чисел от 1 до 18 являются возможными, а другая половина — невозможными. Он также может заметить закономерность: число x возможно ровно тогда, когда возможно число 17 – x.
Ещё одна закономерность, на которую следует обратить внимание, заключается в том, что любое общее кратное двух чисел делит все суммы кратных этих чисел. Это означает, что если у двух чисел есть общее кратное больше 1, то существует бесконечное количество чисел, которые не могут быть получены этим калькулятором. Например, комбинации чисел 4 и 6 никогда не дадут нечётное число.