Разделы 
Дополнительно
Задача по математике - 1962
2019-01-22 
Участникам тестовой олимпиады было предложено $n$ вопросов. Жюри определяет сложность каждого из вопросов: целое положительное количество баллов, получаемых участниками за правильный ответ на вопрос. За неправильный ответ начисляется 0 баллов, все набранные участником баллы суммируются. Когда все участники сдали листки со своими ответами, оказалось, что жюри так может определить сложность вопросов, чтобы места между участниками распределились любым наперед заданным образом. При каком наибольшем числе участников это могло быть?
Решение:
Докажем, что при $n$ участниках такое распределение баллов может существовать. Пример очевиден - пусть $k$-й участник ответит только на один $k$-й вопрос. Тогда, назначив стоимость вопросов $a_1, a_2, \cdots, a_n,$ где $\{ a_1, a_2, \cdots, a_n \} = \{1, 2, \cdots, n \}$, жюри поставит $k$-го участника на место $n + 1 - a_k$.
Теперь докажем от противного, что не могло быть $n + 1$ участников или более. Представим себе, что мы клонировали каждого участника, т. е. у нас есть неограниченное количество участников каждого из $n +1$ типов. Докажем, что если мы сможем составить из них две команды, разные по составу (хотя бы для одного типа число участников этого типа в первой команде не равно числу участников этого типа во второй команде), но имеющих одинаковые результаты (т. е. на каждый вопрос в первой команде ответило столько же человек, сколько во второй), то мы придем к противоречию.
Во-первых, можно считать, что участники каждого типа присутствуют не более, чем в одной команде: если в обеих командах есть по участнику одного типа, удалим их, составы команд останутся разными, а результаты - одинаковыми.
Пусть, без ограничения общности, в первой команде участников не меньше, чем во второй. Тогда нельзя назначить баллы за вопросы так, чтобы места всех участников первой команды были выше, чем места участников второй команды, ибо сумма баллов участников первой команды всегда равна сумме баллов участников второй команды.
Осталось доказать, что такие две команды найдутся. Для этого запишем систему линейных уравнений, $i$-е уравнение которой гласит, что разность числа участников первой и второй команды, ответивших на $i$-й вопрос есть ноль; $j$-й переменной здесь будет число участников $j$-го типа в команде (в первой, если переменная положительна, во второй, - если отрицательна). Это система из $n$ однородных уравнений с $n + 1$ переменной. Как известно, она имеет ненулевое решение, причем, поскольку все коэффициенты рациональны (а они нули или единицы), существует рациональное ненулевое решение. Поскольку уравнения однородны, решение можно домножить на константу. Домножим так, чтобы значения всех переменных стали целыми. Требуемые команды найдены.
Ответ. При $n$ участниках.
Участникам тестовой олимпиады было предложено $n$ вопросов. Жюри определяет сложность каждого из вопросов: целое положительное количество баллов, получаемых участниками за правильный ответ на вопрос. За неправильный ответ начисляется 0 баллов, все набранные участником баллы суммируются. Когда все участники сдали листки со своими ответами, оказалось, что жюри так может определить сложность вопросов, чтобы места между участниками распределились любым наперед заданным образом. При каком наибольшем числе участников это могло быть?
Решение:
Докажем, что при $n$ участниках такое распределение баллов может существовать. Пример очевиден - пусть $k$-й участник ответит только на один $k$-й вопрос. Тогда, назначив стоимость вопросов $a_1, a_2, \cdots, a_n,$ где $\{ a_1, a_2, \cdots, a_n \} = \{1, 2, \cdots, n \}$, жюри поставит $k$-го участника на место $n + 1 - a_k$.
Теперь докажем от противного, что не могло быть $n + 1$ участников или более. Представим себе, что мы клонировали каждого участника, т. е. у нас есть неограниченное количество участников каждого из $n +1$ типов. Докажем, что если мы сможем составить из них две команды, разные по составу (хотя бы для одного типа число участников этого типа в первой команде не равно числу участников этого типа во второй команде), но имеющих одинаковые результаты (т. е. на каждый вопрос в первой команде ответило столько же человек, сколько во второй), то мы придем к противоречию.
Во-первых, можно считать, что участники каждого типа присутствуют не более, чем в одной команде: если в обеих командах есть по участнику одного типа, удалим их, составы команд останутся разными, а результаты - одинаковыми.
Пусть, без ограничения общности, в первой команде участников не меньше, чем во второй. Тогда нельзя назначить баллы за вопросы так, чтобы места всех участников первой команды были выше, чем места участников второй команды, ибо сумма баллов участников первой команды всегда равна сумме баллов участников второй команды.
Осталось доказать, что такие две команды найдутся. Для этого запишем систему линейных уравнений, $i$-е уравнение которой гласит, что разность числа участников первой и второй команды, ответивших на $i$-й вопрос есть ноль; $j$-й переменной здесь будет число участников $j$-го типа в команде (в первой, если переменная положительна, во второй, - если отрицательна). Это система из $n$ однородных уравнений с $n + 1$ переменной. Как известно, она имеет ненулевое решение, причем, поскольку все коэффициенты рациональны (а они нули или единицы), существует рациональное ненулевое решение. Поскольку уравнения однородны, решение можно домножить на константу. Домножим так, чтобы значения всех переменных стали целыми. Требуемые команды найдены.
Ответ. При $n$ участниках.
