ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97969
Темы:    [ Числовые таблицы и их свойства ]
[ Примеры и контрпримеры. Конструкции ]
[ Индукция (прочее) ]
[ Теория групп (прочее) ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение 1

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


Решение 2

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


Ответ

Можно.

Замечания

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

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

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

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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .