Задача 97969

Темы:    [ Числовые таблицы и их свойства ] [ Примеры и контрпримеры. Конструкции ] [ Индукция (прочее) ] [ Теория групп (прочее) ]

Сложность: 4+ Классы: 8,9,10

Условие

Автор: Шевелев В.С.

Прямой угол разбит на бесконечное число квадратных клеток со стороной единица. Будем рассматривать ряды клеток, параллельные сторонам угла (вертикальные и горизонтальные ряды). Можно ли в каждую клетку записать натуральное число так, чтобы каждый вертикальный и каждый горизонтальный ряд клеток содержал все натуральные числа по одному разу?

Решение 1

  Первую строку заполним числами по порядку. Каждую следующую строку заполняем слева направо по следующему правилу: в очередную клетку ставим наименьшее допустимое число (то есть не совпадающее с уже поставленными под ним и слева от него числами).
  Докажем, что число n появится в k-м столбце. Действительного, его появлению может препятствовать только то, что во всех строчках, кроме тех, где в этом столбце стоят меньшие числа, n встречается левее k-го места. Но это невозможно: в первых  k – 1  столбцах n встречается не более  k – 1  раз. Ситуация со строками аналогична.

Решение 2

  Для знатоков. Введём на N операцию ⊕, превращающую N в группу (например, осуществив биекцию с Z). В клетку с "координатами"  (a, b)  поместим число  a ⊕ b.

Ответ

Можно.

Замечания

  1. Распределение чисел, соответствующее решению 1, можно описать и явно. Обозначим через K₀ квадрат 1×1, в который вписана единица. Индуктивно будем увеличивать его: квадрат K_n+1 размера 2ⁿ⁺¹×2ⁿ⁺¹ получается из K_n добавлением еще трёх квадратов (см. рис.). В каждом ряде клеток квадрата K_n содержатся все числа от 1 до 2ⁿ. Объединение всех этих квадратов даёт искомую конструкцию.
  Ту же конструкцию (в ней удобнее вместо N рассмотреть множество неотрицательных целых чисел) можно получить и из решения 2: заменим числа на их двоичные разложения и отождествим их с элементами
Z₂ ⊕ Z₂ ⊕ ...

  2. Баллы: 7-8 кл – 8, 9-10 кл. – 5.

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1988
выпуск
Номер	9
Задача
Номер	М1123
олимпиада
Название	Турнир городов
Турнир
Номер	9
Дата	1987/1988
вариант
Вариант	весенний тур, основной вариант, 9-10 класс
Задача
Номер	2
олимпиада
Название	Турнир городов
Турнир
Номер	9
Дата	1987/1988
вариант
Вариант	весенний тур, основной вариант, 7-8 класс
Задача
Номер	6