Ответ на Задачу о повторяющихся паролях
Недельку назад я опубликовал задачку о карточках и их кодах.
Надо сказать, что условие было нарочито запутано, и всё, что требовалось от решения - провести аналогию с одним известным и давно изученным явлением. Собственно, задача не заслуживает не только моей фамилии, но даже просто собственного названия.
РЕШЕНИЕ:
Итак, что мы имеем. Подразумевается, что пара «карточка-код» выбирается абсолютно случайно, и никто никаким способом не может заранее сказать, какой карточке будет соответствовать какой код. Таким образом, получается, что описанная в задаче ситуация - не что иное, как самая обыкновенная, давным-давно всем известная рулетка. В роли колеса тут выступает набор используемых кодов, взломщики - игроки, а бросок шарика - собственно, проба кода к конкретной карточке.
Обозначив общее количество кодов-секторов рулетки через n, n < 10 000, получаем количество карточек a > n4, а взяв карточки всех систем - a >> (много больше) n4. То есть общее количество вращений рулетки на много порядков превышает количество равновероятных исходов (для обычной 37-секторной рулетки это почти два миллиона спинов, что составляет без малого год круглосуточной работы четырёхрулеточного казино, из расчёта по одному броску в минуту).
Теперь же начнём с простого. Хотя существует некая вероятность, что код второго взломщика подходит только к одной лишь его собственной карточке, на практике количество нулей после запятой в числе, описывающем эту вероятность, неприлично велико. Гораздо более вероятно, что, поскольку на бесконечном промежутке (a → ∞) число b карточек с одним и тем же кодом (независимо от этого кода) будет описываться соотношением b = a / n, то, раз у нас конечное a >> n4, b получается много больше n4 / n, то есть b >> n3.
Теперь о двух других взломщиках.
Как нас учит теория вероятностей, количество конкретных исходов случайного события для бесконечного количества измерений стремится к числу, равному для каждого из исходов, что мы уже эмпирически доказали выше, то есть, опять же, b = a / n при a → ∞. Зачем я повторил эту формулу? А дело в том, что в ней нет упоминаний о том, по какой схеме игроки делают ставки пробуют коды. Улавливаете? Практика игры в рулетку подтверждает, что независимо от схемы ставок выигрывает каждая 37-я, и только из-за наличия «зеро» и хитрой системы выплат казино не остаётся внакладе.
У нас в точности та же самая ситуация.
Каждый взломщик вскроет b >> n3 карточек, а конкретные числа (промежуток a конечен, следовательно, на нём возможны любые флуктуации) зависит только от их везения.
ОТВЕТ:
Примерно одинаково, близко к отношению количества карточек к количеству кодов к ним b = a / n.