Эта задача является прямым продолжением задачи №70

Конкурсная задача №87 (12 баллов)

Раньше в круговых турнирах по футболу была принята система подсчета очков, при которой за победу команде начислялось 2 очка, за ничью - 1 очко, а за поражение - 0 очков. Сейчас за победу команда получает 3 очка.

Обобщим эту ситуацию:
Пусть при одной системе подсчета очков команда получает 0 очков за поражение, 1 очко - за ничью и c₁ очков - за победу (c₁ > 1). Такую систему назовем старой. Систему, в которой за поражение команде начисляют 0 очков, за ничью - 1 очко, а за победу - c₂ очков (с₂ > c₁) назовем новой.

Итоговую турнирную таблицу назовем строгой (в терминах задач 48 и 70 такие таблицы назывались правильными, но термин «строгая», представляется мне более удачным), если никакие две команды не набрали в итоге поровну очков.

Турнир будем называть перевертышем, если порядок расположения команд в итоговой таблице при подсчете по старой системе будет обратен порядку их расположения при подсчете очков по новой системе и при этом обе таблицы будут строгими.

Для заданных с₁ и c₂ определить наименьшее возможное число кругов в турнире-перевертыше.

Примечания:
1. Числа с₁ и с₂ могут быть любыми действительными с единственным ограничением c₂ > c₁ > 1.
2. Легко видеть, что любая система подсчета очков, при которой за победу дается больше очков, чем за ничью, а за ничью - больше, чем за поражение, сводится к «нормализованной» системе подсчета очков, при которой за поражение начисляется 0, за ничью - 1, а за победу - c очков при некотором c > 1.

Решение

Пусть u и h наименьшие натуральные такие, u*c₁ < h < u*c₂ и 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 балла

---