Стройка
В городе группа приглашённых экспертов выбирала место для строительства здания филиала Национальной школы экономики. Процедура была следующая: каждый из экспертов мог распределить ровно баллов между четырьмя местами: на берегу реки , на возвышенности , в жилом квартале или в промышленной зоне . Чтобы меньше возникало неоднозначных результатов, каждый из экспертов мог ставить предполагаемым местам строительства , , и только попарно различное (т. е. все четыре числа должны быть различными) целое неотрицательное количество баллов. Побеждало место, набравшее наибольшее суммарное количество баллов.
После подведения итогов выяснилось, что победило место у реки, а меньше всех набрало место в промышленной зоне. Эксперты разъехались, но тут организаторы обнаружили, что недавно местный парламент издал закон: в промышленных зонах учебные заведения строить нельзя, и в список возможных мест её вносить не имели права. Чтобы формально соблюсти закон, из всех результатов убрали место , а все проставленные экспертами положительные баллы уменьшили на один, так как на меньшее количество мест полагалось бы меньше баллов.
Например, пусть эксперт М. расставил баллы следующим образом: за , за , за и за . Тогда после пересмотра результаты его оценок будут следующие: за , за , за . После нового подведения итогов оказалось, что ранее побеждавшее место у реки теперь на последнем по рейтингу месте — набрало меньше всех баллов.
- Могло ли такое быть, если экспертов было пятеро?
- Могла ли сложиться такая ситуация, если экспертов было более пяти человек?
- Какое минимальное количество экспертов могло быть, чтобы сложилась подобная ситуация?
- Да, такое могло быть.
После пересчёта получаем:
-
Да, такое могло быть. Для примера достаточно удвоить уже готовую таблицу, полученную в пункте .
-
По условию имеем и . Пусть изменилось на какую-то величину , а — на . Из данных условий получаем:
1)
-
-
Из 1) получаем
-
Из 2) и 3) получаем
Значит, . Заметим, что число, на которое изменяется оценка определённого места, равно , где – количество экспертов, а – количество нулей, которые поставили данному месту. Полученное нами неравенство означает, что поставили хотя бы на нуля больше, чем . Рассмотрев вместо , получим то же неравенство. Значит, нулей было хотя бы . Каждый эксперт ставил ровно ноль, значит и экспертов было хотя бы . Пусть их было ровно . Тогда у и стояло ровно по нуля. Таким образом, выполняются равенства . Всего сумма баллов равна , у больше всех, тогда у было хотя бы баллов. Разберём случаи:
- Пусть у ровно баллов. Тогда у и их по . Но невозможно набрать двумя числами, среди которых могут быть только и . Противоречие.
- Пусть у ровно баллов. Тогда у и их по . Тогда оценки и выглядят как набор (по-другому невозможно выбрать из чисел два числа так, чтобы они в сумме давали ) Тогда заметим, что максимальное значение может быть равно . Противоречие.
- Пусть у хотя бы баллов. Тогда у и должно быть хотя бы по баллов, но это невозможно набрать двумя числами, выбирая из имеющихся . Противоречие.
Тогда минимальное количество экспертов – . Пример приведён в пункте .