Выбрана 1 задача 
Убрать все задачи
В таблице m строк, n столбцов. Горизонтальным ходом называется такая перестановка элементов таблицы, при которой каждый элемент остаётся в той строке, в которой он был и до перестановки; аналогично определяется вертикальный ход ("строка" в предыдущем определении заменяется на "столбец"). Укажите такое k, что за k ходов (любых) можно получить любую перестановку элементов таблицы, но существует такая перестановка, которую нельзя получить за меньшее число ходов.
Решение
|
|
 |
Условие
По кругу записывают 2015 натуральных чисел так, чтобы каждые два соседних числа различались на их наибольший общий делитель.
Найдите наибольшее натуральное N, на которое гарантированно будет делиться произведение этих 2015 чисел.
Решение
Оценка. Два нечётных числа не могут стоять рядом, так как они не делятся на свою чётную разность. Поэтому чётных чисел не меньше половины, то есть хотя бы 1008. Так как их больше половины, то какие-то два чётных числа стоят рядом. Из этой пары чётных чисел хотя бы одно кратно 4, иначе их разность кратна 4, а сами они – нет.
Предположим, у нас нет чисел, кратных 3. Тогда, из-за нечётности количества чисел, какие-то два соседних числа дают одинаковые остатки при делении на 3. Эти числа делятся на свою разность, которая кратна 3. Противоречие.
Следовательно, N ≥ 3·21009.
Пример. Числа 4, 3, 2, 1, 2, 1, ..., 2, 1, 2 удовлетворяют условию. Их произведение равно 3·21009.
Ответ
N = 3·21009.
Замечания
1. Пример единственный.
2. 5 баллов.
