Разделы 
Дополнительно
Задача по математике - 10449
2023-02-17 
Имеется 30 копилок. Каждую копилку можно открыть лишь одним ключом, который не подходит ко всем остальным копилкам. Перемешав ключи, их бросили в запертые копилки наугад по одному. Две копилки взломали.
Какова вероятность того, что после этого все остальные копилки удастся открыть, не взламывая замков? (Открыв или взломав какую-либо копилку, мы можем использовать брошенный в нее ключ для открывания копилки, к которой он подходит.)
Решение:
Докажем, что если в $n$ копилок наугад бросили по ключу (каждую копилку можно открыть одним и только одним ключом) и две копилки взломали, то с вероятностью $\frac{2}{n}$ остальные копилки удалось открыть вставленными ключами.
Пусть $р_{n}$ - искомая вероятность для случая, когда число копилок равно $n$. Ясно, что $p_{2} = 1$. Докажем, что если $n \geq 2$, то
$p_{n+1} = \frac{n}{n+1} p_{n}$. (1)
Отсюда будет следовать, что
$p_{n} = \frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \cdots \cdot \frac{2}{3} p_{2} = \frac{2}{n}$,
и, таким образом, вероятность, которую требуется найти в задаче, $p_{30} = \frac{1}{15}$.
Расставим $n + 1$ копилок в ряд и в каждую бросим наугад по ключу. Получившуюся перестановку ключей (номера копилок остаются неизменными) обозначим $Е$. Пусть $r$ - номер копилки, в которую брошен ключ от $(n + 1)$-й копилки, a $s$ - номер копилки, ключ от которой брошен в $(n + 1)$-ю копилку. Ясно, что может произойти одно из двух: либо оба числа $r$ и $s$ равны $n + 1$ (ключ от последней копилки брошен в последнюю копилку), либо оба числа $r$ и $s$ меньше $n + 1$.
В первом случае ($r = s = n + 1$), исключив из рассмотрения последнюю копилку, мы получим некоторую перестановку $Е_{1}$ ключей от первых $n$ копилок среди первых $n$ копилок. Во втором случае сопоставим перестановке $n + 1$ ключей $Е$ перестановку $Е_{1}$ отличающуюся от $Е$ лишь тем, что в $r$-ю копилку брошен ключ от $s$-й копилки [а ключ от $(n + 1)$-й копилки, бывший там раньше, находится теперь в «своей» $(n + 1)$-й копилке].
Итак, всякой перестановке $Е$ соответствует вполне определенная перестановка $E_{1}$. Наоборот, если перестановка $E_{1}$ известна, то она могла возникнуть либо после того, как, вынув ключи из $r$-н и $(n+1)$-й копилок ($1 \leq r \leq n$), мы поменяли их местами, либо после того, как была исключена из рассмотрения $(n + 1)$-я копилка, в которую брошен ее же «собственный» ключ. Следовательно, одной перестановке $Е_{1}$ ключей от первых $n$ копилок соответствуют $n + 1$ различных перестановок ключей от $n + 1$ копилок.
Без ограничения общности мы можем считать, что взламываются две первые копилки. После этого мы сможем открывать и при перестановке $Е$, и при перестановке $E_{1}$ одни и те же копилки до тех пор, пока не дойдем до $r$-й копилки. Дойдя до этой копилки, мы при перестановке ключей $Е$ сможем открыть $(n + 1)$-ю копилку, а затем копилку с номером $s$. При перестановке $Е_{1}$ ключ, лежащий в $r$-й копилке, подходит к $s$-й копилке. Следовательно, дальше мы снова в обеих перестановках открываем одни и те же копилки.
Таким образом, при перестановке $Е$ все $n + 1$ копилок можно открыть в том и только в том случае, если при соответствующей ей перестановке $Е_{1}$ можно открыть первые $n$ копилок и в $(n + 1)$-ю копилку брошен ключ, который не подходит к ее замку. [В противном случае $(n + 1)$-ю копилку открыть не удастся.]
Следовательно, каждая перестановка п ключей соответствует $n + 1$ перестановкам $n + 1$ ключей, а перестановки, при которых можно открыть все копилки, соответствуют только $n$ перестановкам $n + 1$ ключей. Именно это и утверждает соотношение (1).
Имеется 30 копилок. Каждую копилку можно открыть лишь одним ключом, который не подходит ко всем остальным копилкам. Перемешав ключи, их бросили в запертые копилки наугад по одному. Две копилки взломали.
Какова вероятность того, что после этого все остальные копилки удастся открыть, не взламывая замков? (Открыв или взломав какую-либо копилку, мы можем использовать брошенный в нее ключ для открывания копилки, к которой он подходит.)
Решение:
Докажем, что если в $n$ копилок наугад бросили по ключу (каждую копилку можно открыть одним и только одним ключом) и две копилки взломали, то с вероятностью $\frac{2}{n}$ остальные копилки удалось открыть вставленными ключами.
Пусть $р_{n}$ - искомая вероятность для случая, когда число копилок равно $n$. Ясно, что $p_{2} = 1$. Докажем, что если $n \geq 2$, то
$p_{n+1} = \frac{n}{n+1} p_{n}$. (1)
Отсюда будет следовать, что
$p_{n} = \frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \cdots \cdot \frac{2}{3} p_{2} = \frac{2}{n}$,
и, таким образом, вероятность, которую требуется найти в задаче, $p_{30} = \frac{1}{15}$.
Расставим $n + 1$ копилок в ряд и в каждую бросим наугад по ключу. Получившуюся перестановку ключей (номера копилок остаются неизменными) обозначим $Е$. Пусть $r$ - номер копилки, в которую брошен ключ от $(n + 1)$-й копилки, a $s$ - номер копилки, ключ от которой брошен в $(n + 1)$-ю копилку. Ясно, что может произойти одно из двух: либо оба числа $r$ и $s$ равны $n + 1$ (ключ от последней копилки брошен в последнюю копилку), либо оба числа $r$ и $s$ меньше $n + 1$.
В первом случае ($r = s = n + 1$), исключив из рассмотрения последнюю копилку, мы получим некоторую перестановку $Е_{1}$ ключей от первых $n$ копилок среди первых $n$ копилок. Во втором случае сопоставим перестановке $n + 1$ ключей $Е$ перестановку $Е_{1}$ отличающуюся от $Е$ лишь тем, что в $r$-ю копилку брошен ключ от $s$-й копилки [а ключ от $(n + 1)$-й копилки, бывший там раньше, находится теперь в «своей» $(n + 1)$-й копилке].
Итак, всякой перестановке $Е$ соответствует вполне определенная перестановка $E_{1}$. Наоборот, если перестановка $E_{1}$ известна, то она могла возникнуть либо после того, как, вынув ключи из $r$-н и $(n+1)$-й копилок ($1 \leq r \leq n$), мы поменяли их местами, либо после того, как была исключена из рассмотрения $(n + 1)$-я копилка, в которую брошен ее же «собственный» ключ. Следовательно, одной перестановке $Е_{1}$ ключей от первых $n$ копилок соответствуют $n + 1$ различных перестановок ключей от $n + 1$ копилок.
Без ограничения общности мы можем считать, что взламываются две первые копилки. После этого мы сможем открывать и при перестановке $Е$, и при перестановке $E_{1}$ одни и те же копилки до тех пор, пока не дойдем до $r$-й копилки. Дойдя до этой копилки, мы при перестановке ключей $Е$ сможем открыть $(n + 1)$-ю копилку, а затем копилку с номером $s$. При перестановке $Е_{1}$ ключ, лежащий в $r$-й копилке, подходит к $s$-й копилке. Следовательно, дальше мы снова в обеих перестановках открываем одни и те же копилки.
Таким образом, при перестановке $Е$ все $n + 1$ копилок можно открыть в том и только в том случае, если при соответствующей ей перестановке $Е_{1}$ можно открыть первые $n$ копилок и в $(n + 1)$-ю копилку брошен ключ, который не подходит к ее замку. [В противном случае $(n + 1)$-ю копилку открыть не удастся.]
Следовательно, каждая перестановка п ключей соответствует $n + 1$ перестановкам $n + 1$ ключей, а перестановки, при которых можно открыть все копилки, соответствуют только $n$ перестановкам $n + 1$ ключей. Именно это и утверждает соотношение (1).
