Олимпиада Туймаада по математике. Старшая лига. 2000 год

В стране Графландии 2000 городов, некоторые из которых соединены дорогами. Для каждого из городов посчитали количество выходящих из него дорог. Оказалось, что среди полученных чисел ровно два одинаковых. Чему они могут быть равны?

Комментарий/решение

Ответ в том, что 1000 — единственная возможность. Вот уродливый способ написать доказательство этого:

У нас есть список из 2000 чисел, который содержит каждое число от 0 до 1999 один раз, за ​​исключением того, что одно число отсутствует и одно число включено дважды. Несовместимо иметь одновременно 0 и 1999, поэтому один из них должен отсутствовать. Предположим сначала, что 0 отсутствует и представлен 1999 год. Граф будем строить рекурсивно: в качестве вершины выберем вершину степени 1999. (Двух вершин степени 1999 быть не может, иначе не было бы вершин степени 1, а это было бы плохо.) Затем среди остальных 1999 вершин, одна из них должна быть вершиной степени 1, и у нее уже есть ребро. (Если бы было две вершины степени 1, то максимально возможная степень была бы 1997, т.е. у нас не было бы вершины степени 1998, и это было бы плохо.) Итак, среди оставшихся 1998 вершин максимально возможная степень — 1998, и он должен быть связан с каждой из еще не рассмотренных вершин. (И опять же, из них может быть только один.) Среди них должна быть вершина степени 2, поэтому мы исчерпали ее ребра. (И она должна быть уникальной.) Тогда среди оставшихся 1996 вершин максимально возможная степень — 1997, и эта вершина должна быть уникальной и так далее. Наконец, мы нашли вершину степени 1, 2, 3, ..., 998, 1001, 1002, ..., 1999. Мы еще не рассмотрели 3 вершины, и на данный момент они имеют степень 999. Только одна из них должна быть вершина степени 999 (и их не может быть больше 1, иначе не было бы вершины степени 1000). Значит, две другие вершины должны быть соединены друг с другом и иметь степень 1000.