2014-06-08
На плоскости дано множество M, состоящее из $n$ точек, никакие три из которых не лежат на одной прямой. Каждому отрезку с концами из М поставлено в соответствие либо число +1, либо число - 1, причем число отрезков, которым соответствует число - 1, равно $m$. Треугольник с вершинами из М назовем отрицательным, если произведение трех чисел, соответствующих его сторонам, равно - 1. Доказать, что число отрицательных треугольников имеет ту же четность, что и произведение $nm$.
Решение:
Пусть $k$ - число отрицательных треугольников. Для каждого треугольника перемножим числа, соответствующие его сторонам, а затем перемножим все полученные произведения. В итоге получится число $(- 1)^{k}$. Заметим, что число, соответствующее любому отрезку, входит в это произведение $n – 2$ раза, так как любой отрезок принадлежит $n – 2$ треугольникам. Следовательно, полученное произведение равно $(- 1)^{(n-2)m}$, поэтому число $k$ имеет ту же четность, что и число $(n - 2) m \equiv nm (\mod 2)$.