358
470
всего разделов:
активных пользователей:
30 мартра 2005
Форумы снова функционируют.
21 декабря 2004
Видимо в связи с обнаруженными дырами в phpBB, форум был взломан, а через него взломано и всё остальное содержимое ceemat.ru. Всё кроме форума восстановлено, ведется дискуссия по поводу его сохранения.
Приносим извинения за неудобства.
29 сентября 2004
Форум обновился до версии 2.0.10
15 мая 2004
Новый раздел: "Программирование"
16 апреля 2004 года
Задачи Ярославского турнира математических боев — 124 задачи с решениями.
29 марта 2004
Таллинская викторина: занимательные вопросы и задачи для увлеченных химией.
Высшая лига и лига 9 классов (8)
В ряд выписаны числа от 1 до 50 в некотором порядке. Разрешается менять местами два числа, если разность номеров их позиций равна наибольшему общему делителю этих чисел. Можно ли такими операциями получить произвольное расположение чисел? |
Ответ: можно. Докажем, что число x можно переместить на любое место, сохранив при этом порядок остальных чисел. Для этого достаточно показать, что его можно поменять местами с соседним числом (назовем его y, НОД (x, y) = k). Покажем, как это сделать. Проведем индукцию по k. Число 1 можно перемещать куда угодно. Пусть любую пару чисел, НОД которых меньше k, можно поменять местами, не меняя порядок остальных чисел. Если k = 1, то числа x и y можно сразу поменять местами. Если k > 1, то в пространство между числами x и y поместим k – 1 чисел, меньших k (для них выполнено предположение индукции). После этого поменяем местами числа х и y, а перемещенные k – 1 чисел вернем на прежние места. |
Автор: А. Чеботарев. |
28 Февраля 2004 22:52 Раздел каталога :: Ссылка на задачу
|