Страница: << 1 2 3 4 5 [Всего задач: 23]      

В ряд слева направо стоят $N$ коробок, занумерованных подряд числами $1$, $2, \ldots, N$. В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми. Инструкция состоит из последовательно выполняемых команд вида «поменять местами содержимое коробок № $i$ и № $j$», где $i$ и $j$ – числа. Для каждого ли $N$ существует инструкция, в которой не больше $100N$ команд, со свойством: для любой начальной раскладки указанного вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее коробок без шариков?

Прислать комментарий

Решение

Клетчатая полоска 1×1000000 разбита на 100 сегментов. В каждой клетке записано целое число, причём в клетках, лежащих в одном сегменте, числа совпадают. В каждую клетку поставили по фишке. Затем сделали такую операцию: все фишки одновременно передвинули, каждую – на то количество клеток вправо, которое указано в её клетке (если число отрицательно, то фишка двигается влево); при этом оказалось, что в каждую клетку снова попало по фишке. Эту операцию повторяют много раз. Для каждой фишки первого сегмента подсчитали, через сколько операций она впервые снова окажется в этом сегменте. Докажите, что среди полученных чисел не более 100 различных.

Прислать комментарий

Решение

Глеб задумал натуральные числа $N$ и $a$, $a < N$. Число $a$ он написал на доске. Затем он начал выполнять следующую операцию: делить $N$ с остатком на последнее выписанное на доску число, а полученный остаток от деления также записывать на доску. Когда на доске появилось число $0$, он остановился. Мог ли Глеб изначально выбрать такие $N$ и $a$, чтобы сумма выписанных чисел была больше $100 N$?

Прислать комментарий

Решение

Страница: << 1 2 3 4 5 [Всего задач: 23]