Выбрано 3 задачи 
Убрать все задачи
Капитан Врунгель в своей каюте разложил перетасованную колоду из 52 карт по кругу, оставив одно место свободным. Матрос Фукс с палубы, не отходя от штурвала и не зная начальной раскладки, называет карту. Если эта карта лежит рядом со свободным местом, Врунгель её туда передвигает, не сообщая Фуксу. Иначе ничего не происходит. Потом Фукс называет ещё одну карту, и так сколько угодно раз, пока сам не скажет "стоп". Может ли Фукс добиться того, чтобы после "стопа" каждая карта наверняка оказалась не там, где была вначале?
Двое игроков по очереди выставляют на доску 65×65 по одной шашке. При этом ни в одной линии (горизонтали или вертикали) не должно быть больше двух шашек. Кто не может сделать ход – проиграл. Кто выигрывает при правильной игре?
Назовём натуральное число хорошим, если все его цифры ненулевые. Хорошее число назовём особым, если в нём хотя бы k разрядов и цифры идут в порядке строгого возрастания (слева направо).
Пусть имеется некое хорошее число. За ход разрешается приписать с любого края или вписать между любыми его двумя цифрами особое число или же, наоборот, стереть в его записи особое число. При каком наибольшем k можно из каждого хорошего числа получить любое другое хорошее число с помощью таких ходов?
|
|
 |
Условие
Назовём натуральное число хорошим, если все его цифры ненулевые. Хорошее число назовём особым, если в нём хотя бы k разрядов и цифры идут в порядке строгого возрастания (слева направо).
Пусть имеется некое хорошее число. За ход разрешается приписать с любого края или вписать между любыми его двумя цифрами особое число или же, наоборот, стереть в его записи особое число. При каком наибольшем k можно из каждого хорошего числа получить любое другое хорошее число с помощью таких ходов?
Решение
Очевидно, в особом числе не более девяти цифр. Если k = 9, то при каждой операции число цифр меняется ровно на 9, то есть остаток от деления на 9 числа его цифр не меняется, и из однозначного числа нельзя сделать двузначное.
Пусть k = 8. Поскольку все операции обратимы, то достаточно доказать, что можно вставить любую цифру. Докажем индукцией по n, что можно вставить цифру n.
База. Чтобы вставить 1, вставим сначала 123456789, а затем вычеркнем 23456789.
Шаг индукции. Пусть мы умеем вставлять (и вычёркивать) цифры от 1 до n – 1 < 9. Чтобы вставить n, вставим сначала 123456789, сотрём 12...(n–1) по одной цифре, затем по одной цифре вставим 12...(n–1) справа от n и наконец вычеркнем число 12...(n–1)(n+1)...9 (при n = 9 последние два действия не нужны, а при n = 8 вычёркивается число 12...79).
Ответ
При k = 8.
