Разделы 
Дополнительно
Задача по математике - 3632
2019-06-13 
На столе у учителя стоят весы. На весах стоят гири не обязательно одного веса, на каждой из которых написаны фамилии одного или нескольких учеников. Ученик, входя в класс, переставляет на другую чашку весов каждую гирю, на которой написана его фамилия. Докажите, что можно впустить в класс таких учеников, чтобы в результате перевесила не та чашка весов, которая перевешивала вначале.
Решение:
Утверждение задачи можно доказать индукцией по числу учеников $n$. Но мы приведем другое решение, вытекающее из такого почти очевидного факта: сумма $2^k$ произведений $x_1x_2 \cdots x_k$, где $(x_1, x_2, \cdots, x_k$ - всевозможные наборы из чисел +1 и 1, равно 0 (для его доказательства достаточно перемножить к равенств 1 + (- 1) = 0 и в левой части провести всеми способами почленное умножение). Будем считать, что ученики имеют номера от 1 до $n$ для каждого списка номеров $i_1 < i_2 < \cdots < i_k$ (здесь $k < n$) обозначим через $a_{i_1 i_2 \cdots i_k}$ сумму масс гирь, на которых указан именно этот список, причем гири на одной чашке весов (перевешивающей вначале) берутся со знаком плюс, на другой - со знаком минус. Тогда нужное нам утверждение состоит в следующем: для многочлена вида
$f (x_1, x_2, \cdots, x_n) = a_1x_1 + \cdots + a_nx_n + a_{12}x_1x_2 + a_{13}x_1x_3 + \cdots + a_{(n-1),n} x_{n-1}x_n + a_{123}x_1x_2x_3 + \cdots + a_{n-2, n-1, n} x_{n-2}x_{n-1}x_n + \cdots + a_{1,2, \cdots, n} x_1 x_2 \cdots x_n$,
у которого сумма коэффициентов положительна, всегда найдется набор $x_1, x_2, \cdots, x_n$ из чисел +1 и -1 такой, что значение $f(x_1, x_2 \cdots, x_n)$ отрицательно ($f(x_1, x_2, \cdots, x_n)$ выражает разность масс на чашках весов, если $x_1 = -1$ для тех учеников $i$, кто переставил свои гири, и $x_i = 1$ для остальных). Остается заметить, что сумма значений $f(x_1, x_2, \cdots, x_n)$ по всем наборам - даже сумма значений каждого из составляющих его одночленов - равна 0; поскольку $f(1, 1, \cdots, 1) > 0$, то должен найтись набор, для которого значение $f$ отрицательно.
На столе у учителя стоят весы. На весах стоят гири не обязательно одного веса, на каждой из которых написаны фамилии одного или нескольких учеников. Ученик, входя в класс, переставляет на другую чашку весов каждую гирю, на которой написана его фамилия. Докажите, что можно впустить в класс таких учеников, чтобы в результате перевесила не та чашка весов, которая перевешивала вначале.
Решение:
Утверждение задачи можно доказать индукцией по числу учеников $n$. Но мы приведем другое решение, вытекающее из такого почти очевидного факта: сумма $2^k$ произведений $x_1x_2 \cdots x_k$, где $(x_1, x_2, \cdots, x_k$ - всевозможные наборы из чисел +1 и 1, равно 0 (для его доказательства достаточно перемножить к равенств 1 + (- 1) = 0 и в левой части провести всеми способами почленное умножение). Будем считать, что ученики имеют номера от 1 до $n$ для каждого списка номеров $i_1 < i_2 < \cdots < i_k$ (здесь $k < n$) обозначим через $a_{i_1 i_2 \cdots i_k}$ сумму масс гирь, на которых указан именно этот список, причем гири на одной чашке весов (перевешивающей вначале) берутся со знаком плюс, на другой - со знаком минус. Тогда нужное нам утверждение состоит в следующем: для многочлена вида
$f (x_1, x_2, \cdots, x_n) = a_1x_1 + \cdots + a_nx_n + a_{12}x_1x_2 + a_{13}x_1x_3 + \cdots + a_{(n-1),n} x_{n-1}x_n + a_{123}x_1x_2x_3 + \cdots + a_{n-2, n-1, n} x_{n-2}x_{n-1}x_n + \cdots + a_{1,2, \cdots, n} x_1 x_2 \cdots x_n$,
у которого сумма коэффициентов положительна, всегда найдется набор $x_1, x_2, \cdots, x_n$ из чисел +1 и -1 такой, что значение $f(x_1, x_2 \cdots, x_n)$ отрицательно ($f(x_1, x_2, \cdots, x_n)$ выражает разность масс на чашках весов, если $x_1 = -1$ для тех учеников $i$, кто переставил свои гири, и $x_i = 1$ для остальных). Остается заметить, что сумма значений $f(x_1, x_2, \cdots, x_n)$ по всем наборам - даже сумма значений каждого из составляющих его одночленов - равна 0; поскольку $f(1, 1, \cdots, 1) > 0$, то должен найтись набор, для которого значение $f$ отрицательно.
