Задача 109733

Темы:    [ Доказательство от противного ] [ Примеры и контрпримеры. Конструкции ] [ Системы линейных уравнений ] [ Уравнения в целых числах ]

Сложность: 5 Классы: 9,10,11

Условие

Автор: Токарев С.И.

Участникам тестовой олимпиады было предложено n вопросов. Жюри определяет сложность каждого из вопросов: целое положительное количество баллов, получаемых участниками за правильный ответ на вопрос. За неправильный ответ начисляется 0 баллов, все набранные участником баллы суммируются. Когда все участники сдали листки со своими ответами, оказалось, что жюри так может определить сложность вопросов, чтобы места между участниками распределились любым наперед заданным образом. При каком наибольшем числе участников это могло быть?

Решение

  Докажем, что при n участниках такое распределение баллов может существовать. Пример очевиден – пусть k-й участник ответит только на один k-й вопрос. Тогда, назначив стоимость вопросов a₁, a₂, ..., a_n, где  {a₁, a₂, ..., a_n} = {1, 2, ..., n},  жюри поставит k-го участника на место n + 1 – a_k.
  Пусть участников  n + 1.  Представим себе, что мы клонировали каждого участника, то есть у нас есть неограниченное количество участников каждого из  n + 1  типов (внутри типа все отвечают на вопросы одинаково). Докажем, что можно составить из них две команды, разные по составу (хотя бы для одного типа число участников этого типа в первой команде не равно числу участников этого типа во второй команде), но имеющих одинаковые результаты (то есть на каждый вопрос в первой команде ответило столько же человек, сколько во второй).
  Действительно, запишем систему линейных уравнений, i-е уравнение которой гласит, что разность числа участников первой и второй команды, ответивших на i-й вопрос есть ноль; здесь x_j – число участников j-го типа (в первой команде, если x_j окажется положительным, во второй – если отрицательным). Коэффициенты – нули и единицы – определяются тем, ответил ли участник j-го типа на i-й вопрос. Это система из n однородных уравнений с  n + 1  неизвестным. Как известно, она имеет ненулевое решение, причём, поскольку все коэффициенты рациональны, существует рациональное ненулевое решение. Так как уравнения однородны, решение можно домножить на константу. Домножим так, чтобы значения всех x_j стали целыми. Требуемые команды найдены. При этом участники каждого типа присутствуют не более чем в одной команде.
  Пусть в первой команде участников не меньше, чем во второй. Тогда нельзя назначить баллы за вопросы так, чтобы места всех участников первой команды были выше, чем места участников второй команды, ибо сумма баллов участников первой команды всегда равна сумме баллов участников второй команды.

Ответ

При n участниках.

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

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