Задача 00025 — Задачи на Графы

На доске написаны $n \geq 2$ вещественных чисел $x_{1}, \ldots, x_{n}$ . Каждым ходом разрешается стереть с доски какие-нибудь два числа а и $b$ и написать вместо них число $\frac{a+b-2 a b}{1-a b}$ . В результате таких действий на доске осталось одно число. Докажите, что если при другой последовательности действий на доске осталось бы одно число, оно было бы тем же самым.

Решение

Если применить нашу операцию к числам 1 и $a \neq 1$ , получится число 1. Это значит, что количество единиц на доске не меняется. Поэтому, если их больше одной, одно число оставить не удастся, а если одна, то она и останется при любом допустимом порядке действий. Дальше будем считать, что среди исходных чисел единиц нет.

Применим операцию к числам $a$ и $b$ . Пусть $z=\frac{a+b-2 a b}{1-a b}$ . Тогда $1-z=\frac{(1-a)(1-b)}{1-a b}$ . Отметим, что это число не равно 0 , так как исходные числа не равны 1. Значит, в процессе преобразований 1 не появится. Теперь заметим, что $\frac{z}{1-z}=\frac{a(1-b)+b(1-a)}{(1-a)(1-b)}=\frac{a}{1-a}+\frac{b}{1-b}$ . Следовательно, сумма величин вида $\frac{a}{1-a}$ по всем числам в любой момент процесса корректно определена и сохраняется, пусть она равна $s$ . Пусть в результате получилось число $c$ , тогда $\frac{c}{1-c}=s$ . Тогда $s \neq-1$ , так как $c \neq c$ -1. Следовательно, $c=\frac{s}{s+1}$ — единственное возможное значение последнего числа.