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

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

Условие

Автор: Чувилин К.

Дана таблица n×n, столбцы которой пронумерованы числами от 1 до n. В клетки таблицы расставляются числа 1, ..., n  так, что в каждой строке и в каждом столбце все числа различны. Назовём клетку хорошей, если число в ней больше номера столбца, в котором она находится. При каких n существует расстановка, в которой во всех строках одинаковое количество хороших клеток?


Решение

  Найдём общее количество хороших клеток. В первом столбце их  n – 1  (все, кроме клетки с числом 1), во втором –  n – 2  (все, кроме клеток с числами 1 и 2) и т. д., в последнем столбце таких клеток нет. Значит, всего их  (n – 1) + (n – 2) + ... + 1 = ½ n(n – 1).   Поэтому в каждой строке их должно быть по n–1/2. Следовательно, n нечётно.
  Приведём пример расстановки для  n = 2k + 1.


  В каждой строке стоит циклическая перестановка ряда  2k + 1,  2k, ..., 1.  При этом, как нетрудно видеть, в 2i-й строке хорошими будут первая  i – 1 клетка и клетки с 2i-й по (k+i)-ю, а в (2i–1)-й строке – первая  i – 1  клетка и клетки с (2i–1)-й по (k+i–1)-ю. Таким образом, в каждой строке ровно k хороших клеток.


Ответ

При нечётных n.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2008
Этап
Вариант 5
Класс
Класс 10
задача
Номер 08.5.10.2

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

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