ТренажёрTrainer

Тёплый стартWarm start

Карточки возвращаются через 1, 2, 4, 7, 14 и 21 день — в зависимости от того, насколько уверенно ты их вспомнил. «Не помню» отправляет карточку в самое начало.

Cards return after 1, 2, 4, 7, 14, and 21 days depending on how confidently you recalled them. “I don’t remember” sends a card back to the beginning.

114

к повтору сейчас

в работе

131

всего карточек

Комбинаторика день 1 осталось 114

Правило умножения: две оговорки, без которых оно не работает

The multiplication rule: two qualifications without which it does not work

Сначала сформулируй вслух. Попытка вспомнить закрепляет сильнее, чем чтение готового ответа.

Перемешанная практика

7 задач высокого доступного уровня: подборка покрывает все пройденные разделы. Это отдельная попытка — ответы из учебных дней сюда не подставляются. Сначала определи, что перед тобой, и только потом решай: на экзамене тему никто не подписывает.

7 problems at the strongest available level: this set covers every section you have completed. It is a separate attempt—answers from study days are not carried over. Identify what you are looking at before you solve it; the exam does not label the topic.

Собрать новый набор

S1101Уровень ШАДАлгоритмыОлимпиада ШАД 2025, задача «Похожие геномы»

Мерой похожести двух вирусов служит побитовое исключающее ИЛИ (XOR) их геномов: чем меньше XOR, тем более похожи вирусы.

В базе лежат геномы

[38, 18, 7, 52, 13, 25, 60, 3, 44, 29]

Найдите наименьший возможный XOR пары геномов, стоящих на разных позициях.

The similarity of two viruses is measured by the bitwise exclusive OR (XOR) of their genomes: the smaller the XOR, the more similar the viruses.

The database contains the genomes

[38, 18, 7, 52, 13, 25, 60, 3, 44, 29]

Find the smallest possible XOR of two genomes at distinct positions.

ответ

Подсказка / Hint

Для десяти чисел хватит перебора сорока пяти пар — приём из b1101, только вместо суммы XOR. Быстрый ход — тот же спуск по разрядам, что в мосте b1105, но в обратную сторону. А дальше подумай, как отвечать на такой запрос, если чисел $2 \cdot 10^5$ и они добавляются по одному.

With ten numbers, enumerating all forty-five pairs is enough; this is the technique from b1101, with XOR instead of addition. The fast approach uses the same bitwise descent as bridge problem b1105, but in the opposite direction. Then consider how to answer the query if there are $2 \cdot 10^5$ numbers arriving one by one.

Решение / Solution

Ответ для наших данных: 4 — пара $7$ и $3$: $7 \oplus 3 = 0111_2 \oplus 0011_2 = 0100_2 = 4$.

from itertools import combinations
print(min(x ^ y for x, y in combinations(G, 2)))   # 4

Перебор пар — это $O(n^2)$, здесь всего 45 пар. На олимпиадных ограничениях ($n$ до $2\cdot10^5$, числа до $2^{30}$) он не проходит, и нужен другой подход.

Правильное решение — префиксное дерево (бор) на битах.

Храним двоичные представления чисел в дереве как строки длины $K = 30$, от старших разрядов к младшим. При добавлении нового числа $X$ делаем два действия:

Ищем в боре число $Y$, дающее минимальный XOR с $X$. Спускаемся от корня; на каждой глубине пытаемся пойти по тому же биту, что у $X$ — тогда в этом разряде XOR даст ноль. Если такого перехода нет, идём по единственному имеющемуся.
Вставляем $X$ в бор.

Ответ поддерживаем как минимум по всем добавлениям.

Почему жадный спуск корректен. Пусть на глубине $d$ можно пойти двумя путями. Совпадение бита даёт в этом разряде ноль, несовпадение — единицу, то есть вклад $2^{K-d}$. Но по пункту блока «Мост» один старший разряд перевешивает все младшие вместе взятые, поэтому совпадение в старшем разряде выгоднее любого выигрыша во всех младших. Жадность оптимальна.

Сложность: $O(NK)$ по времени и памяти, где $K$ — число бит.

Проверка третьим способом

Работает правило из блока «Триггеры»: минимальный XOR всегда достигается на паре соседей в отсортированном порядке. Вот его вывод в две строки. Пусть $x < y < z$, и пусть $b$ — самый старший разряд, в котором $x$ и $z$ различаются: в нём у $x$ ноль, у $z$ единица, поэтому $x \oplus z \ge 2^{b}$. Все разряды старше $b$ у $x$ и $z$ совпадают, а $y$ лежит между ними, поэтому в старших разрядах $y$ совпадает с обоими; в самом разряде $b$ у $y$ стоит либо ноль, и тогда $x \oplus y < 2^{b}$, либо единица, и тогда $y \oplus z < 2^{b}$. В обоих случаях какая-то из более тесных пар строго лучше крайней — значит пару, между членами которой лежит третье число, можно не проверять.

Отсортируем: 3, 7, 13, 18, 25, 29, 38, 44, 52, 60 — и проверим только девять соседних пар вместо сорока пяти. Их XOR равны 4, 10, 31, 11, 4, 59, 10, 24, 8; наименьшее значение 4 достигается дважды: $3 \oplus 7 = 4$ и $25 \oplus 29 = 4$. Ответ сошёлся с перебором, и это независимая проверка, а не пересчёт того же самого.

Что забрать

Идея «старший разряд важнее всех младших вместе» — универсальная для битовых задач. Она превращает переборную задачу в жадный спуск по дереву, то есть в то же деление пополам, что и бинарный поиск, только режется не отрезок чисел, а множество кандидатов по очередному биту.

На YMLS такое вряд ли придёт в полном объёме, но сам приём «работать с числами поразрядно, от старших к младшим» вполне может понадобиться.

For the given data, the answer is 4, attained by 7 and 3: $7 \oplus 3 = 0111_2 \oplus 0011_2 = 0100_2 = 4$.

from itertools import combinations
print(min(x ^ y for x, y in combinations(G, 2)))   # 4

Pair enumeration takes $O(n^2)$ time and involves only 45 pairs here. It is too slow under olympiad constraints ($n$ up to $2\cdot10^5$, values below $2^{30}$), so a different approach is required.

The appropriate solution is a binary prefix tree, or binary trie.

Store the binary representations of the numbers in a tree as strings of length $K=30$, from the most significant bit to the least significant. When a new number $X$ arrives, perform two operations:

Find a number $Y$ in the trie minimizing its XOR with $X$. Descend from the root. At each depth, first try the branch with the same bit as $X$, which contributes zero at this position. If that branch does not exist, take the only available branch.
Insert $X$ into the trie.

Maintain the answer as the minimum over all insertions.

Why the greedy descent is correct. Suppose both branches are available at depth $d$. Matching the bit contributes zero at this position, while differing contributes one, with value $2^{K-d}$. One more significant bit outweighs all less significant bits combined, as established in the Bridge section. Therefore matching the more significant bit is preferable to any possible gain below it, and the greedy choice is optimal.

The time and space complexity are $O(NK)$, where $K$ is the number of bits.

A third method for checking

The rule from the Triggers section applies: the minimum XOR is always attained by two adjacent values in sorted order. Here is the proof. Let $x<y<z$, and let $b$ be the most significant bit at which $x$ and $z$ differ. At this bit, $x$ has zero and $z$ has one, so $x\oplus z \ge 2^b$. All bits above $b$ coincide in $x$ and $z$. Since $y$ lies between them, it agrees with both in those higher bits. At bit $b$, either $y$ has zero, giving $x\oplus y < 2^b$, or it has one, giving $y\oplus z < 2^b$. In either case, a closer pair is strictly better than the outer pair. Thus a pair with a third number between its members never needs to be checked.

Sort the values: 3, 7, 13, 18, 25, 29, 38, 44, 52, 60. Check only nine adjacent pairs rather than forty-five. Their XORs are 4, 10, 31, 11, 4, 59, 10, 24, 8. The minimum, 4, is attained twice: $3 \oplus 7 = 4$ and $25 \oplus 29 = 4$. This agrees with exhaustive search and is an independent check.

The takeaway

The principle “a more significant bit outweighs all less significant bits combined” is universal in bitwise problems. It turns an exhaustive search into a greedy tree descent: the same kind of halving as binary search, except that the candidate set is partitioned by the next bit rather than by a numeric interval.

A full-strength version is unlikely on YMLS, but the underlying technique of processing numbers bit by bit, from most significant to least significant, may well be useful.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S1001Уровень ШАДЛиналОлимпиада ШАД 2024, задача C «Дороги под Минском»

В области дороги устроены так: любые два города соединяет ровно одна трасса, любые две трассы пересекаются ровно в одном городе, и на каждой трассе лежит не меньше двух городов (может быть и больше).

Всего трасс $n = 2071$. Сколько может быть городов? Если ответ единственный, укажите его.

Roads in a region satisfy the following conditions: every pair of cities is connected by exactly one road, every pair of roads intersects in exactly one city, and every road contains at least two cities.

There are $n = 2071$ roads. How many cities can there be? If the answer is unique, give that value.

ответ

Подсказка / Hint

Заведи матрицу «город — трасса» из нулей и единиц и посмотри, что означают произведения $AA^{T}$ и $A^{T}A$.

Construct a zero-one city–road incidence matrix and interpret the products $AA^{T}$ and $A^{T}A$.

Решение / Solution

Пусть $m$ — число городов. Введём матрицу инцидентности $A$ размера $m \times n$: $A_{ij} = 1$, если через город $i$ проходит трасса $j$, и 0 иначе.

Что означает $AA^{T}$. Элемент $(AA^T)_{ij}$ при $i \ne j$ — это число трасс, общих для городов $i$ и $j$. По условию оно равно 1. На диагонали стоит число трасс через город $i$; обозначим его $d_i$.

Покажем, что $d_i \ge 2$. Сначала $d_i \ge 1$, и это не пустая оговорка: на трассе лежит не меньше двух городов, значит городов всего не меньше двух, а любые два города соединены трассой — стало быть через каждый город проходит хотя бы одна трасса. Остаётся отбросить случай $d_i = 1$. Пусть через город $P$ проходит ровно одна трасса $L$. Любой другой город обязан иметь с $P$ ровно одну общую трассу, а она проходит через $P$, значит это $L$. Выходит, что все города лежат на $L$. Возьмём любую другую трассу $L'$ (трасс 2071, так что она есть): на ней не меньше двух городов, и все они лежат на $L$, то есть $|L \cap L'| \ge 2$ — противоречие с условием «ровно один общий город».

Значит $AA^{T} = J_m + D$, где $J_m$ — матрица из одних единиц, а $D$ — диагональная с элементами $d_i - 1 \ge 1$.

Что означает $A^{T}A$. Симметрично: $(A^TA)_{ij}$ при $i \ne j$ — число общих городов у трасс $i$ и $j$, оно равно 1; на диагонали стоит число городов на трассе $j$, и оно не меньше 2 по условию. Значит $A^{T}A = J_n + D'$ с положительной диагональной добавкой.

Обе матрицы невырождены — это факт из урока: для любого ненулевого $\mathbf{x}$ величина $\mathbf{x}^{T}(J + D)\mathbf{x} = (\sum_i x_i)^2 + \sum_i (d_i - 1)x_i^2$ строго положительна, поэтому нулевого вектора в ядре нет.

Финал. По тождеству из урока

$$\rank(AA^{T}) = \rank A = \rank(A^{T}A)$$

Матрица $AA^T$ имеет размер $m\times m$ и невырождена, значит её ранг равен $m$. Матрица $A^TA$ имеет размер $n \times n$ и невырождена, значит её ранг равен $n$. Но обе они равны $\rank A$. Следовательно $m = n = 2071$.

Ответ: ровно 2071 город — минимум и максимум совпадают.

Такая конфигурация действительно существует

Ответ «$m$ обязан равняться $n$» был бы пустым, если бы подходящих конфигураций не существовало вовсе. Вот явная: один город-центр, одна большая трасса, на которой лежат все остальные 2070 городов, и ещё 2070 коротких трасс, соединяющих центр с каждым из них по отдельности. Трасс ровно $1 + 2070 = 2071$, городов тоже 2071, и оба условия выполнены.

Что забрать на YMLS

Приём «закодируй конфигурацию матрицей и работай с рангом». Комбинаторная задача про города и дороги превратилась в утверждение о ранге — и решилась без единого перебора.

Тождество $\rank(A^{T}A) = \rank A$ стоит запомнить отдельно: оно же лежит в основе метода наименьших квадратов, то есть обучения линейной регрессии. Это ровно та причина, по которой линейная алгебра стоит в программе ML-школы.

Let $m$ be the number of cities. Define the $m \times n$ incidence matrix $A$ by $A_{ij} = 1$ if road $j$ passes through city $i$, and $A_{ij}=0$ otherwise.

Interpret $AA^{T}$. For $i \ne j$, the entry $(AA^T)_{ij}$ is the number of roads shared by cities $i$ and $j$, which is 1 by assumption. The diagonal entry is the number of roads through city $i$; denote it by $d_i$.

We claim that $d_i \ge 2$. First, $d_i \ge 1$. This is not vacuous: every road contains at least two cities, so there are at least two cities in total; every pair of cities is joined by a road, hence at least one road passes through each city. It remains to exclude $d_i = 1$. Suppose exactly one road $L$ passes through a city $P$. Every other city must share exactly one road with $P$, and that road passes through $P$, so it must be $L$. Thus all cities lie on $L$. Now take any other road $L'$; one exists because there are 2071 roads. It contains at least two cities, all of which lie on $L$, so $|L \cap L'| \ge 2$, contradicting the condition that two roads share exactly one city.

Therefore $AA^{T} = J_m + D$, where $J_m$ is the all-ones matrix and $D$ is diagonal with entries $d_i - 1 \ge 1$.

Interpret $A^{T}A$. Symmetrically, for $i \ne j$, $(A^TA)_{ij}$ is the number of cities shared by roads $i$ and $j$, equal to 1. A diagonal entry is the number of cities on road $j$, which is at least 2. Thus $A^{T}A = J_n + D'$ with a positive diagonal correction.

Both matrices are nonsingular. For every nonzero $\mathbf{x}$, $\mathbf{x}^{T}(J + D)\mathbf{x} = (\sum_i x_i)^2 + \sum_i (d_i - 1)x_i^2$ is strictly positive, so the kernel contains no nonzero vector.

Conclusion. By the identity

$$\rank(AA^{T}) = \rank A = \rank(A^{T}A)$$

The matrix $AA^T$ is a nonsingular $m\times m$ matrix, so its rank is $m$. The matrix $A^TA$ is a nonsingular $n \times n$ matrix, so its rank is $n$. Both ranks equal $\rank A$. Hence $m = n = 2071$.

Answer: exactly 2071 cities; the minimum and maximum coincide.

Such a configuration really exists

The conclusion “$m$ must equal $n$” would be empty if no valid configuration existed. Here is one: take one central city, one long road containing all other 2070 cities, and 2070 additional short roads, each joining the center to one of those cities. There are exactly $1 + 2070 = 2071$ roads and 2071 cities, and both conditions are satisfied.

The YMLS takeaway

Use the technique “encode the configuration as a matrix and reason about rank.” A combinatorial problem about cities and roads became a rank statement and was solved without enumeration.

The identity $\rank(A^{T}A) = \rank A$ is worth memorizing. It also underlies the least-squares method used to train linear regression models, which is exactly why linear algebra is part of the ML school curriculum.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S1201Уровень ШАДМатанализОлимпиада ШАД 2025, задача A «Плюс-минус»

Дана интегрируемая функция $f: \mathbb{R} \to \mathbb{R}$ такая, что

$$\int_{-\infty}^{+\infty} f(x)\,dx = 2025$$

Найдите $\displaystyle\int_{-\infty}^{+\infty} f\!\left(x - \frac1x\right)dx$.

Let $f:\mathbb{R}\to\mathbb{R}$ be an integrable function such that

$$\int_{-\infty}^{+\infty} f(x)\,dx = 2025$$

Find $\displaystyle\int_{-\infty}^{+\infty} f\!\left(x - \frac1x\right)dx$.

ответ

Подсказка / Hint

Ответ тот же. Разберись, почему — здесь замена работает не так, как обычно.

The answer is the same. Determine why: the substitution behaves differently from an ordinary one-to-one change of variables.

Решение / Solution

Ответ: 2025.

Идея. Рассмотрим $\varphi(x) = x - \frac1x$. На каждом из промежутков $(-\infty, 0)$ и $(0, +\infty)$ эта функция строго возрастает и отображает промежуток на всю прямую $\mathbb{R}$.

Значит при замене переменной каждая точка $y$ имеет ровно два прообраза — корни уравнения

$$x^2 - yx - 1 = 0$$

Обозначим их $x_1(y)$ и $x_2(y)$. По теореме Виета

$$x_1(y) + x_2(y) = y$$

Продифференцируем это тождество по $y$:

$$x_1'(y) + x_2'(y) = 1$$

Обе ветви возрастают, значит производные положительны и модули можно снять. Тогда

$$\int_{\mathbb{R}} f\!\left(x - \tfrac1x\right)dx = \int_{\mathbb{R}}\big(|x_1'(y)| + |x_2'(y)|\big)f(y)\,dy = \int_{\mathbb{R}} f(y)\,dy = 2025$$

Сверка, которая ловит ошибку в рассуждении

Утверждение проверяется машиной на конкретной $f$ за полминуты: возьми плотность стандартного нормального распределения, умноженную на 2025, и посчитай оба интеграла численно — mpmath.quad по промежуткам $(-\infty, 0)$ и $(0, +\infty)$ отдельно, потому что в нуле подынтегральная функция ведёт себя резко. Числа совпадут. Это не доказательство, но именно так отличают верное рассуждение от красивого.

Что забрать на YMLS

Приём «замена, склеивающая две ветви»: если подстановка неоднозначна, суммируй по всем ветвям — якобианы часто складываются во что-то тривиальное.

В чистом виде такое на YMLS вряд ли придёт. Но родственный приём — симметризация $\int_a^b f(x)dx = \int_a^b f(a+b-x)dx$ из восьмого дня — приходит регулярно, и это тот же ход мысли: не вычислять, а использовать структуру замены.

Answer: 2025.

Idea. Consider $\varphi(x)=x-\frac1x$. On each interval $(-\infty,0)$ and $(0,+\infty)$, this function is strictly increasing and maps the interval onto the entire real line $\mathbb{R}$.

Therefore, under the change of variables, every point $y$ has exactly two preimages: the roots of

$$x^2 - yx - 1 = 0$$

Denote them by $x_1(y)$ and $x_2(y)$. By Vieta's formulas,

$$x_1(y) + x_2(y) = y$$

Differentiate this identity with respect to $y$:

$$x_1'(y) + x_2'(y) = 1$$

Both branches are increasing, so their derivatives are positive and the absolute values can be removed. Hence

$$\int_{\mathbb{R}} f\!\left(x - \tfrac1x\right)dx = \int_{\mathbb{R}}\big(|x_1'(y)| + |x_2'(y)|\big)f(y)\,dy = \int_{\mathbb{R}} f(y)\,dy = 2025$$

A check that catches a flaw in the reasoning

Test the claim computationally with a specific $f$: take the standard normal density multiplied by 2025 and evaluate both integrals numerically. Use mpmath.quad separately on $(-\infty,0)$ and $(0,+\infty)$ because the integrand varies sharply near zero. The results agree. This is not a proof, but it is an effective way to distinguish a correct argument from an attractive but false one.

The YMLS takeaway

Use the technique “a substitution that merges two branches.” When a substitution is not one-to-one, sum over all branches; the Jacobian factors often combine into something simple.

This exact form is unlikely on YMLS. A related method that appears regularly is the symmetrization $\int_a^b f(x)dx = \int_a^b f(a+b-x)dx$ from Day 8. The idea is the same: exploit the structure of the substitution instead of evaluating the integral directly.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S0101Уровень ШАДКомбинаторикаЭкзамен ШАД 2024, задача D «Координаты в квадрате»

На клетчатой бумаге нарисован квадрат $n \times n$ по линиям сетки. Левая нижняя клетка имеет координаты $(1,1)$, правая верхняя — $(n,n)$. Внутри него по линиям сетки рисуют квадрат $(n-1) \times (n-1)$, внутри того — квадрат $(n-2) \times (n-2)$, и так далее, пока не получится квадрат $1 \times 1$. Он оказался клеткой с координатами $(x, y)$.

Сколько существует различных последовательностей квадратов с таким свойством? Дайте ответ для $n = 10$, $x = 4$, $y = 7$.

An $n \times n$ square is drawn along the grid lines of graph paper. The bottom-left cell has coordinates $(1,1)$ and the top-right cell has coordinates $(n,n)$. Inside it, an $(n-1) \times (n-1)$ square is drawn along the grid lines; inside that, an $(n-2) \times (n-2)$ square is drawn, and so on until a $1 \times 1$ square remains. The final square is the cell with coordinates $(x, y)$.

How many different sequences of squares have this property? Give the answer for $n = 10$, $x = 4$, and $y = 7$.

ответ

Подсказка / Hint

Как из квадрата $k \times k$ получается квадрат $(k-1) \times (k-1)$? Сколько у этого шага независимых решений?

How can a $(k-1) \times (k-1)$ square be obtained from a $k \times k$ square? How many independent choices does each step involve?

Решение / Solution

Ключевое наблюдение. Квадрат $(k-1) \times (k-1)$ помещается внутрь квадрата $k \times k$ ровно четырьмя способами: нужно отрезать один столбец — левый или правый — и одну строку — верхнюю или нижнюю. Причём отрезания столбцов и строк независимы.

Всего шагов $n - 1$. На каждом шаге мы отрезаем один столбец (слева или справа) и одну строку (сверху или снизу).

Столбцы. Закодируем историю отрезаний столбцов строкой из $n-1$ символов: Л, если на этом шаге отрезали левый столбец, П — если правый. Если за все $n-1$ шагов слева отрезали $x - 1$ столбец, то финальная клетка имеет первую координату $x$. Строк с ровно $x-1$ буквой Л ровно $\binom{n-1}{x-1}$ — вопрос снова свёлся к «на каких местах стоят символы одного вида».

Строки. Аналогично: $\binom{n-1}{y-1}$.

Любая комбинация даёт свою последовательность, поэтому перемножаем:

$$N = \binom{n-1}{x-1}\binom{n-1}{y-1}$$

Подставляем $n = 10$, $x = 4$, $y = 7$:

$$\binom{9}{3}\binom{9}{6} = 84 \cdot 84 = 7056$$

Что здесь стоит забрать

Приём разделения на независимые оси. Задача выглядела как перебор вложенных квадратов, а свелась к двум независимым строкам — «в каком порядке отрезали столбцы» и «в каком порядке отрезали строки». Как только удаётся расщепить задачу на независимые части, ответ становится произведением. Этот ход встретится ещё много раз.

Key observation. A $(k-1) \times (k-1)$ square can be placed inside a $k \times k$ square in exactly four ways: remove either the left or the right column, and either the top or the bottom row. The choices for rows and columns are independent.

There are $n - 1$ steps in total. At each step, one column (left or right) and one row (top or bottom) are removed.

Columns. Encode the history of column removals by a string of $n-1$ symbols: L if the left column was removed at that step and R if the right column was removed. The final cell has first coordinate $x$ exactly when a total of $x - 1$ columns were removed from the left. The number of strings with exactly $x-1$ occurrences of L is $\binom{n-1}{x-1}$; once again, the problem reduces to choosing the positions occupied by one type of symbol.

Rows. Similarly, there are $\binom{n-1}{y-1}$ possible row-removal histories.

Every pair of histories gives a distinct sequence of squares, so we multiply:

$$N = \binom{n-1}{x-1}\binom{n-1}{y-1}$$

Substituting $n = 10$, $x = 4$, and $y = 7$ gives

$$\binom{9}{3}\binom{9}{6} = 84 \cdot 84 = 7056$$

Main takeaway

Split the problem along independent axes. What looked like a search through nested squares becomes two independent strings: the order in which columns were removed and the order in which rows were removed. Whenever a problem splits into independent parts, the total count is the product of the counts for those parts. This technique will return often.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S0401Уровень ШАДСлучайные величиныОлимпиада ШАД 2025, задача «Инклюзивный марьяж»

Из стандартной колоды в 52 карты вынимают карты по одной без возвращения. Найдите математическое ожидание числа карт, которое нужно вынуть, чтобы среди них оказались и король, и дама. Считается общее число вынутых карт, включая последнюю. Ответ округлите до четырёх знаков после запятой.

Cards are drawn without replacement from a standard 52-card deck. Find the expected number of cards that must be drawn until both a king and a queen have appeared, counting the final card. Round to four decimal places.

ответ

Подсказка / Hint

И «номер первого короля», и «номер первой дамы» считаются леммой о промежутках. Максимум из них напрямую не считается: вспомни тождество $\max + \min = $ сумма и подумай, что такое здесь минимум.

The positions of the first king and the first queen are both handled by the gaps lemma. Their maximum is harder to compute directly: recall the identity $\max + \min = $ sum, and interpret the minimum here.

Решение / Solution

Лемма о промежутках. В колоде из $n$ карт помечены $k$. Среднее число карт, которое нужно вынуть до первой помеченной включительно, равно

$$\E = \frac{n+1}{k+1}$$

Доказательство закольцовыванием — самое короткое из существующих. Добавим сверху ещё одну помеченную карту и замкнём колоду из $n+1$ карты в круг. Случайно повернём круг. Теперь помеченных карт $k+1$, и они разбивают круг на $k+1$ дугу из непомеченных карт. Дуги переходят друг в друга поворотом, значит в среднем одинаковы, и в каждой $\frac{n-k}{k+1}$ карт.

Считая от добавленной карты, до первой настоящей помеченной надо пройти одну дугу и саму помеченную карту:

$$\E = \frac{n-k}{k+1} + 1 = \frac{n+1}{k+1}$$

Решение задачи. Пусть $\xi$ — номер первого короля, $\eta$ — первой дамы. Нужно $\E\max\{\xi, \eta\}$. Максимум напрямую считать тяжело, но выручает тождество

$$\max\{\xi,\eta\} + \min\{\xi,\eta\} = \xi + \eta$$

Здесь $\min\{\xi,\eta\}$ — момент появления первой из восьми выделенных карт (четыре короля и четыре дамы вместе). Все три величины считаются по лемме:

$$\E\xi = \E\eta = \frac{52+1}{4+1} = \frac{53}{5}, \qquad \E\min = \frac{52+1}{8+1} = \frac{53}{9}$$$$\E\max = \frac{53}{5} + \frac{53}{5} - \frac{53}{9} = \frac{689}{45} \approx 15.3111$$

Что забрать на YMLS

Два приёма, каждый из которых работает далеко за пределами этой задачи.

Первый — лемма $\frac{n+1}{k+1}$. Закрывает целый класс задач «сколько тянуть до первого нужного». В малом размере ты вывел её индикаторами в задаче b0405, здесь она применена трижды подряд — к королям, к дамам и к восьми картам сразу.

Второй — тождество $\max + \min$. Если максимум считать трудно, а минимум легко, считай минимум и вычитай. Это общий приём, а не трюк для карт: сегодня он уже работал в задаче про два кубика и в задаче про две равномерные точки.

Gaps lemma. In a deck of $n$ cards, suppose $k$ are marked. The expected number of cards drawn up to and including the first marked card is

$$\E = \frac{n+1}{k+1}$$

Circular proof. Add one marked card to the top and join the $n+1$ cards into a circle, then rotate the circle uniformly at random. The $k+1$ marked cards divide the circle into $k+1$ gaps of unmarked cards. Rotation permutes these gaps, so they have the same expected size, $\frac{n-k}{k+1}$.

Starting from the added card, reaching the first original marked card requires crossing one gap and then drawing the marked card itself:

$$\E = \frac{n-k}{k+1} + 1 = \frac{n+1}{k+1}$$

Apply the lemma. Let $\xi$ be the position of the first king and $\eta$ the position of the first queen. We need $\E\max\{\xi,\eta\}$. Use

$$\max\{\xi,\eta\} + \min\{\xi,\eta\} = \xi + \eta$$

Here $\min\{\xi,\eta\}$ is the position of the first among eight marked cards: the four kings and four queens together. The lemma gives

$$\E\xi = \E\eta = \frac{52+1}{4+1} = \frac{53}{5}, \qquad \E\min = \frac{52+1}{8+1} = \frac{53}{9}$$$$\E\max = \frac{53}{5} + \frac{53}{5} - \frac{53}{9} = \frac{689}{45} \approx 15.3111$$

What to carry into YMLS

Two techniques here apply far beyond this problem.

First, the $\frac{n+1}{k+1}$ gaps lemma. It resolves an entire class of “how many draws until the first target?” questions. You derived its small version using indicators in b0405; here it is applied three times—to kings, queens, and all eight marked cards.

Second, the identity $\max + \min$. When the maximum is hard and the minimum easy, compute the minimum and subtract. This is a general method, not a card trick; it already appeared in the problems about two dice and two uniform variables.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

S0301Уровень ШАДВероятностьпарадокс Гарднера, уровень ШАД

У человека двое детей. Известно, что хотя бы один из них — мальчик, родившийся во вторник. Найдите вероятность того, что оба ребёнка мальчики.

Считайте, что пол и день недели каждого ребёнка независимы, все семь дней и оба пола равновероятны. Ответ округлите до четырёх знаков после запятой.

A person has two children. It is known that at least one is a boy born on Tuesday. Find the probability that both children are boys.

Assume that each child's sex and day of birth are independent, with all seven days and both sexes equally likely. Round the answer to four decimal places.

ответ

Подсказка / Hint

Опиши каждого ребёнка парой «пол, день недели». Сколько всего таких пар и сколько комбинаций для двоих детей?

Describe each child by the pair “sex, day of the week.” How many such pairs are possible, and how many combinations are there for two children?

Решение / Solution

Каждый ребёнок описывается парой (пол, день недели) — всего $2 \cdot 7 = 14$ равновозможных вариантов. Для двоих детей: $14^2 = 196$ исходов.

Знаменатель — исходы, где есть мальчик-вторник. Считаем дополнением. Исходы, где мальчика-вторника нет: каждый ребёнок — один из $14 - 1 = 13$ прочих вариантов, то есть $13^2 = 169$. Значит подходящих $196 - 169 = 27$.

Числитель — оба мальчики и хотя бы один родился во вторник. Всего пар мальчиков $7^2 = 49$. Из них без вторника $6^2 = 36$. Остаётся $49 - 36 = 13$.

$$\P = \frac{13}{27} \approx 0.4815$$

Почему это ломает интуицию

Три условия про одну и ту же семью дают три разных ответа: «старший — мальчик» даёт $\frac12$ (задача w0302), «хотя бы один мальчик» — $\frac13$ (задача w0303), «хотя бы один мальчик, рождённый во вторник» — $\frac{13}{27} \approx 0.48$.

Казалось бы, день недели — посторонняя деталь, а ответ меняется. Причина: она меняет пространство исходов. Никакого словесного правила «чем подробнее условие, тем ответ ближе к $\frac12$» при этом нет: условие «хотя бы один мальчик, родившийся в понедельник или во вторник» тоже подробное, а даёт $\frac{49 - 5^2}{196 - 12^2} = \frac{24}{52} = \frac{6}{13} \approx 0.4615$ — меньше, чем один вторник. Ряд $\frac13$, $\frac{6}{13}$, $\frac{13}{27}$, $\frac12$ выстраивается только счётом, а в уроке стоит контрпример, где адресное условие роняет ответ до нуля.

Мораль для экзамена одна: выписывай $\Omega$ полностью и считай, а не рассуждай словами. В этой теме словесная интуиция подводит систематически.

Each child is described by a pair (sex, day of the week), giving $2 \cdot 7 = 14$ equally likely possibilities. Two children therefore produce $14^2 = 196$ outcomes.

Denominator—outcomes with a Tuesday-born boy. Use the complement. If there is no Tuesday-born boy, each child has one of the other $14 - 1 = 13$ descriptions, giving $13^2 = 169$ outcomes. Thus the condition leaves $196 - 169 = 27$ outcomes.

Numerator—both are boys and at least one was born on Tuesday. There are $7^2 = 49$ pairs of boys, of which $6^2 = 36$ contain no Tuesday birth. This leaves $49 - 36 = 13$.

$$\P = \frac{13}{27} \approx 0.4815$$

Why intuition fails here

Three conditions about the same family produce three different answers: “the older child is a boy” gives $\frac12$ (w0302), “at least one child is a boy” gives $\frac13$ (w0303), and “at least one is a boy born on Tuesday” gives $\frac{13}{27} \approx 0.48$.

The weekday may look irrelevant, but it changes the sample space. There is no verbal rule saying that a more detailed condition makes the answer closer to $\frac12$. For example, “at least one boy born on Monday or Tuesday” gives $\frac{49 - 5^2}{196 - 12^2} = \frac{24}{52} = \frac{6}{13} \approx 0.4615$, less than the Tuesday-only answer. The sequence $\frac13$, $\frac{6}{13}$, $\frac{13}{27}$, $\frac12$ emerges only from counting; the lesson even contains a counterexample where a condition specifying a particular child drives the answer to zero.

The exam lesson is simple: write out $\Omega$ completely and count instead of reasoning verbally. Verbal intuition is systematically unreliable in this topic.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок

Y1504Уровень YMLSСтатистикаавторская

Независимая одинаково распределённая выборка: $2,0,3,2$. Закон $P(X=k)=p(1-p)^{k}$, $k=0,1,\ldots$, $0<p\le1$. Постройте $L$, найдите MLE параметра $p$ и обоснуйте максимум.

Ответ округлите до четырёх знаков после запятой.

An i.i.d. sample is $2,0,3,2$. The model is $P(X=k)=p(1-p)^{k}$, $k=0,1,\ldots$, $0<p\le1$. Construct $L$, find the MLE of $p$, and justify the maximum.

Round your answer to four decimal places.

ответ

Подсказка / Hint

Запишите отдельно число успехов и суммарное число неудач. Затем проверьте границы области параметра.

Write down the number of successes and the total number of failures separately. Then check the parameter boundaries.

Решение / Solution

$L(p)=p^{4}(1-p)^{7}$; $\ell(p)=4\ln p+7\ln(1-p)$. $\ell\prime(p)=4/p-7/(1-p)=0$, $\hat p=4/11=0.3636$.

$\ell\prime\prime(p)=-4/p^2-7/(1-p)^2<0$: логарифм строго вогнут, поэтому стационарная точка — единственный максимум. Она лежит в $(0,1)$; на обоих концах $L$ стремится к нулю. В показателе $(1-p)$ считаем неудачи, а не все попытки.

$L(p)=p^{4}(1-p)^{7}$; $\ell(p)=4\ln p+7\ln(1-p)$. $\ell\prime(p)=4/p-7/(1-p)=0$, $\hat p=4/11=0.3636$.

$\ell\prime\prime(p)=-4/p^2-7/(1-p)^2<0$: the log-likelihood is strictly concave, so the stationary point is the unique maximum. It lies in $(0,1)$; at both ends $L$ tends to zero. The exponent of $(1-p)$ counts failures, not all trials.

уверенность1 — угадал, 5 — уверен полностью

В журнал ошибок