Холщовый мешок
Соединённые Штаты являются для всего мира совестью
О беспорядочном порядке

Иногда в условиях задач можно увидеть словосочетания в некотором порядке, в каком-то порядке.

Например, задача 10.4 регионального этапа:
По кругу стоят `10^{1000}` натуральных чисел. Между каждыми двумя соседними числами записали их наименьшее общее кратное. Могут ли эти наименьшие общие кратные образовать `10^{1000}` последовательных чисел (расположенных в каком-то порядке)?
Решение:
Пусть `n = 10^1000`. Обозначим исходные числа (в порядке обхода) через `a_1, ..., a_n`; мы будем считать, что `a_{n+1} = a_1`. Положим `b_i = (a_i, a_{i+1})`. Предположим что `b_1, ..., b_n` – это `n` подряд идущих натуральных чисел.
Рассмотрим наибольшую степень двойки `2^m`, на которую делится хотя бы одно из чисел `a_i`. Заметим, что ни одно из чисел `b_1, ..., b_n` не делится на `2^{m+1}`. Пусть для определённости `a_1` делится на `2^m`; тогда `b_1` и `b_n` кратны `2^m`: `b_1 = 2^m x`, `b_n = 2^m y` при некоторых нечётных `x` и `y`. Без ограничения общности можно считать, что `x < y`. Тогда среди `n` последовательных чисел `b_1, ..., b_n` должно быть и число `2^m(x + 1)` (поскольку `2^m x < 2^m(x + 1) < 2^m y`). Но это число делится на `2^{m+1}` (так как `x + 1` чётно), что невозможно. Противоречие.

Иногда предположение об упорядоченном порядке приводит к плачевным результатам. Излишне эмоциональный комментарий к этой задаче можно посмотреть на youtube

@темы: Головоломки и занимательные задачи