М1761. Ящики фокусника

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

Условие

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

Ответ: [latex]12.[/latex]

Решение

Пусть карточка [latex]1[/latex] (или число [latex]1[/latex]) лежит в красном ящике
(сокращенно КЯ), а карточка с наименьшим числом [latex]k,[/latex] не лежащая в КЯ, лежит в белом ящике (БЯ). Тогда [latex]k-1[/latex] находится в КЯ.
По условию, в синем ящике (СЯ) есть хотя бы одна карточка; пусть [latex]n[/latex] – наименьшее число (т.е. карточка с наименьшим числом) в СЯ [latex]\to [/latex] [latex]n > k.[/latex] Если [latex]n-1[/latex] лежит в КЯ, то зритель может вытащить либо [latex]n-1[/latex] и [latex]k[/latex] из КЯ и
БЯ, либо [latex]n[/latex] и [latex]k-1[/latex] из СЯ и КЯ. Суммы чисел на карточках одинаковы, значит, в этом случае фокус не удастся.
Следовательно, [latex]n-1[/latex] находится в БЯ. Предположим, что карточка [latex]2[/latex] лежит в КЯ. Тогда взяв либо [latex]2[/latex] и [latex]n-1[/latex] из КЯ и БЯ, либо [latex]1[/latex] и [latex]n[/latex] из КЯ и СЯ, получим одинаковые суммы, значит, [latex]k=2[/latex] и [latex]2[/latex] находится в БЯ.
Рассмотрим два случая.

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

Лемма 1

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

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

Лемма 2

Если в одном ящике лежат карточки [latex]x[/latex] и [latex]y,[/latex] а в
двух других [latex]x+1[/latex] и [latex]y+1[/latex] соответственно, то фокус не удастся.

Доказательство дословно повторяет доказательство леммы [latex]1.[/latex]

Выше мы показали, что для каждой пары ящиков есть карточки с двумя последовательными числами, а именно
КЯ, БЯ : [latex]1,2,[/latex]
БЯ, СЯ : [latex]n-1, n,[/latex]
СЯ, БЯ : [latex]m — 1, m.[/latex]
Значит, по лемме [latex]1[/latex] ни в одном из ящиков нет карточек с двумя последовательными числами.
Далее, полагая, что [latex]y = 1,[/latex] если [latex]x[/latex] лежит в КЯ и [latex]x + 1[/latex] – в
СЯ, и [latex]y = n — 1,[/latex] если [latex]x[/latex] находится в БЯ и [latex]x + 1[/latex] – в КЯ,
по лемме [latex]2[/latex] получаем, что в этих случаях фокус не удастся.
Аналогично фокус не удастся, если [latex]x[/latex] лежит в СЯ, а [latex]x + 1[/latex] в БЯ. Итак, если а находится в КЯ, то [latex]a + 1[/latex] – в БЯ, [latex]a + 2[/latex] – в СЯ, [latex]a + 3[/latex] – в БЯ и т.д. Значит, в КЯ находятся числа, сравнимые с [latex]1[/latex] по модулю [latex]3[/latex], в БЯ – сравнимые с [latex]2,[/latex] в СЯ – делящиеся на [latex]3.[/latex] Покажем, что такое расположение карточек подходит: сумма чисел на карточках из КЯ и БЯ делится на [latex]3,[/latex] из КЯ и СЯ сравнима с [latex]1[/latex] по модулю 3, из СЯ и БЯ – с [latex]2,[/latex] т.е. всегда можно определить, из каких ящиков взяты карточки.
Мы получили, что если карточка [latex]1[/latex] лежит в КЯ, а карточка с наименьшим числом не из КЯ находится в БЯ, то есть два варианта раскладывания карточек. Аналогично рассуждаем в случае других пяти пар ящиков. Значит, всего имеется [latex]2 \times 3 \times 2 = 12[/latex] различных способов.

Н. Агаханов, А. Гайфуллин

М1761. Ящики фокусника: 1 комментарий

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

Добавить комментарий для Artem Отменить ответ

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