2022-10-26
Пусть
$p_{1} < p_{2} < \cdots < p_{n}$ - различные простые числа. Рассмотрим выражение:
$p_{1} : p_{2} : p_{3} : \cdots : p_{n}$.
Расставляя различными способами скобки, можем получать разные выражения. Например, при $n = 4$ можно расставить скобки следующими способами: $p_{1} : (p_{2} : (p_{3} : p_{4})); (p_{1} : p_{2}): (p_{3} : p_{4}); p_{1} : ((p_{2}: p_{3}): p_{4}); (p_{1} : (p_{2} : p_{3})): p_{4}$.
Легко заметить, что первое и последнее из написанных выражений представляют одно и то же число $\frac{p_{1}p_{3}}{p_{2}p_{4}}$. Спрашивается, сколько различных чисел можно получить из предложенного выражения, расставляя скобки, при произвольном $n \geq 2$?
Решение:
Прежде всего заметим, что после выполнения всех делений получим рациональное число вида
$r = \frac{q_{1}q_{2} \cdots q_{k} }{q_{k+1}q_{k+2} \cdots q_{n} }$,
где $q_{1},q_{2}, \cdots , q_{n}$ - исходные простые числа $p_{1}, p_{2},, \cdots, p_{n}$, переставленные каким-то образом. Так как все $q_{i}$ -простые, любая из таких дробей несократима и две. такие дроби равны тогда и только тогда, когда равны их числители (или знаменатели).
Теперь покажем, что можем получить в точности $2^{n-2}$ различных чисел.
Рассмотрим число $r$. Предположим дополнительно, что $q_{1} < q_{2} < \cdots < q_{k}$ и $q_{k+1} < q_{k + 2} < \cdots < q_{n}$. Назовем это число «хорошим», если оно получено из выражения $p_{1} : p_{2}: \cdots : p_{n}$ при помощи расстановки скобок. Нетрудно убедиться, что если $r$ «хорошее», то $q_{1} = p_{1}, q_{k+1} = p_{2}$, т. е.
$r = \frac{p_{1}q_{2} \cdots q_{k} }{p_{2}q_{k+1} \cdots q_{n} }$.
Докажем индукцией по $k$, что любое число такого вида является «хорошим». При $n = 2$ это очевидно. Пусть $q_{2} = p_{l + 1}$, где $2 \leq l < n$. Тогда
$r = \frac{p_{1}p_{l+1}q_{3} \cdots q_{k} }{p_{2}p_{3}p_{4} \cdots p_{l} q_{k+l} \cdots q_{n} } = \frac{p_{1} }{p_{2}p_{3} \cdots p_{l-1} } : \left [ \frac{p_{l}q_{3} \cdots q_{k} }{p_{l+1}q_{k+l} \cdots q_{n} } \right ] = (( \cdots (p_{1} : p_{2} ) : p_{3} ) \cdots ) : p_{l-1} ) : \left [ \frac{p_{l}q_{3} \cdots q_{k} }{p_{l+1}q_{k+1} \cdots q_{n} } \right ]$.
По предположению индукции число в квадратных скобках «хорошее», т. е. получается из выражения $p_{l} : p_{l+1} : \cdots : p_{n}$ при помощи расстановки скобок. Следовательно, и число $r$ - «хорошее». Таким образом, «хороших» чисел ровно столько, сколько различных подмножеств $\{ q_{2}, \cdots , q_{k} \}$ множества $\{ p_{3},p_{4}, \cdots , p_{n} \}$. Легко убедиться в том, что таких подмножеств в точности $2^{n - 2}$.