\documentclass[10pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage{amsmath,amsthm,amsfonts,amssymb}
\usepackage[dvips]{epsfig}
\usepackage[russian]{babel}
\usepackage{ifthen}

\pagestyle{plain}
\topmargin=-1.2in
\textheight=10.8in
\oddsidemargin=-0.3in
\textwidth=7in
\footskip=14pt

\makeatletter

\newenvironment{df}{\par\smallskip{\bf Определение.} }{\par\smallskip}


\def\after#1{}

\long\def\usl#1{{\bf Условие.} \it #1 \rm\par{\bf Решение.} }

\def\Remark{\par{\bf Замечание.}\enskip}

\renewcommand\thesubsection{\arabic{subsection}}
\renewcommand\thesubsubsection{}

\newcounter{problem}[subsection]
\newcounter{subprob}[problem]
\newif\ifsub
\long\def\prob#1{\subfalse\@@prob #1\par\smallskip}
\newcommand\@@prob{\refstepcounter{problem}
\par\noindent\hskip\parindent\textbf{\arabic{subsection}.\arabic{problem}.} \kern1em}
\newcommand\probb[3]{\par\noindent\hskip\parindent\textbf{#1.\kern1em \itshape #2)\kern1em} #3\par\smallskip}
\newcommand\probbb[2]{\par\noindent\hskip\parindent\textbf{#1.\kern1em} #2\par\smallskip}


\newif\ifstar\starfalse

\newcommand{\sub}{\ifsub\par\indent\fi \@sub\subtrue}
\newcommand{\substar}{\ifsub\par\indent\fi\startrue\@sub\subtrue}
\newcommand{\@sub}{\refstepcounter{subprob}
\hbox to 3em{\bfseries{\itshape\alph{subprob}}\ifstar\boldmath$)^{*}$\else)\fi\hfil} \starfalse\relax}
\def\subb#1{\hbox to 3em{\bfseries{\itshape #1)}\hfil} \relax}


%

\def\sol{\par{\bf Решение.} }
\def\draft{{\bf Черновик!} \ }

\def\zlabel#1{\expandafter\xdef\csname z@#1\endcsname{\arabic{subsection}.\arabic{problem}}%
  \expandafter\xdef\csname zz@#1\endcsname{\csname z@#1\endcsname\alph{subprob})}}
\def\zref#1{\csname z@#1\endcsname}
\def\zreff#1{\csname zz@#1\endcsname}

\def\lemma#1{\par\smallskip{\bf Лемма.} #1\par}


\makeatother

\let\leq\leqslant
\let\geq\geqslant
\let\le\leq
\let\ge\geq
\let\ds\displaystyle

\def\D#1#2#3{\hbox{Д}_{#1,#2}(#3)}
\def\d#1#2{#1\hbox{д}[#2]}

\def\V#1#2#3{\hbox{В}_{#1,#2}(#3)}
\def\v#1#2{#1\hbox{в}[#2]}

\def\const{\mathop{\rm const}}


\begin{document}

\title{Взвешивания со сломанными весами. Решения}
\author{К.~Кноп, Г.~Челноков, И.~Богданов}
\date{}
\maketitle

\setcounter{subsection}1

\subsection{Вводные задачи: конкретные случаи}

\subsubsection{Что точно можно?}

Мы будем для краткости называть фальшивую монету ФМ.

Заметим, что если есть всего один сломанный тестер, и показания двух тестеров на каком-то наборе совпали, то эти показания истинны.

\prob{\zlabel{33}
    \usl{Тремя весами, из которых одни сломаны, можно из 3 монет найти фальшивую за 3 взвешивания (На удобном языке: $\V 31 3\leq 3$).}
Взвесим первые две монеты на всех трех весах. Как минимум два результата совпадут~--- это и будет правильный результат этого взвешивания. По нему, очевидно, определяется ФМ.
}

\prob{
  \sub \zlabel{86}
    \usl{Тремя детекторами, из которых один сломан, можно из 8 монет найти фальшивую за 6 тестирований. (На удобном языке: $\D 31 8\leq 6$.)}
Разделим все монеты на 4 группы по две монеты. Проверим первым детектором группы 1 и 2, а вторым~--- группы 1 и 3. Без ограничения общности можно считать, что оба ответа положительны (почему?). Тогда третьим детектором проверим группы 2 и 3. Возможны два случая.

1. Пусть ответ отрицателен; тогда ФМ в группе 1 (иначе хотя бы два детектора соврали!). Проверив одну монету из этой группы на всех трех детекторах, мы найдем ФМ.

2. Пусть ответ на третье испытание положителен. Тогда уже точно один из детекторов соврал (и если бы у нас имелся в наличии четвертый, то он точно бы был рабочим~--- но и без него все получается!). Проверим группы 1 и 2~--- теперь на втором детекторе. Если ответ положителен, то ФМ точно в этих группах, так как это утверждают два детектора; значит, первый детектор на первом испытании говорил правду, а врал тогда либо второй, либо третий. Если же ответ отрицателен, то либо первый, либо второй детектор лжет, а значит, третий~--- рабочий, поэтому ФМ в группе 2 или 3.

Итого, после 4 тестирования мы определили рабочий детектор и две группы, в которых находится ФМ. Тогда ее легко найти за 2 оставшихся испытания.

  \sub \zlabel{94}
  \usl{Тремя весами, из которых одни сломаны, можно из 9 монет найти фальшивую за 4 взвешивания.  (На удобном языке: $\V 31 9\leq 4$).}
Для удобства занумеруем монеты числами от 0 до 8 и запишем их в троичной записи (таким образом, каждой монете сопоставлена пара цифр от 0 до 2). Первое взвешивание делаем первыми весами в соответствии с первой цифрой номера: на левую чашу кладем монеты, у номера которых первая цифра 0, на правую --- у которых она 1. Второе взвешивание делаем аналогично вторыми весами в соответствии со второй цифрой номера. Без ограничения общности можем считать, что оба раза весы говорили, что фальшивая монета на левой чаше. Тогда 4 монеты без нулей в номере точно не фальшивые (иначе соврали и первые, и вторые весы).

Теперь разобьем монеты на три группы следующим образом: в одну поместим 00, в другую 01 и 02, в третью~--- 10 и 20; дополним все группы до трех монет точно не фальшивыми и взвесим третьими весами.

Если весы сказали, что фальшивая в группе с 00, то это и есть 00 (иначе двое весов соврали), и четвертое взвешивание не понадобилось. Если взвешивание сказало, что фальшивая в группе с 01 и 02, то третьи весы противоречат вторым. Поэтому хотя бы одни из них соврали, а значит, первые точно исправны. Но тогда у фальшивой первая цифра действительно 0; таким образом, остались лишь три кандидата на ФМ и одни точно исправные весы, которыми мы находим ФМ за 1 ход. Аналогично поступаем, если третье взвешивание сказало, что фальшивая в группе с~10 и 20.
}

\prob{
  \sub \zlabel{32-9}
  \usl{Тремя детекторами, из которых один сломан, можно из 32 монет найти фальшивую за 9 тестирований. (На удобном языке: $\D 31 {32}\leq 9$.)}
Разобьем все монеты на 4 группы по 8 монет в каждой и применим тот же алгоритм, что и в задаче \zreff{86}. Тогда в случае 1 мы за 3 тестирования найдем группу из 8 монет, которая содержит фальшивую; применяя ту же задачу, мы сделаем требуемое. Во втором же случае мы за 4 тестирования найдем две группы, одна из которых содержит фальшивую, а также найдем один рабочий детектор. С помощью него мы еще за 4 испытания найдем ФМ~--- в этом случае мы даже обошлись 8 тестированиями.


  \sub \zlabel{81-7}
  \usl{Тремя весами, из которых одни сломаны, можно из 81 монеты найти фальшивую за 7 взвешиваний. (На удобном языке: $\V 31 {81}\leq 7$).}
Аналогично \zreff{94}, занумеруем монеты последовательностями из 4 цифр 0, 1 или~2, и проведем первое взвешивание по первой цифре на первых весах, а второе по второй цифре~--- на вторых. Без ограничения общности можем считать, что оба раза весы говорили, что фальшивая монета имеет цифру 0 в соответствующем разряде. Отсюда опять же следует, что монеты, у которых первая и вторая цифра точно не нули~--- настоящие.

Теперь разобьем монеты на три группы следующим образом: в одну поместим 9 монет, у которых первые две цифры~--- 00, в другую~--- 18 монет с первыми двумя цифрами 01 или 02, а в третью~--- с цифрами 10 и 20; дополним все группы до 27 монет точно не фальшивыми и взвесим третьими весами.

Если весы сказали, что фальшивая в группе с 00, то это действительно так, и у нас осталось 9 монет, среди которых есть фальшивая, и 4 взвешивания. Это сводит задачу к~\zreff{94}.

Если взвешивание сказало, что фальшивая в группе с 01 и 02, то третьи весы противоречат вторым. Значит, хотя бы одни из них соврали, поэтому первые точно исправны. Но тогда у ФМ первая цифра действительно~0. Теперь мы имеем 27 монет, среди которых есть фальшивая, и одни точно исправные весы; с помощью них мы находим фальшивую за 3 хода (а седьмой даже не понадобился).
Аналогично мы поступаем, если третье взвешивание сказало, что фальшивая в группе с 10 и 20.
}


\subsubsection{Что точно нельзя?}

\prob{
  \usl{Из двух монет нельзя найти фальшивую за 2 тестирования/взвешивания (любым числом любых устройств, среди которых есть сломанные). (На удобном языке: $\D x1 2\geq 3$, $\V x1 2\geq 3$).}
Если оба тестирования мы делаем одним устройством, то оно может оказаться сломанным, и мы не получим никакой информации. Если мы использовали разные устройства, то в случае противоречащих ответов мы не можем определить фальшивую.
}

\prob{
  \sub \usl{Любым числом детекторов, среди которых есть сломанный, нельзя найти фальшивую монету из $2^k$ монет за $k$ тестирований. (На удобном языке: $\D x1 {2^k}>k$).}
  Предположим, что это возможно.

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

  На первом ходу количество кандидатов в фальшивые не уменьшалось (ибо первый детектор мог соврать). Поэтому за $k$ шагов при некотором наборе исходов оно уменьшилось не более, чем в $2^{k-1}$ раз, то есть осталось больше~1. Таким образом, при этом наборе исходов мы явно не смогли однозначно определить фальшивую монету.

  \sub \usl{Любым числом весов, среди которых есть сломанные, нельзя найти фальшивую монету из $3^k$ монет за $k$ взвешиваний. (На удобном языке: $\V x1 {3^k}>k$.)}
  Аналогично, только количество кандидатов делится на 3, а не на 2.
}

\prob{
  \sub \usl{Любым числом детекторов, среди которых есть сломанные, нельзя найти фальшивую монету из $2^k$ монет за $k+1$ тестирование. (На удобном языке: $\D x1 {2^k}>k+1$).}
   Будем говорить, что тестирование {\em отказало } данной монете, если оно показало, что монета находится в другой группе, нежели фальшивая. Иными словами, если тестирование отказало монете, то или монета не фальшивая, или детектор сломан.

  Аналогично доказанному в предыдущей задаче, если бы за $k+1$ тестирование можно было определить фальшивую, то после второго тестирования монет, которые могут оказаться фальшивыми, должно быть не более $2^{k-1}$. Но любая монета, которой не отказало хотя бы одно тестирование из первых двух, может оказаться фальшивой (если другое тестирование делалось на сломанном детекторе).

  Первое тестирование при одном из исходов отказывает не более, чем $\frac 12$ всех монет; таким образом, в этом случае первое тестирование {\em не отказывает} хотя бы половине всех монет. Второе же при некотором исходе не откажет еще какой-нибудь монете. Значит, строго больше половины монет могут оказаться фальшивыми --- противоречие.

  \sub \usl{Любым числом весов, среди которых есть сломанные, нельзя найти фальшивую монету из $3^k$ монет за $k+1$ взвешивание. (На удобном языке: $\V x1 {3^k}>k+1$.}
  Аналогично: получаем, что первое взвешивание не откажет хотя бы трети всех монет, а второе не откажет еще какой-нибудь монете. Поэтому после первых двух взвешиваний кандидатов будет больше, чем треть всех монет.
  
  \sub \usl{Любым числом весов, среди которых есть {\bf двое} сломанных, нельзя найти фальшивую монету из $n>3^6$ монет за $11$ взвешиваний. (На удобном языке: $\V x2 {n}>11$, если $n>3^6$.)}
  Решение этого пункта находится в конце раздела 3.
}


\subsection{Грубые, но серийные результаты}

\subsubsection{Серийные оценки сверху}

\prob{
  \usl{\sub Для каждого $k$ найдите минимальное такое $K$, что $\D Kk n<\infty$ при любом~$n$ (то есть, найдите минимальное число детекторов, при котором вообще {\em возможно} найти фальшивую монету).
  
  \sub Тот же вопрос для весов.}
  Решение не зависит от типа тестеров.
  
  {\bf Ответ.} $K=2k+1$.
  
  Пусть число тестеров $\leq 2k$, а фальшивая монета~--- $A$. Заставим все сломанные тестеры действовать так, как будто фальшивая монета~--- $B$. Тогда никогда не удастся выяснить, то ли все сломанные сломаны (и фальшивая~--- $A$), то ли все наоборот (и фальшивая~--- $B$).

  Если же тестеров $2k+1$, то можно каждую монету (или каждую пару для весов) проверить на всех тестерах; $k+1$ из результатов совпадут~--- это и будут истинные результаты.  
}

\prob{
  \sub 
  \usl{Докажите, что $\D 31{2^k}\leq 2k+1$. }
  Индукция по~$k$. При $k=1$ проверим первую монету всеми тремя детекторами; два совпавших ответа будут истинными.
  
  Пусть при $k=t$ утверждение доказано. Рассмотрим $2^{t+1}$ монет и проверим первые $2^t$ из них на первых двух тестерах. Если результаты совпадают, то они истинны, и мы сократили число монет до $2^t$; применяя предположение индукции, получаем требуемое.
  
  Если же результаты различны, то один из первых двух детекторов сломан; тогда третьим (заведомо рабочим) детектором мы за $t+1$ испытание найдем ФМ; в этом случае мы использовали не более $t+3\leq 2(t+1)+1$ испытаний.

  \sub \usl{Докажите, что $\V 31{3^k}\leq 2k+1$. }
  Совершенно аналогично.}

\prob{
  \sub 
  \usl{Докажите, что $\V 31{3^{2k}}\leq 3k+1$. }
  Опять индукция; база при $k=1$~--- это задача~\zreff{94}. Переход абсолютно аналогичен решению~\zreff{81-7}.

  \sub 
  \usl{Докажите, что $\D 31{2^{2k}}\leq 3k+2$. }
  Аналогично, индукция; переход аналогичен решению~\zreff{32-9}. База доказывается из тех же соображений; именно, мы либо за 3 испытания находим ФМ, либо за 4 детекции находим пару монет, среди которых есть фальшивая, и рабочий детектор. Тогда за оставшееся испытание мы найдем ФМ.
}

\prob{
  \sub \usl{Докажите, что при бесконечном числе детекторов, из которых один сломан, можно выявить одну фальшивую монету из $2^k$ за $k+o(k)$ взвешиваний. Иными словами, $\D \infty1{2^k}= k+o(k)$.}
  Занумеруем все монеты $k$-значными двоичными числами (от $0\dots0$ до $1\dots1$). Первыми $k$ взвешиваниями применим первые $k$ детекторов: каждый~--- к своему двоичному разряду. Без ограничения общности, пусть каждый из них ответил, что у фальшивой монеты в соответствующем разряде стоит~0. Значит, в любом случае единиц в номере ФМ не больше одной.
  
  Применим $(k+1)$-й детектор к монете $0\dots0$. Если он говорит, что она фальшивая, то так оно и есть (иначе два детектора солгали!). Иначе мы понимаем, что какой-то детектор из первых $k+1$ солгал, и при этом остался $k+1$ кандидат на фальшивость. Из этих кандидатов можно найти ФМ $(k+2)$-м (рабочим!) детектором за $\le \log_2(k+1)+1$ испытаний. Итого мы справились не более, чем за $k+1+\log_2(k+1)+1=k+o(k)$ испытаний.

  \sub \usl{Докажите, что при бесконечном числе весов, из которых одни сломаны, можно выявить одну фальшивую монету из $3^k$ за $k+o(k)$ взвешиваний. Иными словами, $\V \infty1{2^k}= k+o(k)$. }
  Абсолютно аналогично.
}

\prob{
  \usl{
  \sub Докажите, что существует $x$ такое, что $\D x1{2^k}= k+o(k)$. 

  \sub Докажите, что существует $x$ такое, что $\V x1{3^k}=k+o(k)$.}
  Следует из следующей задачи.
}

\prob{
  \subb{b} \usl{Докажите, что $\V 31{3^{k(k+1)}}\leq (k+1)^2$ при $k\geq 2$.}
Решим задачу индукцией по $k$, база для $k=1$ доказана в 2.2.b.

Как и раньше, нумеруем монеты в троичной системе счисления. Первые $k$ взвешиваний делаем по первым $k$ разрядам на первых весах, вторые $k$ взвешиваний~--- по следующим $k$ разрядам на вторых весах. Без ограничения общности можно считать, что все взвешивания показывали, что у фальшивой монеты в соответствующем разряде стоит 0. Теперь, если у номера ФМ есть не ноль как в первых $k$ разрядах, так и во вторых, то и первые, и вторые весы соврали. Значит, все такие монеты точно настоящие (будем их называть {\em эталонами}).

Для $(2k+1)$-го взвешивания разделим все неэталоны так: в одну группу поместим монеты, у которых в первых $2k$ разрядах только нули, во вторую --- монеты, у которых нули в первых $k$ разрядах, но есть не нули в разрядах с $(k+1)$-го по $2k$-й, а в третью~--- монеты, у которых есть не нули в первых $k$ разрядах, но в разрядах с $(k+1)$-го по $2k$-й все цифры~--- нули.
Ясно, что во второй и третьей группах монет поровну; взвесим их третьими весами. Если взвешивание указало на первую группу, то все результаты взвешиваний верны (иначе хотя бы двое весов давали неверный результат); значит, нам осталось за $k^2$ взвешиваний узнать $k(k-1)$ разрядов, что возможно по предположению индукции. Если $(2k+1)$-е взвешивание указало на вторую группу (для третьей аналогично), то показания третьих весов противоречат показаниям вторых, значит, первые весы точно исправны. Тогда мы уже выяснили первые $k$ разрядов, и за оставшиеся $k^2$ взвешиваний исправными весами выясним оставшиеся.

\par\indent
  \subb{a} \usl{Докажите, что $\D 31{2^{k(k+1)}}\leq (k+1)^2$ при $k\geq 5$.}
Аналогично пункту b) можно получить чуть более слабую оценку ${\D 31{2^{k(k-1)/2-1}}\leq }$\\ ${\leq k(k+1)/2-1}$. Похоже, что более сильная, к сожалению, следует лишь из~4.4.
}


\subsubsection{Серийные оценки снизу}

\prob{
  \sub \usl{Докажите, что $\D x1 n\leq \D x1 {2^k}$ при $n<2^k$.}
См. решение 3.8a).


  \sub \usl{Докажите, что $\V x1 n\leq \V x1 {3^k}$ при $n<3^k$.}
  Жюри не известно простого доказательства этого факта.
  }


\prob{
  \sub \usl{Докажите, что $\D x1 n\leq \D x1 N$ при $n<N$.}
Пусть есть какой-то алгоритм, позволяющий определить фальшивую монету из $N$ штук. Рассмотрим $n$ монет и добавим к ним $N-n$ фиктивных. Применим к ним тот же алгоритм; при этом, если нам надо будет класть в детектор фиктивные монеты, не будем класть вместо них ничего. Ясно, что при этом мы найдем фальшивую монету за то же число испытаний.

  \sub \usl{Докажите, что $\V x1 n\leq \V x1 N$ при $n<N$.}
  Жюри не известно простого доказательства этого факта.
}


\prob{\subtrue
  Мы приведем два решения этой задачи. Оба решения годятся для обоих пунктов с незначительными изменениями; мы напишем одно из них для первого пункта, а другое~--- для второго. 
  
  \sub\usl{Докажите, что если $\D x1 n=d$, то $\ds\frac{2^d}{d+1}\geq n$. (Эта оценка не зависит от~$x$!)}\zlabel{lowba}
Рассмотрим алгоритм, позволяющий найти ФМ за $d$ ходов. Пусть мы каким-то образом его провели; запишем результаты испытаний в строчку. У нас получилась строка из $d$ знаков <<Д>> и <<Н>> (означающих <<да>> и <<нет>>). При этом по строчке мы умеем восстановить, какие именно взвешивания мы делали (ибо по первым $i$ результатам алгоритм определяет, что за взвешивание делается на $(i+1)$-м шаге), а значит, каждой такой строчке однозначно соответствует ФМ.

Теперь выясним, сколько таких строчек соответствует одному варианту ФМ. Их хотя бы $d+1$; действительно, есть как минимум такие строчки: 0) в которой все ответы правильные; 1) в которой ровно первый ответ неверен; 2) в которой только второй ответ неверен; \dots; $k$) в которой ровно $k$-й ответ неверен. Ясно, что строка 0) отличается от всех остальных; строки же $i$) и $j$) (при $i<j$) отличаются хотя бы в $i$-м разряде.

Таким образом, строк не меньше, чем~$n(d+1)$; с другой стороны, всех возможных строк не больше, чем~$2^d$. Таким образом, $n(d+1)\leq 2^d$, что и требовалось.

\Remark Из этого доказательства видно, как должен быть устроен алгоритм, если мы хотим его сделать близким к этой оценке. Она будет точной, если a) (почти) все строчки будут возможны и b) (!!!) если какой-то тестер соврет, то мы сможем это распознать до второго его использования. Действительно, если мы этого не сделаем, то количество строк, соответствующих одной ФМ, увеличится.

  \sub \usl{Докажите, что если $\V x1 n=d$, то $\ds\frac{3^d}{2d+1}\geq n$.}\zlabel{lowb}
Введем обозначения. При каждом взвешивании мы делим монеты на три группы, и очередные весы отказывают монетам двух групп. Пусть уже сделаны некоторые взвешивания. Тогда монеты, которые {\bf всегда} оказывались в <<фальшивой>> группе при взвешивании на $i$-х весах, назовем {\em фальшивыми с точки зрения} этих весов.

Тогда после нескольких шагов алгоритма все монеты делятся на следующие группы. 1) Монеты, фальшивые с точки зрения всех весов; такие монеты мы будем называть {\em подозреваемыми}. 2) Монеты, фальшивые с точки зрения всех весов, кроме $i$-х; такие монеты мы будем называть {\em отказниками $i$-го типа}. Ясно, что эти монеты могут оказаться фальшивыми, только если $i$-е весы сломаны. 3) Монеты, которые хотя бы двое весов помещали в группу настоящих; тогда они и являются настоящими, и их мы будем называть {\em эталонами}.

Пусть у нас имеется алгоритм, позволяющий найти фальшивую из~$n$ монет за $d$ шагов. Мы можем считать, что он всегда заканчивает свою работу ровно через $d$ шагов (если это происходит раньше, просто сделаем еще несколько произвольных взвешиваний).

Введем понятие {\em значимости} монеты в некоторый момент алгоритма. Если осталось еще $m$ шагов до конца алгоритма (то есть сделано $d-m$ шагов), то будем говорить, что значимость любой подозреваемой монеты равна~$2m+1$, а значимость любого отказника~--- 1 (значимость эталона равна нулю). Значимостью ситуации назовем суммарную значимость всех монет.

Заметим, что если в ситуации со значимостью~$x$ делается некоторое взвешивание (скажем, на первых весах), то сумма значимостей трех ситуаций, в которые мы придем при трех возможных результатах взвешивания, не меньше $x$. Для этого достаточно доказать, что сумма возможных значимостей каждой монеты после взвешивания не меньше, чем ее исходная значимость. Подозреваемая со значимостью $2m+1$ при единственном исходе останется подозреваемой (со значимостью $2(m-1)+1$), а при двух других исходах становится отказником со значимостью~1. Отказник не первого типа при одном исходе остается отказником, при двух других становится эталоном. Для отказников же первого типа (и только для них!) сумма значимостей после взвешивания будет больше их нынешней значимости (1 превращается в 3).

Итак, если значимость ситуации была равна~$x$, то при одном из исходов она станет не меньше, чем $x/3$. Предположим, что при каждом взвешивании и получается такой исход. В начале алгоритма значимость была равна $(2d+1)n$ (все монеты подозрительны), а в конце она должна стать равной 1 (так как после $d$ шагов значимость любой монеты равна~1). Значит, $(2d+1)n\leq 3^d$, что и требовалось доказать.

\Remark Это доказательство тоже говорит немало о том, как должен выглядеть оптимальный алгоритм. Именно, значимость должна каждый раз уменьшаться втрое. 

Задумаемся, а что может нам помешать каждый раз уменьшать значимость ровно в 3 раза? Во-первых, если мы взвешиваем весами того типа, которого есть отказники, то вес этих отказников не делится на три. Значит, мы должны построить процесс так, чтобы этой ситуации не возникало. Во-вторых, для каждого конкретного взвешивания значимости ситуаций, к которым ведут три различных возможных исхода, должны быть примерно равны.
}


\probb{2.6}{c}{ \usl{Любым числом весов, среди которых есть {\bf двое} сломанных, нельзя найти фальшивую монету из $n>3^6$ монет за $11$ взвешиваний. (На удобном языке: $\V x2 {n}>11$, если $n>3^6$.)}
Рассмотрим произвольный алгоритм, позволяющий найти ФМ из $n$ монет за 11 ходов. Пусть мы каким-то образом его провели; запишем результаты испытаний в строчку. У нас получилась строка из 11 знаков <<$<$>>, <<$=$>> и <<$>$>>. Как и в решении~\zreff{lowba}, каждой такой строчке однозначно соответствует ФМ.

Теперь выясним, сколько таких строчек соответствует одному варианту ФМ. Их хотя бы $1+2\cdot 11+4\cdot 55=243$; действительно, есть как минимум такие строчки: 0) в которой все ответы правильные; 1) в которых ровно один ответ неверен (таких строчек 22: можно выбрать место, в котором стоит неверный ответ, 11 способами, и в каждом из них может стоять один из двух возможных неверных ответов); 2) в которых ровно два ответа неверны (таких $4\cdot 55$, ибо есть 55 пар мест и 4 варианта пар неверных ответов). Нетрудно понять, что все описанные строчки различны.

Таким образом, строк не меньше, чем $243n$; с другой стороны, всех возможных строк не больше, чем $3^{11}$. Таким образом, $n\cdot 243\leq 3^{11}$, откуда $n\leq 3^6$.
}

\subsection{Точные результаты}

\prob{\usl{
  \sub Докажите, что $\D 41{2^4}=7$.

  \sub Докажите, что $\V 41{3^6}=9$.}
  См. решение 4.4. Хотя это можно сделать и без применения столь общих приемов.
}
\prob{
    \usl{\sub Среди какого наибольшего числа монет можно выявить фальшивую на $\d 41$ за 15 тестирований? (Иначе говоря, найдите наибольшее $n$ такое, что $\D 41 n\leq 15$.)

  \sub Среди какого наибольшего числа монет можно выявить фальшивую на $\v 41$ за 13 тестирований? (Иначе говоря, найдите наибольшее $n$ такое, что $\V 41 n\leq 13$.)

  \sub А за 40 тестирований?}
  {\bf Ответы.} a) $2^{11}$; b) $3^{10}$; c) $3^{36}$.
  
  Верхние оценки следуют из задачи~\zref{lowb}. Доказательство того, что эти оценки достигаются, вытекает из решения~4.4. Тем не менее, при желании эти алгоритмы можно найти ручными методами.
}

\prob{\usl{Приведите пример такого $n$, что $\V 41 n<\V 31 n$.}
Решение этой задачи находится после 4.4.}

\prob{\zlabel{toch}
  \sub \usl{Докажите, что $\D 41 {3^k}=k+\log_2 k + c_{\text{д} k}$, где последовательность~$c_{\text{д} k}$ ограничена.}
Мы докажем, что $\D41{2^k}=k+t$ для наименьшего $t$ такого, что $2^t \ge k+t+1$
(тогда ${t= \log_2(k+t)+O(1)}$, откуда $t=\log_2 k+O(1)$, что и требовалось). Из решения~\zref{lowb} мы уже знаем, что $\D41{2^k}\geq \discretionary{}{\hbox{$\geq$}}{}k+t$. Осталось привести алгоритм, позволяющий найти фальшивую за $k+t$ взвешиваний.

Здесь и далее во всех задачах с детекторами {\em значимостью} подозреваемой монеты будем называть величину $i+1$, где~$i$~--- число ходов до конца процесса (по умолчанию), или же до специально оговоренного момента этого процесса. Значимость отказника всегда равна 1, эталона --- нулю. Значимость ситуации есть сумма значимостей монет. Заметим, что сумма значимостей возможных ситуаций после тестирования не меньше исходной значимости; значит, при одном из исходов испытания она уменьшается не более, чем вдвое.

При этом значимость исходной ситуации равна $(k+t+1)2^k\leq 2^{k+t}$. Значит, для достижения $k+t$ шагов мы должны добиться того, что значимость всегда уменьшается вдвое (или почти вдвое). Таким образом, мы будем строить алгоритм так, чтобы в каждый момент существовали отказники не более, чем трех различных типов; при этом значимость ситуации за $m$ шагов до конца не будет превосходить~$2^m$. Ясно, что в начальный момент это так.

Сначала опишем шаг алгоритма в общих чертах. Пусть до конца осталось $m$ шагов. Мы делим монеты на группы так, чтобы (i) возможные значимости ситуаций после тестирования не превосходили~$2^{m-1}$, и (ii) в каждой группе были бы отказники не более, чем двух типов. Затем проводим испытание тем детектором, для которого нет отказников его типа. Пусть он указал на некоторую группу, как на содержащую фальшивую. Тогда отказниками после этого хода будут только старые отказники из этой группы (среди которых не больше двух разных типов) и отказники текущего детектора (которые все одного типа) --- то есть мы по индукции сохранили требуемое число типов отказников.

Теперь разберемся в деталях. Во-первых, заметим, что при таком распределении сумма значимостей возможных ситуаций после взвешивания будет равна исходной значимости. Поэтому, если мы смогли распределить подозреваемых так, чтобы эти значимости не превосходили $2^{m-1}$, то заведомо можно {\bf как-то} распределить отказников так, чтобы это продолжало выполняться. 

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

  {\bf Лемма о двух автобусах.} Даны несколько школьников из трех классов (пусть их количества равны $a_1\leq a_2\leq a_3$) и два автобуса (их вместимости равны $b_1\leq b_2$; при этом $a_1+a_2+a_3\leq b_1+b_2$). Школьников надо рассадить по автобусам так, чтобы в каждом автобусе были школьники не более, чем из двух классов. Тогда это можно сделать если и только если $b_1 \geq a_1$.

\proof
Пусть $b_1\geq a_1$; покажем, как можно разместить школьников. Если суммарная вместимость автобусов больше, чем количество школьников, то можно уменьшить одно из чисел $b_1$ или $b_2$ на единицу так, чтобы условие продолжало выполняться (если $b_2>b_1$, то уменьшим $b_2$, иначе можно уменьшить $b_1$). Итого, можно считать, что $a_1+a_2+a_3=b_1+b_2$

Выстроим всех школьников в ряд: сначала все из первого класса, затем~--- из третьего, и в конце~--- из второго. Затем рассадим первых $b_1$ из них в первый автобус, затем следующих $b_2$ во второй. Тогда все первоклассники окажутся в первом автобусе (непосредственно из условия), а все второклассники окажутся во втором автобусе (в противном случае $b_2< a_2$, $b_1> a_1+a_3 > a_3\geq b_2$, что неверно).

Обратно, если $b_1 < a_1$, то также $b_1 < a_2$ и $b_1 < a_3$. То есть никакой класс не может целиком находиться в первом автобусе, а значит представители всех трех классов попадут во второй автобус.
\endproof

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

Вернемся к построению алгоритма. На первых $k$ тестированиях мы делим и подозреваемых, и отказников на две равные части; тогда, очевидно, при любом исходе значимость уменьшится ровно вдвое, поэтому условие~(i) выполняется. При этом условие леммы, очевидно, выполняется (отказников какого-то типа не больше половины!), поэтому здесь мы шаг выполнить смогли. После $k$-ого такого хода останется ровно одна подозреваемая и несколько отказников трех типов.

Разберемся подробнее, что происходит на следующих ходах. Если к какому-то ходу подозреваемых не осталось, то всех отказников мы можем разделить на две группы поровну (или почти поровну, если их число нечетно) с выполнением условия (ii)~--- по тем же причинам. При этом, так как значимость не превосходила~$2^m$ до этого шага, то число монет в группах не превосходит $2^{m-1}$, а значит, условие (i) также выполнено.

Осталось разобрать случай, когда подозреваемая осталась. Положим ее в первую группу; тогда в эту группу можно положить еще максимум $2^{m-1}-m$ отказников, а остальных~--- в другую. Теперь, если лемма об автобусах неприменима, то отказников каждого из трех типов больше, чем $2^{m-1}-m+1$. Но тогда общая значимость монет сейчас равна $(m+1)+3(2^{m-1}-m+1)=2^m+(2^{m-1}-2m+4)$; нетрудно видеть, что вторая скобка всегда положительна, поэтому эта ситуация невозможна.

  \sub 
  \usl{Докажите, что $\V 41 {3^k}=k+\log_3 k + c_{\text{в} k}$, где последовательность~$c_{\text{в} k}$ ограничена.}  
Аналогично, мы докажем, что $\V41{3^k}=k+t$ для наименьшего $t$ такого, что $3^t \ge 2(k+t)+1$
(тогда $t=\discretionary{}{\hbox{$=$}}{}\log_3 k+O(1)$). Оценка $\V41{3^k}\geq k+t$ опять следует из задачи~\zref{lowb}. Алгоритм мы будем строить, руководствуясь такими же соображениями (здесь значимость подозрительной монеты за $m$ шагов до конца равна $2m+1$). В этом случае условия разбиения на три группы будут выглядеть так: (i) возможные значимости ситуаций после тестирования не превосходят~$3^{m-1}$; (ii) в каждой группе есть отказники не более, чем двух типов; и (iii) в двух группах (возможно, после добавления эталонов) поровну монет (именно эти две группы мы и положим на чашки весов).

Выполнимость условия (ii) гарантирует аналогичная

{\bf Лемма о трех автобусах.} Даны несколько школьников из трех классов (пусть их количества равны $a_1\leq a_2\leq a_3$) и три автобуса (их вместимости равны $b_1\leq b_2\leq b_3$; при этом $a_1+a_2+a_3\leq b_1+b_2+b_3$). Школьников надо рассадить по автобусам так, чтобы в каждом автобусе были школьники не более, чем из двух классов. Тогда это можно сделать тогда и только тогда, когда $b_1+b_2\geq a_1$.

\proof
Покажем, как рассадить школьников при условии $b_1+b_2\geq a_1$.
Опять же, если $a_1+a_2+a_3<\discretionary{}{\hbox{$<$}}{} b_1+b_2+b_3$, то можно уменьшить одно из $b_i$ с соблюдением этого условия.

Выстроим всех школьников в ряд: сначала все из первого класса, затем~--- из третьего, и в конце~--- из второго. Затем рассадим первых $b_1$ из них в первый автобус, затем следующих $b_2$ во второй, и оставшихся в третий. В первый автобус попадает не больше трети, то есть второклассники в него не попадут. В третий не попадут первокласники из условия леммы. Наконец, если во второй автобус попали дети из всех трех классов, то в него попали хотя бы $a_3+2$ человека, а в третий~--- не больше $a_2-1<a_3$. Это невозможно, так как $b_2\leq b_3$.

Обратно, если $b_1+b_2 < a_1$, то также $b_1+b_2 < a_2$ и $b_1+b_2 < a_3$. Таким образом, никакой класс не может целиком находиться в первых двух автобусах, а значит, представители всех трех классов попадут в третий автобус.
\endproof

\Remark На самом деле, лемма о двух автобусах~--- частный случай этой, когда в одном автобусе нет мест.

\smallskip

Вернемся к алгоритму. На первых $k$ взвешиваниях мы делим и подозреваемых, и отказников на три равные части; тогда все три условия выполнены. После $k$-ого такого хода останется ровно одна подозреваемая и несколько отказников трех типов. Заметим, что после двух первых взвешиваний у нас уже получилось $4\cdot 3^{k-2}$ эталона. Это позволит нам гарантировать выполнение условия~(iii).

На следующих ходах, если к какому-то ходу подозреваемых не осталось, то всех отказников мы можем разделить на три группы почти поровну с выполнением условия (ii); при этом в двух группах будет поровну монет. Пусть, наконец, подозреваемая осталась. Положим ее в первую группу; это можно сделать, так как ее значимость после этого взвешивания будет равна $2m-1\leq 3^{m-1}$. Можно считать, что во вторую и третью группы мы должны положить поровну отказников. Тогда сумма двух минимальных вместимостей групп больше трети суммарной вместимости, поэтому лемма применима. При этом условие (iii) также выполняется. Последний случай разобран.
  
  \sub Найдите возможно лучшее ограничение сверху на эту последовательность.
}

\probbb{4.3}{  \usl{Приведите пример такого $n$, что $\V 41 n<\V 31 n$.}
Например, годится $n=3^{10}$. Из решения задачи~4.2b) следует, что $\V 41 n=13$. Далее мы будем пользоваться терминологией, введенной в~\zreff{lowb}.

Докажем, что $\V 31 n>13$. Предположим противное; это может случиться, только если значимость на каждом шагу уменьшается ровно втрое (при любом исходе взвешивания!). А это, в свою очередь, значит, что в любой момент существуют отказники не более, чем двух типов~--- а именно {\bf не} того типа, на котором производится очередное взвешивание.

Рассмотрим, как это может происходить. Будем обозначать ситуацию тройкой чисел $(a,b,c)$, где $a$~--- количество подозреваемых, а $b$ и $c$~--- количества отказников присутствующих двух типов. Тогда исходная ситуация есть $(3^{10},0,0)$, после первого взвешивания~--- $(3^9,2\cdot 3^9,0)$. Пусть во втором взвешивании количества подозреваемых в группах равны $a$, $b$, $c$.

Пусть это взвешивание показало на первую группу, тогда мы пришли к ситуации $(a,3^9-a,t)$, где число $t$ вычисляется из суммарной значимости: $23a+(3^9-a)+t=3^{11}$, откуда $t=8\cdot 3^9-22a$. Заметим, что $t\geq 0$, то есть $a\leq \frac4{11}3^9$. Аналогично $b,c\leq \frac4{11}3^9$, поэтому $a=3^9-(b+c)\geq \frac3{11}3^9$.

Посмотрим на третье взвешивание. Если все $a$ подозреваемых лежат в одной группе, то значимость этой группы будет не меньше $21\cdot \frac{3}{11}3^9>3^{10}$, что невозможно. Значит, подозреваемые попадут хотя бы в две группы. Тогда, чтобы после каждого возможного исхода оставались отказники лишь двух типов, необходимо, чтобы в каждой группе лежали бы отказники только одного типа. Значит, в какой-то группе будут лежать {\bf все} отказники одного типа~--- пусть их количество равно~$s$. Если на ней лежат еще $x$ подозреваемых, то ее значимость после взвешивания равна $3^{10}=21x+(a-x)+s=s+a+20x$; таким образом, $3^{10}-s-a$ должно делиться на~20. При этом $s=3^9-a$ либо $s=t=8\cdot 3^9-22a$. В первом случае получаем, что $3^{10}-s-a=2\cdot 3^9$ не делится на 20, что невозможно. Значит, выполнен второй случай, а тогда $3^{10}-s-a=21a-5\cdot 3^9$. Так как это число делится на~20, то $a$ должно делиться на~5. Аналогично, $b$ и $c$ также должны делиться на~5; это противоречит тому, что $a+b+c=3^9$, которое на~5 не делится.
}




\prob{
  \sub \usl{Докажите, что $\D x1 n=\D 41 n$ для любого $n$ и $x>4$.}
Пусть мы должны найти фальшивую из $n$ монет. Заметим, что если $t$ таково, что $2^t <\discretionary{}{\hbox{$<$}}{} n(t+1)$, то найти фальшивую за $t$ испытаний не удастся из соображений значимости. Аналогично, если  ${2^{t-1}} <\discretionary{}{\hbox{$<$}}{}{ \lceil n/2 \rceil \cdot t + \left(n-\lceil n/2 \rceil\right)}$ (верхняя целая часть $\lceil x \rceil$ есть наименьшее целое число, не меньшее $x$), то невозможно найти фальшивую. В самом деле, как бы мы не разделили монеты для первого теста, в одну из групп попадут хотя бы $\lceil n/2 \rceil$ монет; тогда, если первый тест скажет, что фальшивая в этой группе, определение будет невозможно по соображениям значимости. Понятно, что второе неравенство сильнее первого, то есть достаточно проверять его.

Итак, если мы приведем алгоритм, который для любого такого $t$, что $2^{t-1} \geq \lceil n/2 \rceil \cdot t + (n-\lceil n/2 \rceil)$ ищет фальшивую за $t$ ходов при помощи 4 детекторов, то мы доказали, что $\D41n=\D{\infty}1n$. Сделаем это.

Построим алгоритм, отвечающий двум условиям: (i) за $i$ шагов до конца значимость ситуации не больше~$2^i$; (ii) присутствуют отказники не более чем трех типов. На первом шаге разделим монеты почти пополам (т.е. на группы из $\lceil n/2 \rceil$  и $n-\lceil n/2 \rceil$) монет. По предположению, значимость ситуации после взвешивания $\le 2^{t-1}$. Дальше каждый раз делим подозреваемых почти пополам, а отказников распределяем исходя из соображений значимости, после чего выбираем, каких именно отказников куда помещать~--- по лемме о двух автобусах.

Рассмотрим $i$-й шаг до конца. Если значимость ситуации меньше $2^i$, то добавим {\em фиктивных} отказников так, чтобы новая значимость была равна $2^i$. Нетрудно понять, что если отказников (считая виртуальных!) не меньше, чем $3(i-2)-1$, то мы, во-первых, можем добиться того, чтобы значимости возможных после взвешивания ситуаций отличались не больше, чем на~1. Тогда в обоих случаях значимости за $i-1$ шаг до конца будут не больше $2^{i-1}$, ибо их сумма не больше $2^i$, что и требовалось. Более того, в этом случае количества отказников в двух группах будут отличаться не более, чем вдвое, поэтому в данном случае лемма об автобусах также применима (проверьте это!).

Осталось показать, что количество отказников за $i$ шагов до конца не меньше, чем $3(i-2)-1$, то есть суммарная значимость подозреваемых не превосходит $2^i-3(i-2)+1$.  Это можно сделать аккуратным подсчетом; мы не будем проводить его здесь.

  \sub \usl{Докажите, что $\V x1 n=\V 41 n$ для любого $n$ и $x>4$.}
Аналогично; нужно вдобавок добиться, чтобы в двух из получающихся на очередном шаге групп будет поровну элементов. Это можно сделать добавлением эталонов.

\Remark Теми же методами (хотя и с б\'ольшим числом технических подробностей) можно показать, что идеальное число тестеров существует для любого числа сломанных тестеров.
}

\prob{
  \sub \usl{Верна ли оценка того же вида, что и в задаче \zref{toch}, для $\D 31 n$?}
Пусть мы хотим (при достаточно большом~$n$) из $n$ монет найти фальшивую тремя детекторами, из которых один сломан.

Рассмотрим минимальное $d$, такое что $2^d+d+1\ge n(2d+1)$. Докажем, что нам хватит $d$ ходов для того, чтобы осталось не более двух монет, которые могут оказаться фальшивыми; это и будет момент, относительно которого мы определяем значимость. Тогда исходная значимость равна $n(2d+1)$.

Обозначим $x_i=2^i+i+1$. Построим процесс так, чтобы за $i$~взвешиваний до конца значимость не превосходила $x_i$, а отказники всегда были не более, чем двух разных типов.
Заметим, что если мы этого добились, то после $d$-го хода значимость не превосходит 2, значит, не более чем две монеты являются подозреваемыми или отказниками.

Построим процесс по индукции. До первого взвешивания оба условия выполнены. Пусть осталось построить $i$~последних взвешиваний, покажем, как сделать очередное. Здесь вместо леммы об автобусах используется следующая (очевидная)

{\bf Лемма о разрезании.} Пусть в ряд выстроены несколько предметов, стоимость каждого не превосходит $x$, а общая их стоимость равна $S$. Тогда ряд можно разбить на $t$ частей так, чтобы стоимость каждой части не превосходила~$\ds\frac{S+(t-1)x}t$.
\endproof

Пусть, без ограничения общности, присутствуют отказники первого и второго типа. Расставим монеты в ряд: сначала отказников первого типа, затем подозреваемых, и в конце отказников второго типа.
Обозначим количество подозреваемых через $a$. Посчитаем отказников с коэффициентом 1, а подозреваемых~--- $i-1$. Тогда сумма коэффициентов не превосходит $x_i-2a$; значит, по лемме о разрезании этот ряд можно разрезать на две части так, чтобы сумма коэффициентов в каждой части была $\le \ds\frac{x_i-2a+i-1}{2}$. Теперь, если протестировать детектором монеты любой из частей разрезания, то значимость полученной части будет равна сумме ее коэффициентов, увеличенной на количество подозреваемых (ибо подозреваемых в этой части мы должны считать с коэффициентом $i$ вместо $i-1$, а в другой~--- с коэффициентом~1 вместо~0). Таким образом, при любом исходе значимость не превысит $\ds\frac{x_i+i-1}{2}=x_{i-1}$. При этом, что если в какую-то часть разбиения попали отказники обоих типов, то туда же попали все подозреваемые; поэтому при любом исходе проверки остались отказники не больше, чем двух типов.

Итак, через $d$ взвешиваний у нас осталось не более двух кандидатов на ФМ. Осталось заметить, что из двух монет одну фальшивую можно найти за ограниченное число ходов (например, за 3). Таким образом, доказано, что $d+3$ тестирований хватит. Осталось заметить, что $d=\log_2(n(2d+1)-d-1)$, откуда $d=\discretionary{}{\hbox{$=$}}{}\log_2 n+\log_2 \log_2 n+O(1)$, как и требовалось.


  \sub \usl{Тот же вопрос про $\V 31 n$.}
Аналогично, мы собираемся (при достаточно больших $n$) из $n$ монет оставить только 3 кандидатов в фальшивые за $d$ взвешиваний. Мы утверждаем, что достаточно выбрать $d$ таким, что
$$
  (2d+1)+2\cdot 3^{d}\geq n(2d+1).
$$
Тогда (по задаче~\zref{33}) мы найдем ФМ за $d+3$ взвешивания; при этом $d=\log_3n+\log_3\log_3n+O(1)$.

Опять же, моментом, относительно которого отсчитывается значимость, мы называем момент после $d$-го взвешивания; тогда исходная значимость равна $n(2d+1)$.

Обозначим $y_i=(2i+1)+2\cdot 3^i$; мы будем строим процесс так, чтобы за $i$~взвешиваний до конца значимость не превосходила $y_i$, а отказники всегда были не более, чем двух разных типов; тогда после $d$-го взвешивания значимость не превосходит~3, что и требовалось.

Шаг алгоритма строится опять же аналогично. Присвоим всем подозреваемым коэффициент $D=2i-2$, а отказникам коэффициент~1; тогда сумма всех коэффициентов не превосходит~$y_i-3a$, где $a$~--- количество подозреваемых. Разложим все монеты в ряд: сначала отказников первого типа, затем подозреваемых, и в конце отказников второго типа. Тогда по лемме о разрезании, из можно разрезать на три части так, что сумма коэффициентов в каждой части не больше $\ds\frac{y_i-3a+2D}3$. Это значит, что значимость любой ситуации после взвешивания с такими тремя частями не превосходит $\ds\frac{y_i-3a+2D}3+a=y_{i-1}$, что и требовалось.

Здесь может возникнуть еще одна проблема: количества монет в трех полученных группах могут различаться. Покажем, что нам хватит эталонов для того, чтобы сделать две группы равными; тогда мы можем соорудить требуемое взвешивание. Легко видеть, что на первых двух шагах таких проблем не возникает: в первом взвешивании две из трех групп имеют равное количество монет, а во втором взвешивании легко распределить отказников и подозреваемых по трем группам так, что в двух из них монет будет поровну (немного изменив алгоритм разбиения, но не ухудшив оценку!). После этих взвешиваний появится хотя бы $\frac49n-2$ эталонов. Тогда мы раскладывали по трем группам не более, чем $\frac59 n+2$ монет, и значит, разность количеств монет в двух из этих групп будет не больше, чем $\frac 5{27}n+1\leq \frac49 n-2$ при $n\geq 12$. Тогда эталонов хватит. Решение окончено.
}

\end{document}

