\documentclass[12pt,a4paper,russian]{article}

\usepackage[koi8-r]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath,amssymb}
\usepackage{enumerate}

\topmargin -0.4cm
\headsep=0.0cm
\headheight=0.0cm
\textheight 24.6cm
\oddsidemargin -0.3cm
\evensidemargin -0.3cm
\textwidth 15.9cm

\begin{document}
\thispagestyle{empty}
\begin{flushright}
\it Задачи к семинарам по курсу \\
``Численные методы'' для 443 группы\\
кафедры физики частиц и космологии
\end{flushright}

\newcommand{\lnum}{8}
\begin{center}
  к лекции {\lnum} ``Алгоритмы потоковой обработки данных.'' 
\end{center}

\renewcommand{\labelenumi}{{\bf \lnum.\arabic{enumi}}}
\begin{enumerate}

\item N заключенных Кощеев бессмертных посадили пожизненно в одиночные
  камеры. Каждый день надзиратель приводит одного из них в общую
  комнату на 5 минут. В комнате находится выключатель, связанный с
  идеальной лампочкой (не имеющей физических свойств кроме состояния
  горит/не горит). За посещение заключенный вправе на свое усмотрение
  оставить выключатель в том же состоянии или переключить в другое
  состояние. Работники тюрьмы не меняют состояние выключателя,
  начальное состояние лампочки - выключенное. Последовательность
  приводов случайна (или подобрана с умыслом против заключенных), но
  для любого заданного момента времени каждый заключенный обязательно
  попадет в данную комнату через некоторое конечное время. Любой
  заключенный может сказать ``В этой комнате уже все N Кощеев побывали
  хотя бы один раз''. Если это окажется правдой, то всех отпустят,
  если ложь - всех казнят. До заключения все Кощеи собираются вместе и
  могут договориться о стратегии. Требуется стратегия 100\%
  гарантируюшая освобождение.

\item В комнате 100 ящиков, в которые в случайном порядке помещены
таблички с номерами от 1 до 100 (по одной табличке с каждым
номером). 100 заключенных с порядковыми номерами от 1 до 100 по
очереди заводят в комнату. Каждый заключенный может последовательно
открыть 50 ящиков. Если заключенный не встретит табличку со своим
порядковым номером, то всех казнят. Заключенные могут договориться
между собой об алгоритме, но после этого не взаимодействуют между
собой. При каком алгоритме вероятность выжить максимальна?


\item * Змей Горыныч поймал счётное количество эльфов и сообщил им,
что тех, кто не угадает цвет своего колпака, он съест. Угадывать
предлагается в следующих условиях. Эльфы становятся в бесконечную
колонну так, что 1-ый видит хвост колонны от 2-го до бесконечности,
2-й - хвост от 3-го до бесконечности и так далее. На них
материализуются колпаки черных и белых цветов. Каждый эльф знает свой
номер в колонне и видит колпаки на всех, кто стоит перед ним, но не
видит на себе и не на тех, кто сзади. Свои предполагаемые цвета все
эльфы называют одновременно. До построения всем эльфам даётся время на
то, чтобы договориться о стратегии. Каждый эльф обладает
неограниченной вычислительной мощностью и бесконечной
памятью. Придумать стратегию, с помощью которой при любом исходе будет
съедено лишь конечное число эльфов.


\end{enumerate}

\end{document}