\documentclass[12pt]{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.6in
\oddsidemargin=-0.3in
\textwidth=7in

\makeatletter


\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}

\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\zlabel#1{\expandafter\xdef\csname z@#1\endcsname{\arabic{subsection}.\arabic{problem}}}
\def\zref#1{\csname z@#1\endcsname}

\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

\subsection{Постановка проблемы}

\subsubsection{Базовые понятия}


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


{\em Детектор}~--- это устройство, которое за одно действие ({\em тестирование}) про любое выбранное подмножество монет сообщает, содержится в нем фальшивая или нет.
Таким образом, детектор при любом разбиении полного множества на 2 подмножества определяет, в каком из подмножеств оказалась фальшивая монета).

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

{\bf Главная изюминка данной задачи:}
мы разрешаем некоторым устройствам сообщать неверную информацию. При этом устройства не уподобляются лжецам, которые <<всегда врут>>. Они просто сломаны~--- то есть информация от такого устройства может быть как истинной, так и ложной. Грубо говоря, вместо правильного работающего устройства у нас работает генератор случайных ответов. Итого, у нас есть несколько устройств, и мы знаем лишь, сколько из них сломаны, но не знаем, какие. (При этом за одну операцию тестирование проводится только на одном из устройств!)

Введем обозначения. Пусть $\D xy z$ обозначает минимальное число тестирований детекторами, необходимое для {\bf гарантированного} нахождения одной фальшивой монеты среди $z$ при помощи $x$ детекторов, из которых $y$ сломаны (эту тестирующую систему мы будем обозначать через $\d xy$). Аналогично, $\V xy z$ будет обозначать то же для весов (а соответствующая система обозначается $\v xy$).

На протяжении первых разделов мы будем приводить для каждой задачи две формулировки: с использованием введенных обозначений, и (для тех, кому этот язык еще непривычен) без их использования.


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

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

\prob{
 Тремя весами, из которых одни сломаны, можно из 3 монет найти фальшивую за 3 взвешивания (На удобном языке: $\V 31 3\leq 3$).
}

\prob{
  \sub Тремя детекторами, из которых один сломан, можно из 8 монет найти фальшивую за 6 тестирований. (На удобном языке: $\D 31 8\leq 6$. )

  \sub Тремя весами, из которых одни сломаны, можно из 9 монет найти фальшивую за 4 взвешивания.
(На удобном языке: $\V 31 9\leq 4$). %Для 3В сделать 9 монет за 4 теста.
}

\prob{
  \sub Тремя детекторами, из которых один сломан, можно из 32 монет найти фальшивую за 9 тестирований. (На удобном языке: $\D 31 {32}\leq 9$.) 

  \sub Тремя весами, из которых одни сломаны, можно из 81 монеты найти фальшивую за 7 взвешиваний. (На удобном языке: $\V 31 {81}\leq 7$). %Для 3В 81 монету за 7 тестов.
}


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

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

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

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

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

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

  \sub
  Любым числом весов, среди которых есть {\bf двое} сломанных, нельзя найти фальшивую монету из $n>3^6$ монет за $11$ взвешиваний. (На удобном языке: $\V x2 {n}>11$, если $n>3^6$.)
}

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

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

В этом разделе $k$~--- натуральное число.

\prob{
  \sub Для каждого $k$ найдите минимальное такое $K$, что $\D Kk n<\infty$ при любом~$n$ (то есть, найдите минимальное число детекторов, при котором вообще {\em возможно} найти фальшивую монету).

  \sub Для каждого $k$ найдите минимальное такое $K$, что $\V Kk n<\infty$ при любом~$n$.
}


\prob{
  \sub Докажите, что $\D 31{2^k}\leq 2k+1$. %Докажите, что для любого натурального k для 3Д 2^k монет можно сделать за  2k+1 тестов.

  \sub Докажите, что $\V 31{3^k}\leq 2k+1$. %Докажите, что для любого натурального k для 3В 3^k монет можно сделать за  2k+1 тестов.
}

Как видно из предыдущей задачи, при наличии одного сломанного устройства из $n$ монет фальшивая ищется примерно за $2\log_2 n$ тестирований детекторами, и примерно за $2\log_3 n$ взвешиваний весами. Но эта оценка очень неточна. Задачи этого раздела будут посвящена уменьшению константы при логарифме, то есть числа $c$ в оценках вида $\D x1{n}\lesssim c\log_2 n$ и $\V x1{n}\lesssim c\log_3 n$.

\prob{
  \sub Докажите, что $\V 31{3^{2k}}\leq 3k+1$. %3В сделать 3^{2k} монет за 3k+1

  \sub Докажите, что $\D 31{2^{2k}}\leq 3k+2$. %3Д сделать 2^{2k} монет за 3k+1 для четного k.
}

Предыдущая задача показывает, что коэффициент $c$ можно уже сделать строго меньшим~2. Следующая цель --- доказать, что он на самом деле равен~1. Сначала предлагается это сделать для б\'ольшего числа устройств.

\smallskip

{\footnotesize Обозначение $o(k)$ означает функцию, растущую медленнее, чем $k$, то есть $f(k)=o(k)$, если $f(k)/k\to0$ ($k\to\infty$). Например, $\log_2 k=o(k)$ и $\sqrt k = o(k)$.}

\smallskip

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

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

\prob{
  \sub Докажите, что существует $x$ такое, что $\D x1{2^k}= k+o(k)$. %4Д сделать 2^{k} монет за k+o(k)

  \sub Докажите, что существует $x$ такое, что $\V x1{3^k}=k+o(k)$. %4В сделать 3^{k} монет за k+o(k)
}


\prob{
  \sub Докажите, что $\D 31{2^{k(k+1)}}\leq (k+1)^2$ при $k\geq 5$. %3Д сделать 2^{k} монет за k+o(k)

  \sub Докажите, что $\V 31{3^{k(k+1)}}\leq (k+1)^2$ при $k\geq 2$. %3В сделать 3^{k} монет за k+o(k)
}


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

\prob{
  \sub Докажите, что $\D x1 n\leq \D x1 {2^k}$ при $n<2^k$.

  \sub Докажите, что $\V x1 n\leq \V x1 {3^k}$ при $n<3^k$.}

\prob{
  \sub Докажите, что $\D x1 n\leq \D x1 N$ при $n<N$.

  \sub Докажите, что $\V x1 n\leq \V x1 N$ при $n<N$.}


\prob{
  \sub Докажите, что если $\D x1 n=d$, то $\ds\frac{2^d}{d+1}\geq n$. (Эта оценка не зависит от~$x$!)

  \sub Докажите, что если $\V x1 n=d$, то $\ds\frac{3^d}{2d+1}\geq n$.
}


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

Этот раздел посвящен сведению верхних оценок с нижними. Поэтому он начнется опять с разбора <<маленьких частных случаев>>.

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

  \sub Докажите, что $\V 41{3^6}=9$.
}

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

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

  \sub А за 40 тестирований?
}

\prob{
Приведите пример такого $n$, что $\V 41 n<\V 31 n$.
}


\prob{\zlabel{toch}
  \sub Докажите, что $\D 41 {2^k}=k+\log_2 k + c_{\text{д} k}$, где последовательность~$c_{\text{д} k}$ ограничена.


  \sub Докажите, что $\V 41 {3^k}=k+\log_3 k + c_{\text{в} k}$, где последовательность~$c_{\text{в} k}$ ограничена.

  \sub Найдите возможно лучшее ограничение сверху на эту последовательность.
}


\prob{
  \sub Докажите, что $\D x1 n=\D 41 n$ для любого $n$ и $x>4$.

  \sub Докажите, что $\V x1 n=\V 41 n$ для любого $n$ и $x>4$.
}

Если (при фиксированном $s$) для некоторого $t$ выполняются равенства $\D ts n=\D xs n$ ($\V ts n=\V xs n$) при всех $x>t$, то такое число устройств мы будем называть {\em идеальным} (для данного числа сломанных устройств~$s$). Иными словами, увеличивать количество устройств бессмысленно. Предыдущая задача показывает, что 4 устройства~--- идеальное число для одного сломанного.

\prob{
  \sub Верна ли оценка того же вида, что и в задаче \zref{toch}, для $\D 31 n$?

  \sub Тот же вопрос про $\V 31 n$.
}


\end{document}

