Докажите, что любая прямая, пересекающая все стороны выпуклого многоугольника, пересекает его диагонали в таком порядке, что можно сопоставить биекцию между парами отрезков; сформулируйте и докажите точную версию утверждения
Формулировка. Пусть PPP — выпуклый nnn-угольник, и прямая ℓ\ellℓ пересекает все его стороны и не проходит через вершины. Тогда nnn чётно, вершины чередуются по сторонам прямой ℓ\ellℓ; если вершины пронумерованы по кругу v1,…,v2mv_1,\dots,v_{2m}v1,…,v2m так, что ребро (vi,vi+1)(v_i,v_{i+1})(vi,vi+1) пересекает ℓ\ellℓ в точке pi=ℓ∩(vi,vi+1)p_i=\ell\cap(v_i,v_{i+1})pi=ℓ∩(vi,vi+1) (индексы по модулю 2m2m2m), то для любых i<ji<ji<j диагональ [vi,vj][v_i,v_j][vi,vj] пересекает ℓ\ellℓ тогда и только тогда, когда iii и jjj имеют разную четность; в этом случае точка пересечения qi,j=ℓ∩[vi,vj]q_{i,j}=\ell\cap[v_i,v_j]qi,j=ℓ∩[vi,vj] существует и лежит строго внутри отрезка (pi,p j−1)(p_i,p_{\,j-1})(pi,pj−1). Следствие: диагонали, пересекающие ℓ\ellℓ, задаются попарно парами вершин разной четности, и их точки пересечения располагаются на ℓ\ellℓ в естественном биективном соответствии с парами (i,j)(i,j)(i,j) (или с отрезками (pi,pj−1)(p_i,p_{j-1})(pi,pj−1)). Доказательство. 1) Чередование и чётность nnn. Так как каждая сторона (vi,vi+1)(v_i,v_{i+1})(vi,vi+1) пересекает ℓ\ellℓ, то её концы лежат по разные стороны от ℓ\ellℓ. Значит знаки (стороны) вершин при обходе многоугольника чередуются +,−,+,−,…+,-,+,-,\dots+,−,+,−,…, следовательно nnn чётно, n=2mn=2mn=2m. 2) Какие диагонали пересекают ℓ\ellℓ. Диагональ [vi,vj][v_i,v_j][vi,vj] пересекает ℓ\ellℓ тогда и только тогда, когда её концы лежат по разные стороны от ℓ\ellℓ, т.е. когда iii и jjj имеют разную четность. При этом пересечение единственно, так как прямая и отрезок пересекаются не более чем в одной точке. 3) Положение точки пересечения на ℓ\ellℓ. Зафиксируем i<ji<ji<j с разной четностью и рассмотрим кусок границы (замкнутую ломаную) Γ=vivi+1…vj\Gamma=v_i v_{i+1}\dots v_jΓ=vivi+1…vj. Каждое ребро этой ломаной пересекает ℓ\ellℓ и даёт точки pi,pi+1,…,pj−1p_i,p_{i+1},\dots,p_{j-1}pi,pi+1,…,pj−1; этих точек ровно j−ij-ij−i, а так как iii и jjj разной четности, число j−ij-ij−i нечётно. Отрезок [vi,vj][v_i,v_j][vi,vj] вместе с Γ\GammaΓ образует простую замкнутую ломаную (границу простого многоугольника) — назовём её BBB. По свойству границы простой замкнутой ломаной, число пересечений BBB с прямой ℓ\ellℓ чётно. Пересечения границы BBB с ℓ\ellℓ включают все точки pi,…,pj−1p_i,\dots,p_{j-1}pi,…,pj−1 (их нечётное число) и, возможно, точку qi,jq_{i,j}qi,j. Чтобы суммарное число пересечений стало чётным, должна присутствовать ещё одна точка пересечения — это и есть qi,jq_{i,j}qi,j. Она единственна (см. п.2) и, так как точки pi,…,pj−1p_i,\dots,p_{j-1}pi,…,pj−1 упорядочены вдоль ℓ\ellℓ в том же порядке, в каком идут соответствующие ребра, получаем, что qi,jq_{i,j}qi,j лежит строго между крайними из этих точек, то есть в отрезке (pi,pj−1)(p_i,p_{j-1})(pi,pj−1). 4) Биекция. Отображение, сопоставляющее диагонали, пересекающие ℓ\ellℓ (они соответствуют упорядоченным парам вершин разной четности), в внутренности отрезков (pi,pj−1)(p_i,p_{j-1})(pi,pj−1) является взаимно однозначным по построению: каждой такой диагонали соответствует ровно один отрезок (pi,pj−1)(p_i,p_{j-1})(pi,pj−1) и наоборот — каждая пара индексов (i,j)(i,j)(i,j) с разной четностью даёт единственную диагональ и единственную точку пересечения на соответствующем отрезке. Это доказывает формулировку и требуемое утверждение о порядке пересечений диагоналей прямой, пересекающей все стороны выпуклого многоугольника.
Доказательство.
1) Чередование и чётность nnn. Так как каждая сторона (vi,vi+1)(v_i,v_{i+1})(vi ,vi+1 ) пересекает ℓ\ellℓ, то её концы лежат по разные стороны от ℓ\ellℓ. Значит знаки (стороны) вершин при обходе многоугольника чередуются +,−,+,−,…+,-,+,-,\dots+,−,+,−,…, следовательно nnn чётно, n=2mn=2mn=2m.
2) Какие диагонали пересекают ℓ\ellℓ. Диагональ [vi,vj][v_i,v_j][vi ,vj ] пересекает ℓ\ellℓ тогда и только тогда, когда её концы лежат по разные стороны от ℓ\ellℓ, т.е. когда iii и jjj имеют разную четность. При этом пересечение единственно, так как прямая и отрезок пересекаются не более чем в одной точке.
3) Положение точки пересечения на ℓ\ellℓ. Зафиксируем i<ji<ji<j с разной четностью и рассмотрим кусок границы (замкнутую ломаную) Γ=vivi+1…vj\Gamma=v_i v_{i+1}\dots v_jΓ=vi vi+1 …vj . Каждое ребро этой ломаной пересекает ℓ\ellℓ и даёт точки pi,pi+1,…,pj−1p_i,p_{i+1},\dots,p_{j-1}pi ,pi+1 ,…,pj−1 ; этих точек ровно j−ij-ij−i, а так как iii и jjj разной четности, число j−ij-ij−i нечётно. Отрезок [vi,vj][v_i,v_j][vi ,vj ] вместе с Γ\GammaΓ образует простую замкнутую ломаную (границу простого многоугольника) — назовём её BBB. По свойству границы простой замкнутой ломаной, число пересечений BBB с прямой ℓ\ellℓ чётно. Пересечения границы BBB с ℓ\ellℓ включают все точки pi,…,pj−1p_i,\dots,p_{j-1}pi ,…,pj−1 (их нечётное число) и, возможно, точку qi,jq_{i,j}qi,j . Чтобы суммарное число пересечений стало чётным, должна присутствовать ещё одна точка пересечения — это и есть qi,jq_{i,j}qi,j . Она единственна (см. п.2) и, так как точки pi,…,pj−1p_i,\dots,p_{j-1}pi ,…,pj−1 упорядочены вдоль ℓ\ellℓ в том же порядке, в каком идут соответствующие ребра, получаем, что qi,jq_{i,j}qi,j лежит строго между крайними из этих точек, то есть в отрезке (pi,pj−1)(p_i,p_{j-1})(pi ,pj−1 ).
4) Биекция. Отображение, сопоставляющее диагонали, пересекающие ℓ\ellℓ (они соответствуют упорядоченным парам вершин разной четности), в внутренности отрезков (pi,pj−1)(p_i,p_{j-1})(pi ,pj−1 ) является взаимно однозначным по построению: каждой такой диагонали соответствует ровно один отрезок (pi,pj−1)(p_i,p_{j-1})(pi ,pj−1 ) и наоборот — каждая пара индексов (i,j)(i,j)(i,j) с разной четностью даёт единственную диагональ и единственную точку пересечения на соответствующем отрезке.
Это доказывает формулировку и требуемое утверждение о порядке пересечений диагоналей прямой, пересекающей все стороны выпуклого многоугольника.