Содержание

№87

Эта задача является прямым продолжением задачи №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 балла