Разделы 
Дополнительно
Задача по математике - 10440
2023-02-17 
Расположим в ряд произвольным способом $n$ черных и $n$ белых шариков. Подсчитаем число перемен цвета в каждом таком расположении, то есть определим, сколько раз черные и белые шарики оказываются рядом.
Доказать, что расположений, в которых шарики различных цветов $n - k$ раз оказываются рядом, столько же, сколько расположений с $n + k$ парами разноцветных «соседей» ($0 < k < n$).
Решение:
Подсчитаем, сколькими способами можно разложить черные и белые шарики так, чтобы число разноцветных «соседей» (черно-белых или бело-черных пар) было равно $v$. Необходимо различать два случая; когда число $v$ нечетно и когда оно четно.
Первый случай. Пусть число перемен цвета (разноцветных пар, образуемых двумя соседними шариками) в ряду равно нечетному числу $v = 2a + 1$. Назовем отрезком (белым или черным) одноцветные шарики, заключенные между ближайшими друг к другу парами разноцветных соседей. Поскольку число таких пар равно $2а + 1$, то число отрезков равно $2a + 2$. Следовательно, весь ряд состоит из $а + 1$ белых и такого же числа черных отрезков. Если сдвинуть все белые отрезки вместе, то получится ряд из $n$ белых шариков, разделенных $а$ «пограничными столбами». Их мы получим, отметив а шариков из $n - 1$. Аналогичное утверждение справедливо и относительно черных шариков: сдвинув вместе $a + 1$ черных отрезков, мы получим ряд из $n$ черных шариков, разделенных $а$ отмеченными шариками, которые выбраны из $n - 1$ шариков (на рис., а два верхних ряда соответствуют $n = 6, v = 7$ и, следовательно, $а = 3$).
Итак, любой ряд, выстроенный из $n$ белых и $n$ черных шариков, порождает два сочетания из $n - 1$ элементов по $a$. Но не все пары сочетаний, порождаемые различными рядами, различны: два расположения шариков могут порождать одну и ту же пару сочетаний, если белые и черные отрезки, соответствующие друг другу в обоих расположениях, имеют одинаковую длину, но один из рядов начинается с белого, а другой с черного отрезка.
Наоборот, любая пара сочетаний из $n - 1$ элементов по $а$ порождает разбиения $n$ белых и $n$ черных шариков на $a + 1$ отрезков. Расположив их в чередующемся порядке, мы получим ряд из $n$ белых и $n$ черных шариков, содержащий $v = 2a + 1$ пар разноцветных соседей. Существуют две разновидности ряда: одна начинается с черного, другая - с белого отрезка.
<рис. 209>.
Таким образом, число рядов, содержащих $v$ пар разноцветных соседей (черно-белых и бело-черных пар), вдвое больше числа пар сочетаний из $n - 1$ элементов по $а$, то есть равно
$2(С_{n-1}^{a})^{2}$.
Если число $n - k$, о котором говорится в условии задачи, нечетно, то число $n + k$ также нечетно, поскольку разность чисел $n - k$ и $n + k$ (равная $2k$) четна. Следовательно, приведенные выше рассуждения применимы к рядам из $n$ белых и $n$ черных шариков, содержащих как $n - k$, так и $nk$ пар разноцветных соседей. Если $v = n + k$, то число рядов с $v$ переменами цвета равно
$2 (C_{n-1}^{b})^{2}$,
где число $b$ определяется из соотношения $n + k = 2b + 1$ (так же, как число $а$ - из соотношения $n - k = 2а + 1$). Поскольку $a + b = n - 1$ и по хорошо известному свойству биномиальных коэффициентов $С_{m}^{k} = C_{m}^{m-k}$, то
$C_{n-1}^{a} = C_{n-1}^{b}$,
откуда и следует доказываемое утверждение.
Итак, для нечетного $v$ утверждение задачи доказано.
Второй случай. Пусть $v$ - четное число ($v = 2a$). Так же, как в предыдущем случае, рассмотрим одноцветные отрезки, на которые разбивают ряд из $n$ белых и $n$ черных шариков пары разноцветных соседей. На этот раз число отрезков равно $2a + 1$. Если ряд начинается с белого отрезка, то он состоит из $а + 1$ белых и $а$ черных отрезков. Случай, когда ряд начинается с черного отрезка, можно исключить из рассмотрения, поскольку его всегда можно свести к предыдущему случаю (ряд начинается с белого отрезка), перекрасив все белые шарики в черные и наоборот. Сдвинем вместе все $a + 1$ белых и отдельно все а черных отрезков. Мы получим два «половинных» ряда. Ряд из $n$ белых шариков разделен $а$ «пограничными столбами» - $а$ шариками, выбранными из $n - 1$ шариков. Ряд из $n$ черных шариков разделен $а - 1$ шариками, выбранными из $n - 1$ шариков (на рис. б два верхних ряда шариков соответствуют случаю, когда $n = 6, v = 4$ и, следовательно, $а = 2$).
Так же как и в случае четного v, можно утверждать, что число рядов из $n$ белых и $n$ черных шариков с заданным числом $v$ пар разноцветных соседей равно числу пар сочетаний, одно из которых берется из $n - 1$ элементов по $a$, а другое - из $n - 1$ элементов по $а - 1$. На этот раз между разбиениями ряда из $n$ белых и $n$ черных шариков на отрезки и парами сочетаний существует взаимно однозначное соответствие, поскольку цвет первого отрезка нельзя выбирать двумя способами: если, например, число белых отрезков на 1 больше числа черных отрезков, то ряд должен начинаться с белого отрезка.
Итак, число рядов из $n$ белых и $n$ черных шариков с $v$ парами разноцветных соседей равно
$2C_{n-1}^{a}C_{n-1}^{a-1}$,
где коэффициент 2 введен для того, чтобы учесть «равноправие» множества белых и множества черных шариков (безразлично, из какого множества мы будем выбирать $a$, а из какого $а - 1$ элементов).
Если $n - k = 2a$, то число $n + к$ четно: $n + k = 2b$. Следовательно, число рядов с $n + k$ переменами цвета равно
$2C_{n-1}^{b}C_{n-1}^{b-1}$.
Поскольку $а + b = n$, то по уже упоминавшемуся свойству биномиальных коэффициентов
$C_{n-1}^{a} = C_{n-1}^{b-1}$, $C_{n-1}^{a-1} = C_{n-1}^{b}$.
Тем самым утверждение задачи доказано и в случае, когда $v$ четно.
Расположим в ряд произвольным способом $n$ черных и $n$ белых шариков. Подсчитаем число перемен цвета в каждом таком расположении, то есть определим, сколько раз черные и белые шарики оказываются рядом.
Доказать, что расположений, в которых шарики различных цветов $n - k$ раз оказываются рядом, столько же, сколько расположений с $n + k$ парами разноцветных «соседей» ($0 < k < n$).
Решение:
Подсчитаем, сколькими способами можно разложить черные и белые шарики так, чтобы число разноцветных «соседей» (черно-белых или бело-черных пар) было равно $v$. Необходимо различать два случая; когда число $v$ нечетно и когда оно четно.
Первый случай. Пусть число перемен цвета (разноцветных пар, образуемых двумя соседними шариками) в ряду равно нечетному числу $v = 2a + 1$. Назовем отрезком (белым или черным) одноцветные шарики, заключенные между ближайшими друг к другу парами разноцветных соседей. Поскольку число таких пар равно $2а + 1$, то число отрезков равно $2a + 2$. Следовательно, весь ряд состоит из $а + 1$ белых и такого же числа черных отрезков. Если сдвинуть все белые отрезки вместе, то получится ряд из $n$ белых шариков, разделенных $а$ «пограничными столбами». Их мы получим, отметив а шариков из $n - 1$. Аналогичное утверждение справедливо и относительно черных шариков: сдвинув вместе $a + 1$ черных отрезков, мы получим ряд из $n$ черных шариков, разделенных $а$ отмеченными шариками, которые выбраны из $n - 1$ шариков (на рис., а два верхних ряда соответствуют $n = 6, v = 7$ и, следовательно, $а = 3$).
Итак, любой ряд, выстроенный из $n$ белых и $n$ черных шариков, порождает два сочетания из $n - 1$ элементов по $a$. Но не все пары сочетаний, порождаемые различными рядами, различны: два расположения шариков могут порождать одну и ту же пару сочетаний, если белые и черные отрезки, соответствующие друг другу в обоих расположениях, имеют одинаковую длину, но один из рядов начинается с белого, а другой с черного отрезка.
Наоборот, любая пара сочетаний из $n - 1$ элементов по $а$ порождает разбиения $n$ белых и $n$ черных шариков на $a + 1$ отрезков. Расположив их в чередующемся порядке, мы получим ряд из $n$ белых и $n$ черных шариков, содержащий $v = 2a + 1$ пар разноцветных соседей. Существуют две разновидности ряда: одна начинается с черного, другая - с белого отрезка.
<рис. 209>.
Таким образом, число рядов, содержащих $v$ пар разноцветных соседей (черно-белых и бело-черных пар), вдвое больше числа пар сочетаний из $n - 1$ элементов по $а$, то есть равно
$2(С_{n-1}^{a})^{2}$.
Если число $n - k$, о котором говорится в условии задачи, нечетно, то число $n + k$ также нечетно, поскольку разность чисел $n - k$ и $n + k$ (равная $2k$) четна. Следовательно, приведенные выше рассуждения применимы к рядам из $n$ белых и $n$ черных шариков, содержащих как $n - k$, так и $nk$ пар разноцветных соседей. Если $v = n + k$, то число рядов с $v$ переменами цвета равно
$2 (C_{n-1}^{b})^{2}$,
где число $b$ определяется из соотношения $n + k = 2b + 1$ (так же, как число $а$ - из соотношения $n - k = 2а + 1$). Поскольку $a + b = n - 1$ и по хорошо известному свойству биномиальных коэффициентов $С_{m}^{k} = C_{m}^{m-k}$, то
$C_{n-1}^{a} = C_{n-1}^{b}$,
откуда и следует доказываемое утверждение.
Итак, для нечетного $v$ утверждение задачи доказано.
Второй случай. Пусть $v$ - четное число ($v = 2a$). Так же, как в предыдущем случае, рассмотрим одноцветные отрезки, на которые разбивают ряд из $n$ белых и $n$ черных шариков пары разноцветных соседей. На этот раз число отрезков равно $2a + 1$. Если ряд начинается с белого отрезка, то он состоит из $а + 1$ белых и $а$ черных отрезков. Случай, когда ряд начинается с черного отрезка, можно исключить из рассмотрения, поскольку его всегда можно свести к предыдущему случаю (ряд начинается с белого отрезка), перекрасив все белые шарики в черные и наоборот. Сдвинем вместе все $a + 1$ белых и отдельно все а черных отрезков. Мы получим два «половинных» ряда. Ряд из $n$ белых шариков разделен $а$ «пограничными столбами» - $а$ шариками, выбранными из $n - 1$ шариков. Ряд из $n$ черных шариков разделен $а - 1$ шариками, выбранными из $n - 1$ шариков (на рис. б два верхних ряда шариков соответствуют случаю, когда $n = 6, v = 4$ и, следовательно, $а = 2$).
Так же как и в случае четного v, можно утверждать, что число рядов из $n$ белых и $n$ черных шариков с заданным числом $v$ пар разноцветных соседей равно числу пар сочетаний, одно из которых берется из $n - 1$ элементов по $a$, а другое - из $n - 1$ элементов по $а - 1$. На этот раз между разбиениями ряда из $n$ белых и $n$ черных шариков на отрезки и парами сочетаний существует взаимно однозначное соответствие, поскольку цвет первого отрезка нельзя выбирать двумя способами: если, например, число белых отрезков на 1 больше числа черных отрезков, то ряд должен начинаться с белого отрезка.
Итак, число рядов из $n$ белых и $n$ черных шариков с $v$ парами разноцветных соседей равно
$2C_{n-1}^{a}C_{n-1}^{a-1}$,
где коэффициент 2 введен для того, чтобы учесть «равноправие» множества белых и множества черных шариков (безразлично, из какого множества мы будем выбирать $a$, а из какого $а - 1$ элементов).
Если $n - k = 2a$, то число $n + к$ четно: $n + k = 2b$. Следовательно, число рядов с $n + k$ переменами цвета равно
$2C_{n-1}^{b}C_{n-1}^{b-1}$.
Поскольку $а + b = n$, то по уже упоминавшемуся свойству биномиальных коэффициентов
$C_{n-1}^{a} = C_{n-1}^{b-1}$, $C_{n-1}^{a-1} = C_{n-1}^{b}$.
Тем самым утверждение задачи доказано и в случае, когда $v$ четно.
