Назовём автобусный билет счастливым, если сумма цифр его номера делится на 13. пример номера счастливого билета, для которого следующий билет тоже счастливый.
Ну, или 93999. Можно подумать про принцип формирования таких чисел. 1) Пусть число не оканчивается на 9. Тогда изначально сумма его цифр была S, кратная 13. Затем она стала S+1, которая уже не кратна 13. Отсюда делаем вывод, что число должно обязательно оканчиваться на 9. 2) Теперь определим, на сколько же девяток должно оканчиваться это число. Разобьем число на две части: префикс и суффикс. Суффикс полностью состоит из девяток. Пусть суффикс длины n.Тогда сумма цифр в суффиксе равна 9n. Теперь пусть сумма цифр в префиксе равна S. (Разберем разбиение на примере любого числа. Возьмем, например, 1234439999. Сумма префикса S=1+2+3+4+4+3=17, сумма суффикса равна 9*4=36.) Тогда происходят такие вещи: а) Сначала сумма цифр равна S + 9n. По условию, она кратна 13. Тогда S +9n = 13a, где a - некоторое целое и большее нуля число. б) Теперь прибавляем к этому числу 1. После этого действия сумма в префиксе увеличивается на 1, а сумма в суффиксе становится равна 0, так как суффикс полностью состоит из девяток. Новое равенство: S+1 + 0*n = 13b, где b - некоторое целое и большее нуля число. Имеем систему уравнений: S +9n = 13a, S + 1 = 13b Переменных больше, чем уравнений, значит, число решений бесконечно много. Из первого уравнения вычтем второе, получим: 9n-1=13(a-b) n = (13 (a - b) + 1) / 9 = (4 (a - b) + 1) / 9 + a - b Тогда можно подобрать такие пары чисел a и b, где a > b, что n будет целым числом. Пусть a - b = q, тогда n = (4q + 1) / 9 + q, а 4q+1 должно быть кратно 9. Это значит, что 4q+1=9A, где A-целое. 4q=9A-1 q = (9A-1) / 4 = (4 * 2A + A - 1) / 4 = 2A + (A-1)/4 Отсюда видно, что A-1 должно быть кратно 4. Тогда A-1 = 4B, где B - некоторое целое число, больше или равное 0. Тогда A = 4B+1 - уже ограничений на делимость нет. Поэтому можно вернуться к переменным, введенным ранее. q = (9 * (4B+1) - 1) / 4 = 9B + 2. n = (4q + 1)/9 + 2q = (4 * (9B + 2) + 1) / 9 + 9B + 2 = 13B + 3 a = b + 9B + 2. S = 13b - 1 Теперь уже смело можно выбирать целые числа b и B, чтобы определить a. После определения a однозначно определятся n и S. Тогда уже, зная n и S, можно выписать множество чисел, обладающих свойствами, указанными в условии. Вот пример, если запутались: Пусть b = 3, B = 1. Тогда: a = 1 + 9*1 + 2 = 12. S = 13b - 1 = 13*3 - 1 = 38, n = 13B + 3 = 13*1 + 3 = 16 При таких параметрах получится число, например, такое: 7878719999999999999999.
Можно подумать про принцип формирования таких чисел.
1) Пусть число не оканчивается на 9. Тогда изначально сумма его цифр была S, кратная 13. Затем она стала S+1, которая уже не кратна 13. Отсюда делаем вывод, что число должно обязательно оканчиваться на 9.
2) Теперь определим, на сколько же девяток должно оканчиваться это число. Разобьем число на две части: префикс и суффикс. Суффикс полностью состоит из девяток. Пусть суффикс длины n.Тогда сумма цифр в суффиксе равна 9n. Теперь пусть сумма цифр в префиксе равна S. (Разберем разбиение на примере любого числа. Возьмем, например, 1234439999. Сумма префикса S=1+2+3+4+4+3=17, сумма суффикса равна 9*4=36.)
Тогда происходят такие вещи:
а) Сначала сумма цифр равна S + 9n. По условию, она кратна 13. Тогда S +9n = 13a, где a - некоторое целое и большее нуля число.
б) Теперь прибавляем к этому числу 1. После этого действия сумма в префиксе увеличивается на 1, а сумма в суффиксе становится равна 0, так как суффикс полностью состоит из девяток. Новое равенство: S+1 + 0*n = 13b, где b - некоторое целое и большее нуля число.
Имеем систему уравнений:
S +9n = 13a,
S + 1 = 13b
Переменных больше, чем уравнений, значит, число решений бесконечно много.
Из первого уравнения вычтем второе, получим:
9n-1=13(a-b)
n = (13 (a - b) + 1) / 9 = (4 (a - b) + 1) / 9 + a - b
Тогда можно подобрать такие пары чисел a и b, где a > b, что n будет целым числом. Пусть a - b = q, тогда n = (4q + 1) / 9 + q, а 4q+1 должно быть кратно 9.
Это значит, что 4q+1=9A, где A-целое.
4q=9A-1
q = (9A-1) / 4 = (4 * 2A + A - 1) / 4 = 2A + (A-1)/4
Отсюда видно, что A-1 должно быть кратно 4.
Тогда A-1 = 4B, где B - некоторое целое число, больше или равное 0.
Тогда A = 4B+1 - уже ограничений на делимость нет. Поэтому можно вернуться к переменным, введенным ранее.
q = (9 * (4B+1) - 1) / 4 = 9B + 2.
n = (4q + 1)/9 + 2q = (4 * (9B + 2) + 1) / 9 + 9B + 2 = 13B + 3
a = b + 9B + 2.
S = 13b - 1
Теперь уже смело можно выбирать целые числа b и B, чтобы определить a. После определения a однозначно определятся n и S. Тогда уже, зная n и S, можно выписать множество чисел, обладающих свойствами, указанными в условии.
Вот пример, если запутались:
Пусть b = 3, B = 1. Тогда:
a = 1 + 9*1 + 2 = 12.
S = 13b - 1 = 13*3 - 1 = 38,
n = 13B + 3 = 13*1 + 3 = 16
При таких параметрах получится число, например, такое:
7878719999999999999999.