Назовём волшебным натуральное девятизначное число, которое обладает следующими свойствами:
1. В нём содержатся по одному разу все цифры от 1 до 9 (т.е. все цифры кроме нуля).
2. Само волшебное число делится на 9. Если из него вычеркнуть последнюю цифру, то оставшееся восьмизначное число будет делиться на 8. Если из волшебного числа вычеркнуть последние две цифры, то оставшееся семизначное число будет делиться на 7. И так далее: вычёркивая из волшебного числа n последних цифр, мы будем получать число, которое делится на 9-n.
К примеру, если бы число 123456789 являлось волшебным (оно им не является), то число 12345678 делилось бы на 8, 1234567 делилось бы на 7, 123456 делилось бы на 6 и так далее.
Найдите это волшебное число (оно единственное).
Разумеется, эту задачу можно решить тупым перебором на компьютере. Однако, пользуясь знакомыми с детского садика признаками делимости, задачу можно решить и на бумаге, сократив пространство перебора до десятка вариантов.
Решение
Самый простой признак делимости - признак делимости на 5. Для того, чтобы число делилось на 5, оно должно заканчиваться либо на 5, либо на 0. Нуля в волшебном числе быть не может, поэтому пятая цифра может быть только пятёркой.
Наше волшебное число теперь выглядит так: ....5....
Следующий простой признак - признак делимости на 2. Из него мы заключаем, что в позициях 2, 4, 6 и 8 могут быть только чётные цифры (т.е. те же 2, 4, 6, 8), потому что иначе восьмизначное число заведомо не будет делится на 8, шестизначное на 6, четырёхзначное на 4, двухзначное на 2.
Давайте попробуем подобрать цифры на позиции 3 и 4. Мы знаем, что четырёхзначное число должно делиться на 4. Следовательно, по признаку делимости, число, образованное третьей и четвёртой цифрой, должно делиться на 4. Вспоминая, что на четвёртой позиции может быть только чётная цифра, а на третьей - только нечётная, получим следующие варианты:
Теперь посмотрим, что может стоять на позициях 6, 7 и 8. Восьмизначное число должно делиться на 8, поэтому число, образованное этими тремя цифрами тоже должно делиться на 8:
Здесь мы учли, что цифры не могут повторяться, а также то, что пятёрка уже занята.
Обратите внимание, что и четвёртая, и восьмая цифра волшебного числа могут быть либо 2, либо 6. Получается, что, например, шестой цифрой они быть не могут, что оставляет нам лишь 8 вариантов для цифр с шестой по восьмую:
Добьёмся теперь того, чтобы шестизначное число делилось на 6. На 2 оно уже делится, так что обеспечим делимость на 3. Для этого сумма цифр с первой по шестую должна делиться на 3. Учитывая, что сумма всех 9 цифр делится на 3, это равносильно тому, что сумма цифр с седьмой по девятую должна делиться на 3.
Например, если на седьмой и восьмой позиции мы запишем 32, то на девятой нам придётся записать либо 1, либо 7:
16 ->
32 -> 1, 7
72 -> 3, 9
96 -> 3
Учитывая, что на седьмой и восьмой позиции не может быть записано 16, для цифр с шестой по восьмую осталось только 6 вариантов:
Теперь мы знаем, что сумма цифр с первой по шестую делится на 3. В то же время, из свойств волшебного числа следует, что кроме того и сумма цифр с первой по третью делится на 3. Отсюда заключаем, что и сумма цифр с четвёртой по шестую обязана делиться на 3.
Так, например, если на шестую позицию мы ставим цифру 4, то на четвёртую на придётся поставить цифру 6 (а не 2), потому что иначе число 254 не будет делиться на 3. Соответственно, в позиции с шестой по восьмую мы уже не сможем записать 496, потому что шестёрка будет занята.
Аналогично, поставив на шестую позицию цифру 8, мы обязаны будем записать в четвёртой позиции цифру 2.
Учитывая это, для цифр с шестой по восьмую останется всего 3 варианта:
Мы учли почти все требования к волшебному числу, кроме делимости на 7. Но признак делимости на 7 настолько неудобен, что проще будет перебрать оставшиеся несколько вариантов вручную.
Например:
....5.... -> (выбираем 432) -> ....5432. -> (обязательно шестёрку на четвёртую позицию) -> ...6432. -> (восьмёрке осталась только вторая) -> .8.6432. -> (последняя цифра 1 или 7)
---> .8.54321 -> 987654321 или 789654321
---> .8.54327 -> 189654327 или 981654327
Легко видеть, что ни одно из четырёх полученных чисел не является волшебным: нам достаточно проверить только делимость семи первых цифр на 7.
Следующая ветвь:
....5.... -> (выбираем 472) -> ....5472. -> (обязательно шестёрку на четвёртую позицию) -> ...65472. -> (восьмёрке осталась только вторая) -> .8.65472 -> (последняя цифра 3 или 9)
---> .8.654723 -> 189654723 или 981654723
---> .8.654729 -> 183654729 или 381654729
Здесь из четырёх полученных чисел одно является волшебным: 381654729, потому что 3816547 делится на 7 без остатка.
Для очистки совести проверяем последнюю ветвь:
....5.... -> (выбираем 896) -> ....5698. -> (обязательно двойку на четвёртую позицию) -> ...25896. -> (четвёрке осталась только вторая) -> .4.25896. -> (девятой может быть только тройка) -> .4.258963 -> 147258693 или 741258693
Здесь семизначные числа снова на делятся на 7.
Таким образом, мы нашли единственное волшебное число: 381654729
1. В нём содержатся по одному разу все цифры от 1 до 9 (т.е. все цифры кроме нуля).
2. Само волшебное число делится на 9. Если из него вычеркнуть последнюю цифру, то оставшееся восьмизначное число будет делиться на 8. Если из волшебного числа вычеркнуть последние две цифры, то оставшееся семизначное число будет делиться на 7. И так далее: вычёркивая из волшебного числа n последних цифр, мы будем получать число, которое делится на 9-n.
К примеру, если бы число 123456789 являлось волшебным (оно им не является), то число 12345678 делилось бы на 8, 1234567 делилось бы на 7, 123456 делилось бы на 6 и так далее.
Найдите это волшебное число (оно единственное).
Разумеется, эту задачу можно решить тупым перебором на компьютере. Однако, пользуясь знакомыми с детского садика признаками делимости, задачу можно решить и на бумаге, сократив пространство перебора до десятка вариантов.
Решение
Самый простой признак делимости - признак делимости на 5. Для того, чтобы число делилось на 5, оно должно заканчиваться либо на 5, либо на 0. Нуля в волшебном числе быть не может, поэтому пятая цифра может быть только пятёркой.
Наше волшебное число теперь выглядит так: ....5....
Следующий простой признак - признак делимости на 2. Из него мы заключаем, что в позициях 2, 4, 6 и 8 могут быть только чётные цифры (т.е. те же 2, 4, 6, 8), потому что иначе восьмизначное число заведомо не будет делится на 8, шестизначное на 6, четырёхзначное на 4, двухзначное на 2.
Давайте попробуем подобрать цифры на позиции 3 и 4. Мы знаем, что четырёхзначное число должно делиться на 4. Следовательно, по признаку делимости, число, образованное третьей и четвёртой цифрой, должно делиться на 4. Вспоминая, что на четвёртой позиции может быть только чётная цифра, а на третьей - только нечётная, получим следующие варианты:
| 12, | 72 |
| 16, | 76 |
| 32, | 92 |
| 36, | 96 |
Теперь посмотрим, что может стоять на позициях 6, 7 и 8. Восьмизначное число должно делиться на 8, поэтому число, образованное этими тремя цифрами тоже должно делиться на 8:
| 216, | 416, | 632, | 816 |
| 296, | 432, | 672, | 832 |
| 472, | 872 | ||
| 496, | 896 |
Здесь мы учли, что цифры не могут повторяться, а также то, что пятёрка уже занята.
Обратите внимание, что и четвёртая, и восьмая цифра волшебного числа могут быть либо 2, либо 6. Получается, что, например, шестой цифрой они быть не могут, что оставляет нам лишь 8 вариантов для цифр с шестой по восьмую:
| 416, | 816 |
| 432, | 832 |
| 472, | 872 |
| 496, | 896 |
Добьёмся теперь того, чтобы шестизначное число делилось на 6. На 2 оно уже делится, так что обеспечим делимость на 3. Для этого сумма цифр с первой по шестую должна делиться на 3. Учитывая, что сумма всех 9 цифр делится на 3, это равносильно тому, что сумма цифр с седьмой по девятую должна делиться на 3.
Например, если на седьмой и восьмой позиции мы запишем 32, то на девятой нам придётся записать либо 1, либо 7:
16 ->
32 -> 1, 7
72 -> 3, 9
96 -> 3
Учитывая, что на седьмой и восьмой позиции не может быть записано 16, для цифр с шестой по восьмую осталось только 6 вариантов:
| 432, | 832 |
| 472, | 872 |
| 496, | 896 |
Теперь мы знаем, что сумма цифр с первой по шестую делится на 3. В то же время, из свойств волшебного числа следует, что кроме того и сумма цифр с первой по третью делится на 3. Отсюда заключаем, что и сумма цифр с четвёртой по шестую обязана делиться на 3.
Так, например, если на шестую позицию мы ставим цифру 4, то на четвёртую на придётся поставить цифру 6 (а не 2), потому что иначе число 254 не будет делиться на 3. Соответственно, в позиции с шестой по восьмую мы уже не сможем записать 496, потому что шестёрка будет занята.
Аналогично, поставив на шестую позицию цифру 8, мы обязаны будем записать в четвёртой позиции цифру 2.
Учитывая это, для цифр с шестой по восьмую останется всего 3 варианта:
| 432, | 896 |
| 472 |
Мы учли почти все требования к волшебному числу, кроме делимости на 7. Но признак делимости на 7 настолько неудобен, что проще будет перебрать оставшиеся несколько вариантов вручную.
Например:
....5.... -> (выбираем 432) -> ....5432. -> (обязательно шестёрку на четвёртую позицию) -> ...6432. -> (восьмёрке осталась только вторая) -> .8.6432. -> (последняя цифра 1 или 7)
---> .8.54321 -> 987654321 или 789654321
---> .8.54327 -> 189654327 или 981654327
Легко видеть, что ни одно из четырёх полученных чисел не является волшебным: нам достаточно проверить только делимость семи первых цифр на 7.
Следующая ветвь:
....5.... -> (выбираем 472) -> ....5472. -> (обязательно шестёрку на четвёртую позицию) -> ...65472. -> (восьмёрке осталась только вторая) -> .8.65472 -> (последняя цифра 3 или 9)
---> .8.654723 -> 189654723 или 981654723
---> .8.654729 -> 183654729 или 381654729
Здесь из четырёх полученных чисел одно является волшебным: 381654729, потому что 3816547 делится на 7 без остатка.
Для очистки совести проверяем последнюю ветвь:
....5.... -> (выбираем 896) -> ....5698. -> (обязательно двойку на четвёртую позицию) -> ...25896. -> (четвёрке осталась только вторая) -> .4.25896. -> (девятой может быть только тройка) -> .4.258963 -> 147258693 или 741258693
Здесь семизначные числа снова на делятся на 7.
Таким образом, мы нашли единственное волшебное число: 381654729
Комментариев нет:
Отправить комментарий