|
|
Пишет flaass (![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small} flaass)@ 2004-11-19 14:48:00 |
 |
|
 |
|
|
|
|
|
|
 |
|
 |
Об одной задаче последовательного перекодирования
Экстрасенс из бэк виз венджэнс! Нет ничего нуднее, чем переводить с английского на русский собственный текст, при этом местами сокращая. А вот результат:
\documentclass[12pt]{article}
%\usepackage[cp866]{inputenc}
\usepackage[russian]{babel}
\newtheorem{theorem}{Теорема}
\newtheorem{lemma}{Лемма}
\newcommand{\qed}{$\Box$\par\bigskip}
\begin{document}
\begin{center}
{Об одной задаче последовательного декодирования}\\
{М.Алексеев (США), Д.Барский (Англия), А.Воробей (Израиль), Г.Мерзон (Москва), Ю.Прокопчук (Минск), Д.Фон-Дер-Флаасс (Новосибирск)}
\end{center}
На математической олимпиаде "Турнир Городов" в 2004 г. была предложена такая задача:
"Перед экстрасенсом кладут колоду из 36 карт рубашкой вверх. Он называет масть верхней карты, после чего карту открывают, показывают ему и откладывают в сторону. После этого экстрасенс называет масть следующей карты, и т.д. На деле рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Колоду готовит подкупленный служащий - он знает порядок карт в колоде и, хотя не может его изменить, но волен выбирать положение рубашек карт. Как надо сговориться экстрасенсу и служащему, чтобы экстрасенс смог гарантированно угадать масть как можно больше раз?"
Задача естественно обобщается на случай произвольного числа $b$ мастей, $n$ карт в колоде,
$a < b$ различных пометок, которые служащий может оставить на рубашках карт, и произвольного множества $L$ разрешенных последовательностей мастей. Чему равно $m_{a,b}(n, L)$,
наименьшее число ошибок, которое экстрасенс с гарантией может не превзойти?
Мы дадим верхнюю и нижнюю оценки на $m_{a,b}(n, L)$, которые асимптотически совпадают, если $|L|=b^{n-o(n)}$.
Определим функцию
$$s_p(n,k)=\sum_{i=0}^k {n\choose i}p^i;$$
-- частичную сумму биномиального ряда.
\begin{theorem}\label{main}
a) Если $s_{b-1}(p,k)\geq(b/a)^p$, то существует такая константа $c$, зависящая от $a,b,p$, что для любого натурального $m$ и для любого $r$, $1\leq r\leq n$, выполняется неравенство
$m_{a,b}(c+pm+r, L)\leq c+km$ (при любом множестве разрешенных последовательностей длины $c+pm+r$).
b) Если $|L|=N$ и $s_{b-1}(n,k) < N/a^n$, то $m_{a,b}(n) > k$.
\end{theorem}
Оценки Теоремы \ref{main} асимптотически совпадают, если $N=|L|=b^{n-o(n)}$ (например, в случае, когда все $b^n$ последовательностей разрешены, или в случае, когда каждая масть должна встретиться одно и то же число раз, как в исходной задаче):
\begin{theorem}\label{limit}
Если число разрешенных последовательностей длины $n$ равно $b^{n-o(n)}$, то существует предел
$$\alpha(a,b)=\lim_{n\rightarrow\infty}\f
и этот предел является корнем $x$ уравнения
$$(b-1)^x=\frac{b}{a}x^x(1-x)^{1-x}.$$
\end{theorem}
Доказательство Теоремы \ref{main}.
Мы будем измерять количество информации, которой экстрасенс обладает в каждый момент, не в битах, а в более точных единицах, {\bf $N$-итах}. Один $N$-ит обозначает знание, какая из $N$ заранее заданных возможностей выполнена. Например, 2-ит -- это один бит; 1-ит -- это полное отсутствие информации.
a) Пусть заданы $1 < a < b$, $p$. Положим $c=\lceil p\cdot\log_a b\rceil$. Пусть $n=c+pm+r$, где $1\leq r\leq p$;
и пусть $k$ удовлетворяет требуемому неравенству. Мы опишем алгоритм, как экстрасенс (Э) может угадать масти всех, кроме не более чем $c+pk$ карт, независимо от того, каково множество разрешенных последовательностей.
Вначале Э запоминает пометки на первых $c$ картах, называя при этом масти наугад. Это дает не более $c$ ошибок, и один $a^c$-ит информации. Ввиду выбора $c$, мы имеем $a^c\geq b^p$; поэтому полученной информации достаточно, чтобы закодировать любую последовательность из $p$ мастей.
В начале каждой из следующих $m$ стадий, у Э будет достаточно информации, чтобы определить его следующие
$p$ ответов. Служитель задает их так, чтобы не более $k$ из них были неверными. Таким образом, в течение этих $p$ шагов Э сделает не более $k$ ошибок. В то же время он собирает один $a^p$-ит информации из пометок на картах, и $s_{b-1}(p,k)$-ит информации из положений, в которых произошли ошибки, и разностей между ошибочно названной мастью и ее истинным значением. (Масти можно считать занумерованными от $0$ до $b-1$, и разности вычисляются по модулю $b$.)
Таким образом, к концу каждой стадии Э имеет один $a^ps_{b-1}(p,k)$-ит информации. Ввиду выбора $k$, выполняется неравенство $a^ps_{b-1}(p,k)\geq b^p$; таким образом, процесс может быть продолжен.
В заключение Э верно угадывает последние $r$ мастей, используя информацию, полученную на последней, $m$-й стадии. Утверждение (a) доказано.
\medskip
Для доказательства нижней оценки (b) нам потребуется простая лемма из теории графов.
\begin{lemma}\label{tree}
Пусть $T$ --- корневое дерево, дуги которого (ориентированные в направлении от корня) окрашены в черный и белый цвета так, что выполняются следующие условия:
$(i)$ $T$ имеет высоту $n$; то есть, расстояние от корня до каждого листа равно $n$;
$(ii)$ Из каждой вершины выходит не более $p$ черных, и не более $q$ белых дуг;
$(iii)$ Каждый простой путь от корня к листу содержит не более $k$ белых дуг.
Тогда число листьев $T$ не превосходит $p^n\cdot s_{q/p}(n,k)$.
\end{lemma}
Доказательство леммы.\quad Зафиксируем $p$ и $q$. Назовем {\bf $(n,k)$-деревом} любое дерево, удовлетворяющее условиям леммы. Пусть $m(n,k)$ --- наибольшее количество листьев в $(n,k)$-дереве. Выполняются очевидные равенства
$m(n,0)=p^n=p^n\cdot s_{q/p}(n,0)$ (белых дуг вообще нет), и
$m(n,n)=(p+q)^n=p^n\cdot s_{q/p}(n,n)$ (ограничений на цвет дуг нет; из каждой внутренней вершины может выходить $p+q$ дуг).
При $0 < k < n$, любое $(n,k)$-дерево состоит из корня, к которому черными дугами присоединены
$(n-1,k)$-деревья, и белыми дугами присоединены $(n-1,k-1)$-деревья. Таким образом, мы получаем реккурентную формулу $m(n,k)=pm(n-1,k)+qm(n-1,k-1)$, из которой заключение леммы нетрудно доказать по индукции.
\qed
Докажем теперь нижнюю оценку теоремы. Пусть служитель и экстрасенс выбрали стратегию, гарантирующую не более
$k$ ошибок. Во-первых, это означает, что для каждой из $N$ возможных последовательностей мастей служитель однозначно определяет последовательность пометок. Мы рассматриваем каждую такую помеченную последовательность как слово длины $n$ над алфавитом размера
$ab$, буквами которого являются пары $(s,l)$ из масти $s$ и пометки $l$. Определим корневое дерево, вершинами которого являются все начальные сегменты длин от $0$ до $n$ всех
$N$ слов, а дуги соответствуют добавлению к сегменту следующего символа.
Для каждого начального сегмента длины, меньшей $n$, и каждого возможного значения метки на следующей карте,
выбранная стратегия определяет, какую масть назовет экстрасенс. Покрасим черным те дуги, которые соответствуют правильному ответу, и белым --- соответствующие ошибке. Легко видеть, что из каждой вершины выходит не более
$a$ черных дуг, и не более $a(b-1)$ белых. Высота дерева равна $n$, оно имеет $N$ листьев, и каждый путь от корня к листу содержит не более $k$ белых дуг. Применяя Лемму со значениями $p=a$, $q=a(b-1)$, мы получаем требуемое неравенство.
\qed
Для превоначальной задачи с 36 картами, авторам известен алгоритм, гарантирующий не более 10 ошибок. Теорема \ref{main} дает в этом случае нижнюю оценку в 6 ошибок. Точный ответ остается неизвестным.
Авторы выражают благодарность интернет-проекту
LiveJournal ({\it www.livejournal.com}),
который оказался идеальным средством для организации совместной работы над
задачей. Авторы благодарят пользвателей {\it a\_konst} и {\it mi\_b} за ценные обсуждения, и все сообщество пользователей LiveJournal за постоянный интерес к процессу их работы.
\end{document}
Это будет в материалах нашей конференции; еще не совсем полноправная публикация.
А картинку, как я все это излагал, уже показывал.
Экстрасенс из бэк виз венджэнс! Нет ничего нуднее, чем переводить с английского на русский собственный текст, при этом местами сокращая. А вот результат:
\documentclass[12pt]{article}
%\usepackage[cp866]{inputenc}
\usepackage[russian]{babel}
\newtheorem{theorem}{Теорема}
\newtheorem{lemma}{Лемма}
\newcommand{\qed}{$\Box$\par\bigskip}
\begin{document}
\begin{center}
{Об одной задаче последовательного декодирования}\\
{М.Алексеев (США), Д.Барский (Англия), А.Воробей (Израиль), Г.Мерзон (Москва), Ю.Прокопчук (Минск), Д.Фон-Дер-Флаасс (Новосибирск)}
\end{center}
На математической олимпиаде "Турнир Городов" в 2004 г. была предложена такая задача:
"Перед экстрасенсом кладут колоду из 36 карт рубашкой вверх. Он называет масть верхней карты, после чего карту открывают, показывают ему и откладывают в сторону. После этого экстрасенс называет масть следующей карты, и т.д. На деле рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Колоду готовит подкупленный служащий - он знает порядок карт в колоде и, хотя не может его изменить, но волен выбирать положение рубашек карт. Как надо сговориться экстрасенсу и служащему, чтобы экстрасенс смог гарантированно угадать масть как можно больше раз?"
Задача естественно обобщается на случай произвольного числа $b$ мастей, $n$ карт в колоде,
$a < b$ различных пометок, которые служащий может оставить на рубашках карт, и произвольного множества $L$ разрешенных последовательностей мастей. Чему равно $m_{a,b}(n, L)$,
наименьшее число ошибок, которое экстрасенс с гарантией может не превзойти?
Мы дадим верхнюю и нижнюю оценки на $m_{a,b}(n, L)$, которые асимптотически совпадают, если $|L|=b^{n-o(n)}$.
Определим функцию
$$s_p(n,k)=\sum_{i=0}^k {n\choose i}p^i;$$
-- частичную сумму биномиального ряда.
\begin{theorem}\label{main}
a) Если $s_{b-1}(p,k)\geq(b/a)^p$, то существует такая константа $c$, зависящая от $a,b,p$, что для любого натурального $m$ и для любого $r$, $1\leq r\leq n$, выполняется неравенство
$m_{a,b}(c+pm+r, L)\leq c+km$ (при любом множестве разрешенных последовательностей длины $c+pm+r$).
b) Если $|L|=N$ и $s_{b-1}(n,k) < N/a^n$, то $m_{a,b}(n) > k$.
\end{theorem}
Оценки Теоремы \ref{main} асимптотически совпадают, если $N=|L|=b^{n-o(n)}$ (например, в случае, когда все $b^n$ последовательностей разрешены, или в случае, когда каждая масть должна встретиться одно и то же число раз, как в исходной задаче):
\begin{theorem}\label{limit}
Если число разрешенных последовательностей длины $n$ равно $b^{n-o(n)}$, то существует предел
$$\alpha(a,b)=\lim_{n\rightarrow\infty}\f
и этот предел является корнем $x$ уравнения
$$(b-1)^x=\frac{b}{a}x^x(1-x)^{1-x}.$$
\end{theorem}
Доказательство Теоремы \ref{main}.
Мы будем измерять количество информации, которой экстрасенс обладает в каждый момент, не в битах, а в более точных единицах, {\bf $N$-итах}. Один $N$-ит обозначает знание, какая из $N$ заранее заданных возможностей выполнена. Например, 2-ит -- это один бит; 1-ит -- это полное отсутствие информации.
a) Пусть заданы $1 < a < b$, $p$. Положим $c=\lceil p\cdot\log_a b\rceil$. Пусть $n=c+pm+r$, где $1\leq r\leq p$;
и пусть $k$ удовлетворяет требуемому неравенству. Мы опишем алгоритм, как экстрасенс (Э) может угадать масти всех, кроме не более чем $c+pk$ карт, независимо от того, каково множество разрешенных последовательностей.
Вначале Э запоминает пометки на первых $c$ картах, называя при этом масти наугад. Это дает не более $c$ ошибок, и один $a^c$-ит информации. Ввиду выбора $c$, мы имеем $a^c\geq b^p$; поэтому полученной информации достаточно, чтобы закодировать любую последовательность из $p$ мастей.
В начале каждой из следующих $m$ стадий, у Э будет достаточно информации, чтобы определить его следующие
$p$ ответов. Служитель задает их так, чтобы не более $k$ из них были неверными. Таким образом, в течение этих $p$ шагов Э сделает не более $k$ ошибок. В то же время он собирает один $a^p$-ит информации из пометок на картах, и $s_{b-1}(p,k)$-ит информации из положений, в которых произошли ошибки, и разностей между ошибочно названной мастью и ее истинным значением. (Масти можно считать занумерованными от $0$ до $b-1$, и разности вычисляются по модулю $b$.)
Таким образом, к концу каждой стадии Э имеет один $a^ps_{b-1}(p,k)$-ит информации. Ввиду выбора $k$, выполняется неравенство $a^ps_{b-1}(p,k)\geq b^p$; таким образом, процесс может быть продолжен.
В заключение Э верно угадывает последние $r$ мастей, используя информацию, полученную на последней, $m$-й стадии. Утверждение (a) доказано.
\medskip
Для доказательства нижней оценки (b) нам потребуется простая лемма из теории графов.
\begin{lemma}\label{tree}
Пусть $T$ --- корневое дерево, дуги которого (ориентированные в направлении от корня) окрашены в черный и белый цвета так, что выполняются следующие условия:
$(i)$ $T$ имеет высоту $n$; то есть, расстояние от корня до каждого листа равно $n$;
$(ii)$ Из каждой вершины выходит не более $p$ черных, и не более $q$ белых дуг;
$(iii)$ Каждый простой путь от корня к листу содержит не более $k$ белых дуг.
Тогда число листьев $T$ не превосходит $p^n\cdot s_{q/p}(n,k)$.
\end{lemma}
Доказательство леммы.\quad Зафиксируем $p$ и $q$. Назовем {\bf $(n,k)$-деревом} любое дерево, удовлетворяющее условиям леммы. Пусть $m(n,k)$ --- наибольшее количество листьев в $(n,k)$-дереве. Выполняются очевидные равенства
$m(n,0)=p^n=p^n\cdot s_{q/p}(n,0)$ (белых дуг вообще нет), и
$m(n,n)=(p+q)^n=p^n\cdot s_{q/p}(n,n)$ (ограничений на цвет дуг нет; из каждой внутренней вершины может выходить $p+q$ дуг).
При $0 < k < n$, любое $(n,k)$-дерево состоит из корня, к которому черными дугами присоединены
$(n-1,k)$-деревья, и белыми дугами присоединены $(n-1,k-1)$-деревья. Таким образом, мы получаем реккурентную формулу $m(n,k)=pm(n-1,k)+qm(n-1,k-1)$, из которой заключение леммы нетрудно доказать по индукции.
\qed
Докажем теперь нижнюю оценку теоремы. Пусть служитель и экстрасенс выбрали стратегию, гарантирующую не более
$k$ ошибок. Во-первых, это означает, что для каждой из $N$ возможных последовательностей мастей служитель однозначно определяет последовательность пометок. Мы рассматриваем каждую такую помеченную последовательность как слово длины $n$ над алфавитом размера
$ab$, буквами которого являются пары $(s,l)$ из масти $s$ и пометки $l$. Определим корневое дерево, вершинами которого являются все начальные сегменты длин от $0$ до $n$ всех
$N$ слов, а дуги соответствуют добавлению к сегменту следующего символа.
Для каждого начального сегмента длины, меньшей $n$, и каждого возможного значения метки на следующей карте,
выбранная стратегия определяет, какую масть назовет экстрасенс. Покрасим черным те дуги, которые соответствуют правильному ответу, и белым --- соответствующие ошибке. Легко видеть, что из каждой вершины выходит не более
$a$ черных дуг, и не более $a(b-1)$ белых. Высота дерева равна $n$, оно имеет $N$ листьев, и каждый путь от корня к листу содержит не более $k$ белых дуг. Применяя Лемму со значениями $p=a$, $q=a(b-1)$, мы получаем требуемое неравенство.
\qed
Для превоначальной задачи с 36 картами, авторам известен алгоритм, гарантирующий не более 10 ошибок. Теорема \ref{main} дает в этом случае нижнюю оценку в 6 ошибок. Точный ответ остается неизвестным.
Авторы выражают благодарность интернет-проекту
LiveJournal ({\it www.livejournal.com}),
который оказался идеальным средством для организации совместной работы над
задачей. Авторы благодарят пользвателей {\it a\_konst} и {\it mi\_b} за ценные обсуждения, и все сообщество пользователей LiveJournal за постоянный интерес к процессу их работы.
\end{document}
Это будет в материалах нашей конференции; еще не совсем полноправная публикация.
А картинку, как я все это излагал, уже показывал.
