Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2001/04/25.pdf Дата изменения: Fri Dec 23 19:26:28 2005 Дата индексирования: Tue Oct 2 00:12:06 2012 Кодировка: Windows-1251 Поисковые слова: m 2

ЗАДАЧНИК

'КВАНТА'

25

Учитывая, что 2 + = - , имеем: AB A1C 2 . Завершаем доказательство: o 180 = + + 2 + 2 + = 5 36 o . А.Эвнин

Доказанные здесь утверждения принадлежат к тем фактам, которые просто доказать, но непросто обнаружить. В.Произволов

1761. У фокусника 100 карточек, занумерованных

1760. Таблицу размером n Ч n клеток назовем удивительной, если она обладает следующим свойством: всякие n чисел таблицы такие, что в каждом столбце таблицы и в каждой строке таблицы присутствует ровно одно из них, дают одну и ту же сумму. Докажите, что каждая удивительная таблица может быть представлена в виде суммы двух таблиц, у одной из которых в каждом столбце все числа равны, а у другой в каждой строке все числа равны. Например, 1, 1, 1 2, 3, 0 3, 4, 1

F GG GH

6, 7, 5, 6,

I J 4J J 3K

= 2, 3, 2, 3,

F GG GH

I J 0J J 0K

+ 4, 4, 4 . 3, 3, 3

F GG GH

I JJ JK

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

Массовик-затейник вызывает на сцену простодушного добровольца и показывает ему таблицу

21, 22, 23, 24, Затем предлагает добровольцу молча выбрать из таблицы 5 чисел, по одному из каждой строки и каждого столбца, а сам, не зная этих чисел, сообщает изумленному добровольцу, чему равна их сумма. Нас это не изумляет, поскольку сумма всегда будет равна 65. Вопрос в том, как устроены удивительные таблицы. Оказывается, они устроены всегда так, как сказано в условии задачи. Докажем это. Доказательство этого примечательного факта осуществляется на удивление просто. Пусть М произвольная удивительная таблица размером n Ч n . Составим таблицу Р, у которой все строки будут одинаковыми и такими, какова первая строка у таблицы М. Затем, вычтя из таблицы М таблицу Р, получим таблицу Q, у которой в каждой строке будут стоять одинаковые числа (например, в первой только нули). Последнее следует из того, что всякие четыре числа удивительной таблицы, располагающиеся 'в вершинах прямоугольника' a,......, b ........... , c,......, d

F GG GG GG GH

1, 6, 11, 16,

2, 7, 12, 17,

3, 8, 13, 18,

4, 9, 14, 19,

I J 10J J 15J J 20J J 25K
5

.

подчиняются условию a + d = c + b. Проделав эту процедуру с примером из формулировки задачи, получаем равенство

F GG GH

3, 6, 5,

4, 7, 6,

1 3

4 - 3, 3,

I JJ JK

F GG GH

3,

4, 4, 4,

I J 1J J 1K
1

= 3, 2,

F GG GH

0,

0, 3, 2,

I J 3J J 2K
0

Ответ. 12. Пусть карточка 1 (или число 1) лежит в красном ящике (сокращенно КЯ), а карточка с наименьшим числом k, не лежащая в КЯ, лежит в белом ящике (БЯ). Тогда k 1 находится в КЯ. По условию, в синем ящике (СЯ) есть хотя бы одна карточка; пусть n наименьшее число (т.е. карточка с наименьшим числом) в СЯ 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, ..., 99. Покажем, что в этом случае фокус всегда удается: если мы берем карточки из БЯ и КЯ, то получаем суммы 3, 4, ... ..., 100, если из КЯ и СЯ сумму 101, если из БЯ и СЯ суммы 102, 103, ..., 199, т.е. суммы различны. 2) В КЯ есть другие числа, и m наименьшее из них. Тогда m > 2, значит, m 1 не лежит в КЯ. Если m 1 находятся в БЯ, то для пар m - 1, n из БЯ и СЯ и n - 1, m из БЯ и СЯ фокус не удастся. Значит, m 1 лежит в СЯ. Лемма 1. Если в двух различных ящиках лежат карточки х и х + 1, а в третьем у и у +1, то фокус не удастся. Доказательство. Одинаковые суммы имеют пары x, y + 1 и x + 1, y из разных пар ящиков. Лемма 2. Если в одном ящике лежат карточки х и у, а в двух других х + 1 и у + 1 соответственно, то фокус не удастся. Доказательство дословно повторяет доказательство леммы 1. Выше мы показали, что для каждой пары ящиков есть карточки с двумя последовательными числами, а именно

b

gb g

b

g

b

g

b

g

b

g

КЯ, БЯ : 1, 2, . БЯ, СЯ : n 1, n, СЯ, БЯ : m 1, m.

7 Квант ? 4