Комбинаторика на ОММО: графы, турниры, логика, Дирихле

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

Предположим, что борец с номером может победить. Тогда в первом туре должны выбыть борцы с номерами и . Это возможно только если борец с номером проиграл борцу с номером , а борец с номером проиграл борцу с номером . Значит, после первого тура борцы с номерами и останутся.

Аналогично, после второго тура останутся борцы с номерами и , после третьего: и , после седьмого: и Значит, в последнем, финальном, бою встретятся борцы с номерами и . Противоречие с предположением, что борец с номером может победить.

Покажем, что борец с номером 16 может победить. Назовём борцов с номерами большими слабыми. Пусть в туре с номером борец с номером проиграет борцу с номером , борец с номером проиграет борцу с номером , борцы с номерами победят каких-то слабых борцов, оставшиеся слабые борцы как-то сыграют между собой. Тогда после туров останутся борцы с номерами и , и в финальном бое борец с номером победит.