Рыба
Успел из будущей статьи про экстрасенса написать только введение. Зато все результаты там сформулированы и определения даны, осталось только вписать доказательства :)


\documentstyle[12pt]{article}

\title{On a problem in sequential decoding}

\author{ahaxopet, flaass, garvej, jedal, relf}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\begin{document}
\maketitle

\section{Introduction}
The following amusing problem was given on a students' mathematical olympiad:

"A scientific committee tests the ability of a clairvoyant to guess card suits. The standard
36-deck of cards is paced before the clairvoyant face-down. He names the suit of the topmost card;
then opens it and removes from the deck; and so proceeds through the deck. It so happened that
the backs of cards are not symmetric: two possible orientations of a card can be distinguished.
The clairvoyant has bribed the assistant preparing the deck. The assistant cannot change the order
of cards in the deck, but he can choose the orientation of each card. How should the assistant and
the ckairvoyant act to minimize the number of wrong guesses?"

The problem can obviously be generalized. Suppose that we have $b$ suits, $n$ cards in the deck,
and $a < b$ different marks the assistant can leave on the backs of cards. What is $m_{a,b}(n)$,
the minimum number of wrong guesses the clairvoyant can guarantee not to exceed?

The set of allowed suit sequences can also vary. In the original problem, each suit should occur
the same number of times.
We can remove this restriction (allowing all $b^n$ sequences), or specify other sets.

In this note we give upper and lower bounds on $m_{a,b}(n)$ which asymptotically coincide.

Define a function
$$s_p(n,k)=\sum_{i=0}^k {n\choose i)p^i;$$
the partial sum of the binomial expansion.

\begin{theorem}\label{main}
a) If $s_{b-1}(n,k)\geq(b/a)^n$ then, for some constant $c$ depending on $a,b,n$,
for every natural number $m$ and every $r$, $1\leq r\leq n$,
the inequality $m_{a,b}(c+nm+r)\leq c+km$ holds, not depending on
the set of allowed suit sequences.

b) If $N$ is the number of allowed suit sequences of length $n$, and $s_{b-1}(n,k) < N/a^n$, then
$m_{a,b}(n) > k$.
\end{theorem}

The bounds given by Theorem \ref{main} asymptotically coincide when the number of allowed sequences
is $N=b^{n-o(n)}$ (as, for example, is the case when all sequences are allowed,
or when the only restriction is that each suit should occur the same number of times):

\begin{theorem}\label{limit}
If the number of allowed sequences of length $n$ is $b^{n-o(n)}$ then there exists a limit
$$\alpha(a,b)=\lim_{n\rightarrow\infty}\frac{m_{a,b}(n)}{n},$$
and this limit is the root $x$ of the equation
$$(b-1)^x=\frac{b}{a}x^x(1-x)^{1-x}.$$
\end{theorem}


\section{Upper bound --- algorithm}

\section{Lower bound --- game trees}

To prove the lower bound (part (b) of Theorem \ref{main}), we need one simple graph-theoretical lemma.

\begin{lemma}\label{tree}
Let $T$ be a rooted tree whose arcs (oriented outwards from the root) are colored black or white.
Let $T$ satisfy the following properties:

$(i)$ $T$ is of height $n$; that is, the distance from the root to every leaf is $n$;

$(ii)$ Out of every vertex there are at most $p$ black arcs and at most $q$ white arcs;

$(iii)$ Every path from the root to a leaf contains at most $k$ white arcs.

Then the number of leaves of $T$ is at most $p^n\cdot s_{q/p}(n,k)$.
\end{lemma}

\section{Asymptotics}

\section{Extras}

In this section, we describe the best known to the authors algorithm for the original olympiad problem.
Also, we say a few words on another version of the problem, when the suits of the cards are not shown
to the clairvoyant. This version is closely related to the well-known problem of finding optimal covering codes.

\section{Acknowledgements}
The authors are grateful to the internet project LiveJournal ({\tt www.livejournal.com}) which turned
out to be a perfect medium for discussions and for joint research.
The authors thank LiveJournal users {\tt a_konst} and {\tt mi_b} for their useful comments and discussions,
and the whole LiveJournal community for their interest.

\begin{thebibliography}[9]
\end{thebibliography}
\end{document}