|
|
 |
Условие
а) В футбольном турнире в один круг участвовало 75 команд. За победу в матче команда получала 3 очка, за ничью 1 очко, за поражение 0 очков. Известно, что каждые две команды набрали различное количество очков. Найдите наименьшую возможную разность очков у команд, занявших первое и последнее места.
б) Тот же вопрос для n команд.
Решение
б) Минимальный разрыв между первым и последним местом не может быть меньше n – 1. Докажем, что для n > 3 можно составить схему турнира так, чтобы получить разрыв n – 1 (если n = 2 или 3, то очевидно, минимальный разрыв будет составлять 3 очка).
По индукции будем строить таблицу для n команд, в которой результаты – все целые числа от n – 2 до 2n – 3.
База (n = 4). Пример таблицы турнира для четырёх команд:
1) n = 3k + 1. Пусть новая команда выиграет у первой команды 1-й тройки и проигрывает второй и третьей. Тогда у первой команды останется
2n – 3 очка, у второй станет 2n – 1 очко, и она выйдет на первое место. У третьей команды станет 2n – 2 очка. Аналогично поступим с другими полными тройками. Тогда все тройки сдвинутся "вверх" на два очка. Останется одна команда, занимавшая последнее место с n – 2 очками, а у новой команды пока n – 1 очко. Пусть между собой они сыграют вничью и добавят себе по очку.
2) n = 3k + 2. Команды из k троек играют с новой командой аналогично случаю 1). У последних двух команд было n – 1 и n – 2 очка, у новой команды пока n – 2 очка. Пусть последняя команда выиграет у новой, а предпоследняя – сыграет с ней вничью:
3) n = 3k. После того как новая команда сыграет с первыми k – 1 тройками, у неё станет n – 3 очка. У последних трёх команд очков было n, n – 1,
n – 2. Пусть предпоследняя команда выиграет у новой, последняя команда сыграет с ней вничью, а команда с n очками проиграет . Тогда бывшие последними команды наберут соответственно n, n + 2, n – 1, а у новой команды будет n + 1 очко.
Ответ
а) 74; б) n – 1, если n > 3; 3, если n = 2 или 3.
Замечания
Для пункта а) можно предложить и другие алгоритмы составления схемы турнира.
