Волейбол

5 волейболистов встали в круг и по очереди перебрасывают мяч друг другу. Каждый раз игрок, владеющий мячом, случайным образом выбирает, кому сделать передачу. Сколько в среднем передач они должны сделать, чтобы все хотя бы раз коснулись мяча?

4 мухи

4 мухи сидят на 4-х соседних по горизонтали клетках тетрадного листа. В каждый ход все 4 мухи одновременно переползают на соседние по горизонтали или вертикали клетки. Каждая муха выбирает направление независимо от других, причём остаться на месте, пропустив ход, она не может.

Могут ли мухи после определённой последовательности ходов расположиться в ряд по диагонали?

Примитивы синхронизации

Представьте, что Вы должны написать многопоточную программу на языке, в котором почти нет примитивов синхронизации. Единственное средство - функция TSL (test, set and lock), которая выглядит следующим образом:

int tsl(int* value) {
   int oldValue = *value;
   *value = 1;
   return oldValue;
}

При этом среда гарантирует, что функция атомарна. Например, что компилятор транслирует её в атомарную машинную инструкцию.

Как реализовать с помощью этого примитива критическую секцию? Оптимально было бы получить реализацию двух функций: lock() и unlock().

Гномы и колпаки

Людоеды поймали 1000 гномов и объявили, что на следующий день им предстоит испытание.

Всех гномов построят в колонну по одному и наденут всем колпаки красного и синего цветов в произвольном порядке. При этом каждый гном будет видеть, какого цвета колпаки у всех, кто стоит перед ним, но не будет знать свой собственный цвет. После этого людоед подойдёт к последнему гному в колонне и предложит ему угадать цвет своего колпака. Если гном угадает, его отпустят, если нет - убьют и съедят. После этого вопрос будет задан гному, который был предпоследним, а теперь оказался последним в очереди, и так до тех пор, пока в ней не останется гномов.

У гномов есть возможность посовещаться до начала испытания и договориться о стратегии. Как им нужно поступить, чтобы спаслось как можно больше? Передача информации интонацией запрещена: гном имеет право только сказать "красный" или "синий" максимально нейтральным тоном. Впрочем, он может сказать это достаточно громко, чтобы услышали все стоящие впереди.

Подсказка: при правильной стратегии выживут все гномы, кроме, быть может, одного.