Принцип Дирихле

Пусть сёл расположены на левом берегу, а — на правом. Пар сёл на левом берегу Если на правом берегу есть хотя бы села, из которых выходит хотя бы по два рейса фирмы «Сцилла», то по принципу Дирихле из них найдутся два села, из которых ведут по два рейса фирмы «Сцилла» в одну и ту же пару. В этом случае будет выполнено первое условие задачи. В противном случае на правом берегу будет хотя бы сёл, из которых ведут хотя бы шесть рёбер фирмы «Харибда». Так как на левом берегу мы можем выбрать сёл семью способами, по принципу Дирихле на правом берегу найдутся хотя бы сёл ( из которых ведут по шесть рёбер фирмы «Харибда» в одну и ту же шестёрку сёл левого берега. В этом случае выполнено второе условие задачи.