Как проводить взвешивания, чтобы гарантированно найти хотя бы одну настоящую монету

Сообщения: 1 🔎

# 4 Июн 2016 20:20:32
Math

У нумизмата имеется некоторое количество одинаковых по внешнему виду монет, среди которых есть и настоящие, и фальшивые. Он знает, что массы всех настоящих монет одинаковые, а массы всех фальшивых — разные, причем любая фальшивая монета тяжелее настоящей. Но точные массы монет он не знает. Также известно общее количество монет и сколько среди них фальшивых. У нумизмата есть двухчашечные весы без гирь, на чашки которых можно класть любое число монет.

Помогите нумизмату: придумайте, как ему нужно проводить взвешивания, чтобы гарантированно найти хотя бы одну настоящую монету и при этом обойтись как можно меньшим числом взвешиваний. Алгоритм должен одинаково хорошо работать для любого числа монет. Например, если всего монет пять и две из них фальшивые. Или если всего монет 100 и 70 из них фальшивые. Для первого случая (когда всего пять монет и две из них фальшивые) докажите, что меньшим числом взвешиваний обойтись нельзя.

[−] Решение

Чтобы найти настоящую монету, нумизмату следует действовать так. Нужно смешать все монеты в одну кучу, а затем для каждого взвешивания выбирать из этой кучи две монеты и сравнивать их. Если массы монет окажутся равны, то обе они — настоящие. Если одна монета окажется тяжелее, то она точно фальшивая и ее можно выбросить из кучи. Действуя таким образом, мы после очередного взвешивания либо находим настоящую монету (точнее, даже две), либо уменьшаем число «подозрительных» монет на одну. Поскольку их количество известно, то взвешиваний понадобится не больше, чем это количество. (В принципе, если на весах каждый раз было неравенство, то в конце в куче останутся только настоящие монеты — нумизмат найдет их все сразу.)

Тем самым, для первого случая из условия (когда монет пять и две из них фальшивые) понадобится не больше двух взвешиваний, а для второго (когда монет 100 и 70 из них фальшивые) — не больше 70 взвешиваний. Отметим, что в таком варианте эта задача предлагалась на заключительном этапе Всероссийской олимпиаде школьников по математике в этом году. Авторы задачи — Илья Богданов и Сергей Берлов. Участникам олимпиады, естественно, нужно было доказывать оптимальность алгоритма взвешивания.

Сделаем это и мы. То есть докажем, что не существует алгоритма взвешивания, которому всегда будет достаточно меньше взвешиваний чем количество фальшивых монет в куче. Проделаем это для более простого случая, когда монет всего пять и две из них фальшивые.

Допустим, существует способ, который позволяет всегда найти в этой ситуации фальшивую монету за одно взвешивание. Пусть настоящие монеты весят по 8 грамм, а фальшивые весят 9 и 10 грамм. Ясно, что взвешивать нужно только одинаковое число монет, потому что если на одну чашу весов положить больше монет, чем на другую, то первая точно перевесит вне зависимости от того, какие монеты где лежат. То есть взвешивание разного числа монет не дает никакой информации. Далее, заметим, что если на чашках весов лежит одинаковое число монет, то перевесит та чашка, на которой лежит более тяжелая монета. А тогда получается, что за одно взвешивание невозможно отличить ситуацию (Н, Ф₉) от ситуаций (Н, Ф₁₀) и (Ф₉, Ф₁₀), если взвешивается по одной монете (здесь буквой Н обозначена настоящая монета, Ф₉ — фальшивая монета весом 9 грамм, Ф₁₀ — фальшивая монета весом 10 грамм, пара в скобках — то, что лежит на чашах весов). А если взвешивается по две монеты, то результатом всегда будет неравенство (ведь у нас нет четырех одинаковых монет), то есть такое взвешивание вообще не дает информации. Значит, гарантированно указать на настоящую монету нельзя — любая монета на любой чаше может быть фальшивой.

[−] Послесловие

Для случая с сотней монет доказательство того, что меньше чем за 70 взвешиваний гарантированно определить настоящую не получится, аналогично разобранному в решении случаю (и для любого другого числа монет все тоже аналогично), но немного сложнее. Точно так же выбирается специальный набор монет, с которым любой алгоритм взвешивания не справится быстрее, чем написано в решении. Таких наборов много. Подойдет, например, такой: все настоящие монеты весят по 2100, а i-я фальшивая весит m_i = 2¹⁰⁰ + 2ⁱ. Аналогично решению показывается, что имеет смысл класть только одинаковое число монет на чашки весов и что перевешивать будет чашка с самой тяжелой (и имеющей наибольший номер) монетой. Пусть нумизмату это все даже известно. Допустим, что у него все-таки есть алгоритм, который позволит за 69 действий определить настоящую монету.

Итак, пусть нумизмат действует по своему алгоритму. Рассмотрим Соперника, который сообщает нумизмату результаты взвешиваний и одновременно присваивает некоторым монетам массы m_i, начиная с m₇₀ и последовательно уменьшая индекс i. При этом Соперник действует по собственному алгоритму:
1) если на весах уже есть монета с присвоенной массой, то из всех таких монет Соперник выбирает массу с наибольшим номером и сообщает, что чаша с этой массой перевесила;
2) если на весах нет монет с присвоенной массой, то Соперник выбирает любую монету, присваивает ей очередную массу и сообщает, что чаша с этой массой перевесила.

Так как этот алгоритм полностью согласуется с доказанным выше свойством «чаша с наибольшим номером монеты всегда тяжелее», то он не приведет ни к каким противоречиям.

После 69 проведенных взвешиваний присвоенными окажутся не более 69 масс. В частности, масса m₁ точно не присвоена, и такую массу может иметь любая из монет, которой еще не присвоена масса. Иначе говоря, любая из остальных монет может оказаться фальшивой. Следовательно, после 69 взвешиваний нумизмат не сможет указать гарантированно настоящую монету, что и требовалось доказать

В этой, как и очень многих других алгоритмических задачах, основную трудность в анализе алгоритма представляет не доказательство его правильности, а доказательство оптимальности, то есть невозможности улучшить данный алгоритм. И вот в таких задачах рассмотрение алгоритма виртуального Соперника (которому на самом деле все равно, против какого алгоритма действий бороться) является очень мощным и полезным приемом. Приведем еще два примера использования этого приема.

Пример 1
За какое наименьшее число взвешиваний можно найти самую легкую и самую тяжелую из 100 монет различной массы?

Ответ в этой задаче равен 148, и алгоритм действий хорошо известен:
1) 100 монет разбиваются на пары и сравниваются монеты в каждой паре друг с другом — это 50 взвешиваний;
2) Среди 50 более тяжелых монет ищется самая тяжелая — это еще 49 взвешиваний;
3) Среди 50 более легких монет ищется самая легкая — это еще 49 взвешиваний.

Итого 50 + 49 + 49 = 148.

Докажем, что быстрее невозможно. Рассмотрим Соперника, который действует против любого Алгоритма взвешиваний следующим образом. Соперник помечает знаком «+» каждую монетку, которая может оказаться самой тяжелой, и знаком «−» каждую монетку, которая может быть самой легкой. Вначале каждая монетка помечена дважды, то есть всего есть 200 пометок. В конце пометка «+» должна остаться всего у одной монеты, и пометка «−» тоже должна остаться только одна. Значит, по ходу действия алгоритма должны быть стерты 198 пометок. Осталось разобраться, как именно Соперник их стирает. Для этого опишем действия Соперника:
(1) Если Алгоритм пробует сравнить две дважды помеченные монетки, то Соперник произвольно назначает одну из них более тяжелой и стирает у нее «−», а другую назначает более легкой и стирает у нее «+».
(2) Во всех остальных случаях Соперник действует так, чтобы стирать не более одной пометки. Например, если Алгоритм сравнивает монету с двумя пометками и монету с одной пометкой «−», то Соперник сохраняет пометку «−» у второй монеты и стирает ее у первой, то есть объявляет, что первая монета оказалась тяжелее второй.

Действий типа (1) не может быть более 50, так как каждое из них уменьшает число дважды помеченных монет на 2, а всего таких монет было 100. Действия типа (2) стирают не более одной пометки. Поскольку нам нужно стереть всего 198 пометок, а действиями типа (1) можно стереть не более 100, то требуется не менее 98 действий типа (2), а всего — не менее 148 взвешиваний.

Пример 2
Некоторые из шести людей знакомы друг с другом. Сведения о знакомствах хранятся в компьютере. За один запрос к компьютеру мы можем узнать, знакомы ли между собой два конкретных человека. Мы хотим узнать, найдутся ли среди этих людей трое попарно знакомых. Требуется доказать, что не существует алгоритма, делающего это быстрее чем за 10 запросов.

Доказательство такое. Рассмотрим за Компьютер (в данном случае он выступает в роли Соперника) такой граф знакомств: один человек — назовем его A — знаком со всеми остальными, а все остальные пары людей Соперник пока считает незнакомыми. Если Алгоритм спрашивает про знакомство А с кем-либо, Соперник отвечает «да», а если Алгоритм спрашивает про знакомство двух других людей, то Соперник отвечает «нет».

Если Алгоритм не задавал вопроса о знакомстве между B и С, а в итоге сообщил, что тройки попарно знакомых нет, то Соперник тут же объявит B и C знакомыми и предъявит контрпример, в котором такая тройка (A, B, C) есть. Если же Алгоритм не задавал такого вопроса и в итоге сообщил, что тройка попарно знакомых есть, то Соперник тут же объявит все пары, не содержащие А, незнакомыми, и тоже предъявит эту ситуацию как контрпример. Итак, чтобы контрпримера не было, Алгоритм должен запросить знакомство для всех пар (B, C), которых ровно 10, — то есть сделать не менее 10 запросов. (В данном случае мы не обещаем, что и 10 запросов хватит, поскольку не предъявляем никакого подходящего алгоритма.)

Цитировать

Сообщения: 1 🔎


*Имя:
Заголовок:
[tex-clear] [tex-help] [ted] formulas > Формат Шрифт $\mathit{}$ $\mathbf{}$ $\mathrm{}$ $\mathsf{}$ $\mathfrak{}$ $\mathbb{}$ $\mathcal{}$ $\mathscr{}$ Размер $\tiny Aa$ $\scriptsize Aa$ $\footnotesize Aa$ $\small Aa$ $\normalsize Aa$ $\large Aa$ $\Large Aa$ $\LARGE Aa$ $\huge Aa$ $\Huge Aa$ Цвет ${\color{Red} }$ ${\color{DarkRed} }$ ${\color{BrickRed} }$ ${\color{Magenta} }$ ${\color{VioletRed} }$ ${\color{Yellow} }$ ${\color{Orange} }$ ${\color{DarkOrange} }$ ${\color{Brown} }$ ${\color{Sepia} }$ ${\color{Green} }$ ${\color{DarkGreen} }$ ${\color{ForestGreen} }$ ${\color{Teal} }$ ${\color{Emerald} }$ ${\color{Blue} }$ ${\color{DarkBlue} }$ ${\color{RoyalBlue} }$ ${\color{BlueViolet} }$ ${\color{Purple} }$ ${\color{Gray} }$ ${\color{Plum} }$ ${\color{Cyan} }$ Стиль \text{} $\tstyle$ $\dstyle$ Дроби, корни $\frac{}{}$ $\tfrac{}{}$ $\dfrac{}{}$ $\cfrac{}{}$ $\over$ $\atop$ $\sqrt{}$ $\sqrt[]{}$ $\binom{}{}$ $\tbinom{}{}$ Скобки $()$ $\{\}$ $[]$ $\|\|$ $\\|\\|$ $\langle \rangle$ $\left( \right)$ $\left\{ \right\}$ $\left[ \right]$ $\left\| \right\|$ $\left\\| \right\\|$ $\left\langle \right\rangle$ $\left( \right.$ $\left. \right)$ $\left\{ \right.$ $\left. \right\}$ $\left[ \right.;$ $\left. \right]$ $\left\| \right.;$ $\left. \right\|$ Декор., индексы $^{}$ $_{}$ $^{}_{}$ ${}^{}$ ${}_{}$ ${}^{}_{}$ $\leftidx{}{}{}$ $\ltrans{}$ $\vec{}$ $\bar{}$ $\tilde{}$ $\hat{}$ $\dot{}$ $\ddot{}$ $\dddot{}$ $^{\circ}$ $\overset{\circ}{}$ $\overset{\frown}{}$ $\overrightarrow{}$ $\overleftarrow{}$ $\overline{}$ $\underline{}$ $\widetilde{}$ $\widehat{}$ $\overbrace{}^{}$ $\underbrace{}_{}$ $\overset{}{}$ $\underset{}{}$ $\left. \right\|_{}^{}$ $\left. \right\|_{}$ $\not{}$ $\cancel{}$ $\bcancel{}$ $\xcancel{}$ Пробелы, разд. $\!$ $x y$ $\,$ $\;$ $\$ $\quad$ $\qquad$ $\cdot$ $\dots$ $\cdots$ $\ddots$ $\vdots$ $\colon$ $\mid$ \phantom{} \mathstrut{} Квант., операц. $\forall$ $\exists$ $\exists!$ $\nexists$ $\lnot$ $\land$ $\lor$ $\cup$ $\cap$ $\sqcup$ $\sqcap$ $\setminus$ $\bigtriangleup$ $\uplus$ $\cdot$ $\circ$ $\times$ $\pm$ $\mp$ $\dotplus$ $\div$ $/$ $\neg$ $\wedge$ $\vee$ $\barwedge$ $\veebar$ $\curlywedge$ $\curlyvee$ $\textasciicircum$ $\oplus$ $\ominus$ $\otimes$ $\oslash$ $\odot$ $\circledcirc$ $\circledast$ Отношения $\in$ $\notin$ $\ni$ $\not\ni$ $\subset$ $\supset$ $\not\subset$ $\not\supset$ $\subseteq$ $\supseteq$ $\nsubseteq$ $\nsupseteq$ $\subsetneq$ $\supsetneq$ $\subsetneqq$ $\supsetneqq$ $\neq$ $\approx$ $\equiv$ $\not\equiv$ $\sim$ $\nsim$ $\cong$ $\ncong$ $\leqslant$ $\geqslant$ $\nleqslant$ $\ngeqslant$ $\le$ $\ge$ $\nleq$ $\ngeq$ $\nless$ $\ngtr$ $\lneq$ $\gneq$ $\lneqq$ $\gneqq$ $\ll$ $\gg$ $\prec$ $\succ$ $\nprec$ $\nsucc$ $\preceq$ $\succeq$ $\npreceq$ $\nsucceq$ $:=$ $\overset{\mathrm{def}}{=}$ $\triangleq$ $\models$ $\vdash$ $\dashv$ $\mid$ $\nmid$ $\mathop{\vdots}$ $\mathop{\not\vdots}$ $\parallel$ $\nparallel$ $\perp$ $\not\perp$ Большие операт. $\sum_{}^{}$ $\sum_{}$ $\prod_{}^{}$ $\prod_{}$ $\bigcup_{}^{}$ $\bigcup_{}$ $\bigcap_{}^{}$ $\bigcap_{}$ $\bigsqcup_{}^{}$ $\biguplus_{}^{}$ $\bigvee_{}^{}$ $\bigwedge_{}^{}$ $\bigoplus_{}^{}$ $\bigotimes_{}^{}$ $\bigodot_{}^{}$ Стрелки $\to$ $\mapsto$ $\rightarrow$ $\leftarrow$ $\leftrightarrow$ $\nrightarrow$ $\nleftarrow$ $\nleftrightarrow$ $\Rightarrow$ $\Leftarrow$ $\Leftrightarrow$ $\nRightarrow$ $\nLeftarrow$ $\nLeftrightarrow$ $\Uparrow$ $\Downarrow$ $\Updownarrow$ $\rightrightarrows$ $\longmapsto$ $\longrightarrow$ $\longleftarrow$ $\longleftrightarrow$ $\uparrow$ $\downarrow$ $\updownarrow$ $\Longrightarrow$ $\Longleftarrow$ $\Longleftrightarrow$ $\implies$ $\iff$ $\rightleftarrows$ $\nearrow$ $\swarrow$ $\nwarrow$ $\searrow$ $\circlearrowleft$ $\circlearrowright$ $\curvearrowleft$ $\curvearrowright$ $\xrightarrow[]{}$ $\xleftarrow[]{}$ Буквы, значки Греческие $\Gamma$ $\Delta$ $\Theta$ $\Lambda$ $\Xi$ $\Pi$ $\Sigma$ $\Upsilon$ $\Phi$ $\Psi$ $\Omega$ $\digamma$ $\alpha$ $\beta$ $\gamma$ $\delta$ $\epsilon$ $\varepsilon$ $\zeta$ $\eta$ $\theta$ $\vartheta$ $\iota$ $\kappa$ $\varkappa$ $\lambda$ $\mu$ $\nu$ $\xi$ $\pi$ $\varpi$ $\rho$ $\varrho$ $\sigma$ $\varsigma$ $\tau$ $\upsilon$ $\phi$ $\varphi$ $\chi$ $\psi$ $\omega$ Резные $\mathbb{A}$ $\mathbb{B}$ $\mathbb{C}$ $\mathbb{D}$ $\mathbb{E}$ $\mathbb{F}$ $\mathbb{G}$ $\mathbb{H}$ $\mathbb{I}$ $\mathbb{J}$ $\mathbb{K}$ $\mathbb{L}$ $\mathbb{M}$ $\mathbb{N}$ $\mathbb{O}$ $\mathbb{P}$ $\mathbb{Q}$ $\mathbb{R}$ $\mathbb{S}$ $\mathbb{T}$ $\mathbb{U}$ $\mathbb{V}$ $\mathbb{W}$ $\mathbb{X}$ $\mathbb{Y}$ $\mathbb{Z}$ Калиграф. $\mathcal{A}$ $\mathcal{B}$ $\mathcal{C}$ $\mathcal{D}$ $\mathcal{E}$ $\mathcal{F}$ $\mathcal{G}$ $\mathcal{H}$ $\mathcal{I}$ $\mathcal{J}$ $\mathcal{K}$ $\mathcal{L}$ $\mathcal{M}$ $\mathcal{N}$ $\mathcal{O}$ $\mathcal{P}$ $\mathcal{Q}$ $\mathcal{R}$ $\mathcal{S}$ $\mathcal{T}$ $\mathcal{U}$ $\mathcal{V}$ $\mathcal{W}$ $\mathcal{X}$ $\mathcal{Y}$ $\mathcal{Z}$ Рукописные $\mathscr{A}$ $\mathscr{B}$ $\mathscr{C}$ $\mathscr{D}$ $\mathscr{E}$ $\mathscr{F}$ $\mathscr{G}$ $\mathscr{H}$ $\mathscr{I}$ $\mathscr{J}$ $\mathscr{K}$ $\mathscr{L}$ $\mathscr{M}$ $\mathscr{N}$ $\mathscr{O}$ $\mathscr{P}$ $\mathscr{Q}$ $\mathscr{R}$ $\mathscr{S}$ $\mathscr{T}$ $\mathscr{U}$ $\mathscr{V}$ $\mathscr{W}$ $\mathscr{X}$ $\mathscr{Y}$ $\mathscr{Z}$ Готические $\mathfrak{A}$ $\mathfrak{B}$ $\mathfrak{C}$ $\mathfrak{D}$ $\mathfrak{E}$ $\mathfrak{F}$ $\mathfrak{G}$ $\mathfrak{H}$ $\mathfrak{I}$ $\mathfrak{J}$ $\mathfrak{K}$ $\mathfrak{L}$ $\mathfrak{M}$ $\mathfrak{N}$ $\mathfrak{O}$ $\mathfrak{P}$ $\mathfrak{Q}$ $\mathfrak{R}$ $\mathfrak{S}$ $\mathfrak{T}$ $\mathfrak{U}$ $\mathfrak{V}$ $\mathfrak{W}$ $\mathfrak{X}$ $\mathfrak{Y}$ $\mathfrak{Z}$ $\mathfrak{a}$ $\mathfrak{b}$ $\mathfrak{c}$ $\mathfrak{d}$ $\mathfrak{e}$ $\mathfrak{f}$ $\mathfrak{g}$ $\mathfrak{h}$ $\mathfrak{i}$ $\mathfrak{j}$ $\mathfrak{k}$ $\mathfrak{l}$ $\mathfrak{m}$ $\mathfrak{n}$ $\mathfrak{o}$ $\mathfrak{p}$ $\mathfrak{q}$ $\mathfrak{r}$ $\mathfrak{s}$ $\mathfrak{t}$ $\mathfrak{u}$ $\mathfrak{v}$ $\mathfrak{w}$ $\mathfrak{x}$ $\mathfrak{y}$ $\mathfrak{z}$ Значки $\varnothing$ $\infty$ $\partial$ $\aleph$ $\mathfrak{c}$ $\ell$ $\hbar$ $\O$ $\bot$ $\top$ $\angle$ $\measuredangle$ $\sphericalangle$ $\frown$ $\smile$ $\vartriangle$ $\triangledown$ $\blacktriangle$ $\blacktriangledown$ $\triangleleft$ $\triangleright$ $\blacktriangleleft$ $\blacktriangleright$ $\triangle$ $\square$ $\blacksquare$ $\bigcirc$ $\star$ $\bigstar$ $\bullet$ $\diamond$ $\textasciicircum$ $\therefore$ $\because$ $\&$ $\%$ $\S$ $\P$ $\backslash$ Функции, операт. Станд. функц. $\max_{}$ $\min_{}$ $\sup_{}$ $\inf_{}$ $\Pr_{}$ $\operatorname{sign}$ $\deg$ $\arg$ $\operatorname{НОД}$ $\operatorname{НОК}$ $\operatorname{Im}$ $\operatorname{Re}$ $\dim$ $\ker$ $\hom$ $\operatorname{diag}$ $\operatorname{rank}$ $\det$ $\operatorname{tr}$ $\operatorname{spec}$ $\mathsf{P}$ $\mathsf{M}$ $\mathsf{D}$ $\Im$ $\Re$ \operatorname{} Элем. функц. $\exp$ $\log_{}$ $\ln$ $\lg$ $\sin$ $\cos$ $\tg$ $\ctg$ $\arcsin$ $\arccos$ $\arctg$ $\arcctg$ $\sh$ $\ch$ $\th$ $\cth$ Пределы $\lim_{n\to\infty}$ $\lim_{x\to }$ $lim_{}$ $\limsup_{n\to\infty}$ $\liminf_{n\to\infty}$ $\varlimsup_{n\to\infty}$ $\varliminf_{n\to\infty}$ $\to$ $\rightrightarrows$ $\infty$ Дифф. опер. $\mathrm{d}$ $\partial$ $\frac{\mathrm{d} }{\mathrm{d} x}$ $\frac{\partial }{\partial x}$ $\frac{\partial^2 }{\partial x^2}$ $\nabla$ $\Delta$ $\operatorname{grad}$ $\operatorname{div}$ $\operatorname{rot}$ Интегралы $\int$ $\int_{}^{}$ $\int\limits_{}^{}$ $\int_{}$ $\int\limits_{}$ $\oint$ $\oint_{}$ $\oint\limits_{}$ $\ointctrclockwise$ $\ointclockwise$ $\iint$ $\iint_{}$ $\iint\limits_{}$ $\oiint$ $\oiint_{}$ $\oiint\limits_{}$ $\varoiint$ $\sqiint$ $\iiint$ $\iiint_{}$ $\iiint\limits_{}$ $\dotsint$ $\dotsint_{}$ $\dotsint\limits_{}$ Сравнения $\equiv$ $\mod{}$ $\pmod{}$ $\pod{}$ Матрицы $\begin{matrix} & \\ & \end{matrix}$ $\begin{pmatrix} & \\ & \end{pmatrix}$ $\begin{vmatrix} & \\ & \end{vmatrix}$ $\begin{Vmatrix} & \\ & \end{Vmatrix}$ $\begin{bmatrix} & \\ & \end{bmatrix}$ $\begin{Bmatrix} & \\ & \end{Bmatrix}$ $\left\{\begin{matrix} & \\ & \end{matrix}\right.$ $\left[\begin{matrix} & \\ & \end{matrix}\right.$ $\left.\begin{matrix} & \\ & \end{matrix}\right\}$ $\left.\begin{matrix} & \\ & \end{matrix}\right\|$ $\left(\begin{smallmatrix} & \\ & \end{smallmatrix}\right)$ $\binom{}{}$ $\tbinom{}{}$ Спец. блоки $\begin{cases} & \\ & \end{cases}$ $\begin{aligned} & \\ & \end{aligned}$ $\begin{align} & \tag{} \\ & \tag{} \end{align}$ $\begin{tikzpicture} \end{tikzpicture}$ $\ce{}$
Преобразовать url в ссылки Преобразовать $ в tex
* Сколько символов на картинке?
Отправляя данные, вы соглашаетесь с Правилами сайта.

∀ x, y, z

Как проводить взвешивания, чтобы гарантированно найти хотя бы одну настоящую монету