Школа №179 из 9 в 10 класс 2023 год

Школа № 179

2023 год

29.08.2023

1. В вазе лежит $n$ конфет, все разные. Сколькими способами $k$ взрослых людей могут поделить конфеты между собой, если вишнёвые и кокосовые конфеты должны достаться разным людям? (При разделении кому-то может достаться ноль конфет.)
2. Из 100 монет одна фальшивая и имеет два орла. Выбрали случайно монету и бросили 5 раз — выпали все орлы. Какова вероятность, что это фальшивая монета?
3. Докажите, что из любых 52 различных целых чисел можно выбрать 2 таких числа, что их сумма или их разность делится на 100.
4. Докажите, что для любой последовательности положительных чисел $x_1, x_2, \ldots$, найдутся бесконечно малые последовательности $a_n$ и $b_n$, такие что $x_n = \frac{a_n}{b_n}$ при всех натуральных $n$.
5. Приведите пример двух перестановок из 10 элементов $f$ и $g$, таких что любая перестановка является произведением $f$ и $g$, взятых несколько раз.

Решения задач

1. В вазе лежит $n$ конфет, все разные. Сколькими способами $k$ взрослых людей могут поделить конфеты между собой, если вишнёвые и кокосовые конфеты должны достаться разным людям? (При разделении кому-то может достаться ноль конфет.)
   Решение: Пусть вишнёвую конфету можно отдать любому из $k$ человек, а кокосовую — любому из $(k-1)$ человек (чтобы не совпал с вишнёвой). Остальные $(n-2)$ конфеты можно распределить между $k$ людьми независимо. Количество способов:
   $k \cdot (k-1) \cdot k^{n-2} = (k-1) \cdot k^{n-1}$.
   Ответ: $(k-1) \cdot k^{n-1}$.
2. Из 100 монет одна фальшивая и имеет два орла. Выбрали случайно монету и бросили 5 раз — выпали все орлы. Какова вероятность, что это фальшивая монета?
   Решение: По формуле Байеса:
   Пусть событие $A$ — выпало 5 орлов, $F$ — монета фальшивая. Тогда:
   $P(F|A) = \frac{P(A|F)P(F)}{P(A|F)P(F) + P(A| \text{норм})P(\text{норм})}$
   $P(A|F) = 1$, $P(F) = \frac{1}{100}$, $P(\text{норм}) = \frac{99}{100}$, $P(A| \text{норм}) = \left(\frac{1}{2}\right)^5 = \frac{1}{32}$.
   $P(F|A) = \frac{1 \cdot \frac{1}{100}}{1 \cdot \frac{1}{100} + \frac{1}{32} \cdot \frac{99}{100}} = \frac{32}{32 + 99} = \frac{32}{131}$.
   Ответ: $\frac{32}{131}$.
3. Докажите, что из любых 52 различных целых чисел можно выбрать 2 таких числа, что их сумма или их разность делится на 100.
   Решение: Рассмотрим остатки чисел при делении на 100. Возможны пары остатков $(r_i, r_j)$ такие, что:
   • $r_i \equiv r_j \pmod{100}$ → разность делится на 100.
   • $r_i \equiv -r_j \pmod{100}$ → сумма делится на 100.
   Всего 50 пар $\{r, 100 - r\}$ при $1 \le r \le 49$ и отдельно 0 и 50. Каждое число дает один остаток. По принципу Дирихле при 52 числах либо есть два с одинаковыми остатками, либо два из одной пары $\{r, 100 - r\}$. В первом случае разность делится на 100, во втором — сумма.
   Ответ: Доказано.
4. Докажите, что для любой последовательности положительных чисел $x_1, x_2, \ldots$, найдутся бесконечно малые последовательности $a_n$ и $b_n$, такие что $x_n = \frac{a_n}{b_n}$ при всех натуральных $n$.
   Решение: Определим последовательности:
   $a_n = \frac{x_n}{n}$, $b_n = \frac{1}{n}$.
   Тогда $\lim\limits_{n \to \infty} a_n = \lim\limits_{n \to \infty} \frac{x_n}{n} = 0$ и $\lim\limits_{n \to \infty} b_n = 0$, поскольку $\frac{1}{n} \to 0$. При этом $x_n = \frac{a_n}{b_n}$.
   Ответ: Например, $a_n = \frac{x_n}{n}$, $b_n = \frac{1}{n}$.
5. Приведите пример двух перестановок из 10 элементов $f$ и $g$, таких что любая перестановка является произведением $f$ и $g$, взятых несколько раз.
   Решение: В симметрической группе $S_{10}$ достаточно выбрать транспозицию и цикл длины 10. Пусть:
   $f = (1\, 2\, 3\, \ldots\, 10)$ — циклический сдвиг,
   $g = (1\, 2)$ — транспозиция.
   Известно, что эти два элемента порождают всю группу $S_{10}$.
   Ответ: Например, $f = (1\, 2\, 3\, \ldots\, 10)$, $g = (1\, 2)$.