|
|
 |
Условие
На окружности отмечено 2N точек (N – натуральное число). Известно, что через любую точку внутри окружности проходит не более двух хорд с концами в отмеченных точках. Назовем паросочетанием такой набор из N хорд с концами в отмеченных точках, что каждая отмеченная точка является концом ровно одной из этих хорд. Назовём паросочетание чётным, если количество точек, в которых пересекаются его хорды, чётно, и нечётным иначе. Найдите разность между количеством чётных и нечётных паросочетаний.
Решение
Обозначим отмеченные точки A1, A2, ..., A2N в порядке обхода окружности по часовой стрелке. Индукцией по N докажем, что чётных паросочетаний на 1 больше, чем нечётных. Для N = 1 утверждение очевидно: есть лишь одно паросочетание, и оно чётно.
Шаг индукции. Первый способ. Пусть в паросочетании участвует хорда A1Ai и ее пересекают ровно k хорд. Рассмотрим точки A2, ..., Ai–1; ровно k из них являются концами хорд, пересекающих A1Ai. Остальные i – 2 – k точек разбиваются на пары точек, соединенных хордами, которые не пересекают A1Ai. Таким образом, число i – 2 – k чётно, то есть числа i и k имеют одинаковую чётность.
Разобьём все паросочетания на 2N – 1 группу П2, ..., П2N : в группу Пi попадут те паросочетания, в которых точка A1 соединена с Ai. Выкинем из каждого паросочетания из Пi хорду A1Ai; получатся все возможные паросочетания на оставшихся 2N – 2 точках. По предположению индукции, среди них чётных на одно больше, чем нечётных. При этом если i чётно, то чётность паросочетания при выкидывании не менялась, а если нечётно, то менялась. Значит, в каждом из N множеств П2, ..., П2N чётных паросочетаний на одно больше, чем нечётных, а в каждом из N – 1 множеств П3, ..., П2N–1 нечётных на одно больше, чем чётных. Итого, всего чётных паросочетаний больше, чем нечётных, на N – (N – 1) = 1.
Второй способ. Рассмотрим все паросочетания, в которых A2N–1 и A2N соединены хордой. Эта хорда не пересекается ни с одной другой. Значит, выбросив её из каждого из рассматриваемых паросочетаний, мы получим все паросочетания на точках A1, ..., A2N–2, причём чётность каждого из них сохранится. По предположению индукции, среди наших паросочетаний чётных на одно больше, чем нечётных.
Осталось доказать, что среди остальных паросочетаний
поровну чётных и нечётных. Рассмотрим любое из них; пусть в нём есть хорды
A2N–1Ai и A2NAk. Заменим эти хорды на A2NAi и
A2N–1Ak. При этом, если
исходная хорда пересекалась с какой-то из остальных, то и новая хорда будет
с ней пересекаться. С другой стороны, если хорды A2N–1Ai и A2NAk не пересекались, то новые хорды будут пересекаться, и наоборот. Итак, мы разбили оставшиеся паросочетания на пары разной чётности.
Ответ
1.
