На столе лежит 200 фишек: 100 красных, на которых написаны числа от 1 до 100, и 100 синих,на которых также написаны числа от 1 до 100. Враг забрал 99 фишек со стола (по своему усмотрению). Докажите, что на столе осталась пара из красной и синей фишек, сумма чисел на которых не меньше 101.

Представим условие задачи в виде графа. Пусть красные фишки будут красными вершинами, синие фишки – синими. Построим граф так, чтобы синяя фишка с номером i была соединена с красной фишкой с номером 101 − i. Тогда граф разобъется паросочетание, состоящее из 100 ребер. Заметим, что когда враг забирает фишку, он "удаляет" из паросочетания не более одной пары фишек. Тогда после того, как враг заберет 99 фишек, в графе останется хотя бы 1 пара, соединенная ребром, причем одна из этих фишек – красная, другая – синяя, а сумма их значений – ровно 101. Тогда найдется пара из красной и синей фишек, сумма чисел на которых хотя бы 101 (в нашем случае ровно 101).