|
|
 |
Условие
На доске выписано (n – 1)n выражений: x1 – x2, x1 – x3, ..., x1 – xn, x2 – x1, x2 – x3, ..., x2 – xn, ..., xn – xn–1, где n ≥ 3. Лёша записал в тетрадь все эти выражения, их суммы по два различных, по три различных и т. д. вплоть до суммы всех выражений. При этом Лёша во всех выписываемых суммах приводил подобные слагаемые (например, вместо (x1 – x2) +
(x2 – x3) Лёша запишет x1 – x3, а вместо (x1 – x2) + (x2 – x1) он запишет 0).
Сколько выражений Лёша записал в тетрадь ровно по одному разу?
Решение
Все разности, выписанные на доске, разбиваются на пары противоположных: {xi – xj, xj – xi}. Если некоторая сумма (до приведения подобных) не содержит ни разности xi – xj, ни разности xj – xi, то к этой сумме можно прибавить (xi – xj) +
(xj – xi) и получить сумму, равную исходной. Если некоторая сумма содержит и слагаемое xi – xj и слагаемое xj – xi, то можно их вычеркнуть и опять получить сумму, равную исходной. Итак, в каждой сумме, записанной в тетрадь ровно один раз, из каждой пары противоположных разностей встречается ровно одна.
Для каждой такой суммы S зададим на множестве {x1, ..., xn} отношение (линейного) порядка, положив xi > xj, если в S входит слагаемое xi – xj. Надо проверить, что это отношение транзитивно (если xi > xj и xj > xk, то xi > xk). Действительно, в S не могут одновременно входить слагаемые xi – xj,
xj – xk, xk – xi, поскольку их сумма равна нулю.
Обратно, по каждому отношению порядка можно восстановить соответствующую сумму. Докажем, что она встретится в тетради только один раз. В силу симметрии достаточно проверить это для порядка x1 < x2 < ... < xn. Соответствующая сумма S состоит из всех слагаемых xi – xj, где i > j. Любая другая из выписанных Лёшей сумм до полного приведения подобных членов может быть записана как сумма тех же выражений с коэффициентами 0 и ±1. Подставим в обе суммы значения x1 = 1, x2 = 2, ..., xn = n. В S все слагаемые станут положительными, а во второй сумме некоторые слагаемые отсутствуют или отрицательны. Значения сумм различны, значит, после приведения подобных членов они совпасть не могут.
Итак, искомое количество сумм равно числу способов задать порядок на множестве из n элементов. Это число, очевидно, равно количеству перестановок n элементов, то есть n!.
Ответ
n! выражений.
Замечания
Ср. с задачей 97804.
