Олимпиадная задача Блинкова: футбольный турнир, текстовые задачи, индукция

  б) Минимальный разрыв между первым и последним местом не может быть меньше  n – 1.  Докажем, что для  n > 3  можно составить схему турнира так, чтобы получить разрыв  n – 1  (если  n = 2  или 3, то очевидно, минимальный разрыв будет составлять 3 очка).

  По индукции будем строить таблицу для n команд, в которой результаты – все целые числа от  n – 2  до  2n – 3.

  База  (n = 4).  Пример таблицы турнира для четырёх команд:

 Шаг индукции. По предположению индукции есть такая таблица дляnкоманд. Разобьём команды на тройки по количеству набранных очков: первая тройка – команды с  2n– 3,  2n– 4,  2n– 5  очками, вторая – с  2n– 6,  2n– 7,  2n– 8  очками и т. д. (последняя тройка может быть неполной). Добавим ещё одну команду. Рассмотрим три случая.   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  очко.