|
|
 |
Условие
Прямой угол разбит на бесконечное число квадратных клеток со стороной единица. Будем рассматривать ряды клеток, параллельные сторонам угла (вертикальные и горизонтальные ряды). Можно ли в каждую клетку записать натуральное число так, чтобы каждый вертикальный и каждый горизонтальный ряд клеток содержал все натуральные числа по одному разу?
Решение 1
Первую строку заполним числами по порядку. Каждую следующую строку заполняем слева направо по следующему правилу: в очередную клетку ставим наименьшее допустимое число (то есть не совпадающее с уже поставленными под ним и слева от него числами).
Докажем, что число n появится в k-м столбце. Действительного, его появлению может препятствовать только то, что во всех строчках, кроме тех, где в этом столбце стоят меньшие числа, n встречается левее k-го места. Но это невозможно: в первых k – 1 столбцах n встречается не более k – 1 раз. Ситуация со строками аналогична.
Решение 2
Для знатоков. Введём на N операцию ⊕, превращающую N в группу (например, осуществив биекцию с Z). В клетку с "координатами" (a, b) поместим число a ⊕ b.
Ответ
Можно.
Замечания
1. Распределение чисел, соответствующее решению 1, можно описать и явно. Обозначим через K0 квадрат 1×1, в который вписана единица. Индуктивно будем увеличивать его: квадрат Kn+1 размера 2n+1×2n+1 получается из Kn добавлением еще трёх квадратов (см. рис.). В каждом ряде клеток квадрата Kn содержатся все числа от 1 до 2n. Объединение всех этих квадратов даёт искомую конструкцию.
Ту же конструкцию (в ней удобнее вместо N рассмотреть множество неотрицательных целых чисел) можно получить и из решения 2: заменим числа на их двоичные разложения и отождествим их с элементами
Z2 ⊕ Z2 ⊕ ...
2. Баллы: 7-8 кл – 8, 9-10 кл. – 5.
Источники и прецеденты использования
| журнал | |
| Название | "Квант" |
| год | |
| Год | 1988 |
| выпуск | |
| Номер | 9 |
| Задача | |
| Номер | М1123 |
| олимпиада | |
| Название | Турнир городов |
| Турнир | |
| Номер | 9 |
| Дата | 1987/1988 |
| вариант | |
| Вариант | весенний тур, основной вариант, 9-10 класс |
| Задача | |
| Номер | 2 |
| олимпиада | |
| Название | Турнир городов |
| Турнир | |
| Номер | 9 |
| Дата | 1987/1988 |
| вариант | |
| Вариант | весенний тур, основной вариант, 7-8 класс |
| Задача | |
| Номер | 6 |
