Задача из журнала «Квант» (2001 год, 1 выпуск) М1761

Условие

У фокусника 100 карточек, занумерованных
числами от 1 до 100. Он раскладывает все карточки в три
ящика – красный, белый и синий – так, чтобы в каждом
ящике лежала хотя бы одна карточка.
Один из зрителей выбирает два из трех ящиков, вынима-
ет из них по одной карточке и объявляет сумму номеров
вынутых карточек. Зная эту сумму, фокусник определя-
ет тот ящик, из которого карточки не вынимались.
Сколькими различными способами можно разложить кар-
точки по ящикам так, чтобы этот фокус всегда удавался?
(Способы, при которых хотя бы одна карточка попадает
в разные ящики, считаются различными.)

Ответ: 12.

Решение

Пусть карточка 1 (или число 1) лежит в красном ящике
(сокращенно КЯ), а карточка с наименьшим числом k, не
лежащая в КЯ, лежит в белом ящике (БЯ). Тогда k-1
находится в КЯ.
По условию, в синем ящике (СЯ) есть хотя бы одна
карточка; пусть n – наименьшее число (т.е. карточка с
наименьшим числом) в СЯ \to  n > k . Если n-1 лежит в
КЯ, то зритель может вытащить либо n-1 и k из КЯ и
БЯ, либо n и k-1 из СЯ и КЯ. Суммы чисел на карточках
одинаковы, значит, в этом случае фокус не удастся.
Следовательно, n-1 находится в БЯ.
Предположим, что карточка 2 лежит в КЯ. Тогда взяв
либо 2 и n-1 из КЯ и БЯ, либо 1 и n из КЯ и СЯ, получим
одинаковые суммы, значит, k=2 и 2 находится в БЯ.
Рассмотрим два случая.
1) В КЯ нет других карточек, кроме 1. Покажем, что тогда
n=100. Пусть n<100. Тогда n+1 лежит либо в БЯ, либо в СЯ. Пары карточек (1, n+1) и (2, n) с одинаковой суммой находятся в (КЯ, БЯ (СЯ)) и в (БЯ, СЯ) – фокус не удался. Значит,n=100, т.е. в СЯ только одна карточка 100, в КЯ – одна карточка 1, в БЯ – карточки 2, 3, \ldots , 99. Покажем, что в этом случае фокус всегда удается: если мы берем карточки из БЯ и КЯ, то получаем суммы 3, 4, \cdots ,100, если из КЯ и СЯ – сумму 101, если из БЯ и СЯ – суммы 102, 103, \cdots , 199, т.е. суммы различны.

2) В КЯ есть другие числа, и m – наименьшее из них. Тогда m > 2, значит, m-1не лежит в КЯ. Если m-1
находятся в БЯ, то для пар (m-1, n), из БЯ и СЯ и (n-1, m), из БЯ и СЯ фокус не удастся. Значит, m-1 лежит в СЯ.

Лемма 1

Если в двух различных ящиках лежат карточки
x и x+1, а в третьем y и y+1, то фокус не удастся.

Доказательство

Одинаковые суммы имеют пары (x, y + 1)
и (x+1, y), из разных пар ящиков.

Лемма 2

Если в одном ящике лежат карточки x и y, а в
двух других x+1 и y+1 соответственно, то фокус не
удастся.
Доказательство дословно повторяет доказательство лем-
мы 1.
Выше мы показали, что для каждой пары ящиков есть
карточки с двумя последовательными числами, а именно
КЯ, БЯ : 1,2,
БЯ, СЯ : n-1, n,
СЯ, БЯ : m - 1, m.

Задача из журнала «Квант» (2001 год, 2 выпуск) М1769

Условие

 

Концы 2n пересекающихся хорд разделили окружность на 4n равных дуг. Докажите, что среди этих хорд найдутся две параллельные хорды.

Решение

Будем считать, что окружность имеет длину 4n, а, значит каждая из 4n дуг, на которые она разделена концами 2n непересекающихся хорд, имеет длину 1. Важно заметить следующее. Так как хорды не пересекаются, то концы каждой хорды разделяют окружность на дуги нечетной длины.

Обозначим 4n точек деления числами 0, 1, 2, \ldots,4n - 1 последовательно (см. рисунок). Условимся писать  a \equiv b, если числа a и b дают одинаковые остатки при делении на 4n, и говорить, что a и b равны по модулю 4n. Теперь отметим, что если i, j и k, l — две пары из чисел на окружности, для которых выполняется равенство i + j \equiv k + l, то хорды ij и kl параллельны.

Каждая из 2n хорд определена парой своих концов: (i_1, i_2),  (i_3, i_4), \ldots, (i_{4n-1}, i_4n). При этом сумма чисел в каждой паре нечетна.

Допустим, что среди 2n хорд нет параллельных. Тогда набор чисел i_1 + i_2i_3 + i_4, \ldots, i_{4n-1} + i_4n по модулю 4n содержит все нечетные числа от 1 до 4n - 1.

Значит, сумма этого набора равна 4n^2 (по модулю 4n). Непосредственно суммируя числа набора, мы получим i_1 + i_2 + i_3 + i_4 + \ldots + i_{4n-1} + i_4n = 0 + 1 + 2 + \ldots +4n- 1 = 2n (4n-1).

Но тогда должно выполняться равенство 4n^2 \equiv 2n (4n-1).  Легко видеть, что такое равенство не выполняется, т.е. остается заключить, что среди хорд есть параллельные.

BПроизволов