Выбрано 4 задачи 
Убрать все задачи
Капитан Врунгель в своей каюте разложил перетасованную колоду из 52 карт по кругу, оставив одно место свободным. Матрос Фукс с палубы, не отходя от штурвала и не зная начальной раскладки, называет карту. Если эта карта лежит рядом со свободным местом, Врунгель её туда передвигает, не сообщая Фуксу. Иначе ничего не происходит. Потом Фукс называет ещё одну карту, и так сколько угодно раз, пока сам не скажет "стоп". Может ли Фукс добиться того, чтобы после "стопа" каждая карта наверняка оказалась не там, где была вначале?
Двое игроков по очереди выставляют на доску 65×65 по одной шашке. При этом ни в одной линии (горизонтали или вертикали) не должно быть больше двух шашек. Кто не может сделать ход – проиграл. Кто выигрывает при правильной игре?
Назовём натуральное число хорошим, если все его цифры ненулевые. Хорошее число назовём особым, если в нём хотя бы k разрядов и цифры идут в порядке строгого возрастания (слева направо).
Пусть имеется некое хорошее число. За ход разрешается приписать с любого края или вписать между любыми его двумя цифрами особое число или же, наоборот, стереть в его записи особое число. При каком наибольшем k можно из каждого хорошего числа получить любое другое хорошее число с помощью таких ходов?
Существует ли натуральное число, делящееся на 1998, сумма цифр которого меньше 27?
|
|
 |
Условие
Существует ли натуральное число, делящееся на 1998, сумма цифр которого меньше 27?
Решение
Если число делится на 1998, то оно делится и на 999. Мы покажем, что не существует числа, делящегося на 999, сумма цифр которого меньше чем 27.
Разобьем десятичную запись числа на группы по три цифры справа налево
(последняя группа может состоять из одной или двух цифр). Сложим эти группы.
Исходное число делится на 999 тогда и только тогда, когда полученная сумма
делится на 999 (см. решение задачи 78550).
Рассмотрим число, делящееся на 999, разобьём его на тройки цифр и вычислим сумму этих троек. Если новое число больше 1000, то снова разобьём его на тройки цифр и вычислим сумму, и так далее, пока не получим число, меньшее
1000. Это случится, поскольку число уменьшается при каждой операции.
Действительно, если a1, ..., ak
– неотрицательные целые числа, ak ≠ 0 и k ≥ 1, то a0 + 1000a1 + ... + 1000kak > a0 + a1 + ... + ak.
Итак, после нескольких операций мы получим положительное число, меньшее 1000, делящееся на 999, следовательно, оно будет равно 999.
Сумма цифр числа 999 равна 27. Достаточно доказать, что при наших операциях сумма цифр не увеличивается. Когда мы разрезаем число на тройки цифр, сумма цифр не меняется. Покажем, что при сложении сумма цифр не увеличивается. Действительно, обозначим через S(X) сумму цифр числа X. Из алгоритма сложения в столбик видно, что S(X +Y) = S(X) + S(Y) – 9P(X, Y), где P(X, Y) — число переносов при сложении X и Y в столбик. Значит,
S(X + Y) ≤ S(X) + S(Y).
