Задача из журнала «Квант» (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 год, 1 выпуск) М1761: 1 комментарий

  1. Доказательство неполное. Ничего не сказано про то, как подсчитали число способов, чтобы получить ответ 12.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *