Эта задача является прямым продолжением задачи №70
Конкурсная задача №87 (12 баллов)
Раньше в круговых турнирах по футболу была принята система подсчета очков, при которой за победу команде начислялось 2 очка, за ничью - 1 очко, а за поражение - 0 очков. Сейчас за победу команда получает 3 очка.
Обобщим эту ситуацию:
Пусть при одной системе подсчета очков команда получает 0 очков за поражение,
1 очко - за ничью и c1 очков - за победу (c1 > 1). Такую систему назовем
старой. Систему, в которой за поражение команде начисляют 0 очков, за ничью -
1 очко, а за победу - c2 очков (с2 > c1) назовем новой.
Итоговую турнирную таблицу назовем строгой (в терминах задач 48 и 70 такие таблицы назывались правильными, но термин «строгая», представляется мне более удачным), если никакие две команды не набрали в итоге поровну очков.
Турнир будем называть перевертышем, если порядок расположения команд в итоговой таблице при подсчете по старой системе будет обратен порядку их расположения при подсчете очков по новой системе и при этом обе таблицы будут строгими.
Для заданных с1 и c2 определить наименьшее возможное число кругов в турнире-перевертыше.
Примечания:
1. Числа с1 и с2 могут быть любыми действительными с единственным
ограничением c2 > c1 > 1.
2. Легко видеть, что любая система подсчета очков, при которой за победу
дается больше очков, чем за ничью, а за ничью - больше, чем за поражение,
сводится к «нормализованной» системе подсчета очков, при которой за поражение
начисляется 0, за ничью - 1, а за победу - c очков при некотором c > 1.
Решение
Пусть u и h наименьшие натуральные такие, u*c1 < h < u*c2 и d = min(u, h-u).
Тогда наименьшее возможное число кругов в турнире-перевертыше
k = ]3h/2[ - d, где ]x[ - потолок x, т.е. наимньшее целое, не меньшее x.
Доказательство этого утверждения естественно состоит из двух частей: доказательств непреодолимости и достижимости указанной оценки. С полным текстом доказательства можно ознакомиться здесь :marathon:ans_87.doc.
Обсуждение
Первоначальная цена задачи (12 баллов) была увилечена мной до 16 баллов. И инфляция здесь не причем. Просто задача действительно оказалась весьма трудной (даже признанные корифеи основательно спотыкались, решая ее).
Награды
За решение задачи 87 Олег Полубасов получает 15 призовых баллов. Он получил и обосновал оценку k, которая в ряде случаев совпадает с приведенной в решении, в других случаях оказывается на 1 больше. Анатолий Казмерчук получает по 9 призовых баллов. Он получил и «обосновал» оценку k, которая в ряде случаев верна, а в других может оказаться существенно меньше непреодолимой границы ;)
Эстетическая оценка задачи - 4.4 балла