Волейбол

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

4 мухи

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

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

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

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

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

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

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

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

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

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

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

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

Презервативы

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

2 пловца

Два пловца одновременно стартуют по одной дорожке от одного бортика бассейна и плавают туда-сюда с постоянными скоростями. Один проплывает бассейн от одного бортика до противоположного за 11 минут, а второй - за 30 минут. Достигнув бортика, они мгновенно разворачиваются и начинают плыть в обратном направлении с прежней скоростью. Пловцы остановятся, когда оба одновременно окажутся у того бортика, с которого они стартовали. Сколько раз за это время быстрый пловец догонит медленного?

Пользуясь случаем, хочу передать привет Рустему, рассказавшему мне эту задачу два года назад.

Уснуть и видеть сны

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

Иногда бывает такое, что я просыпаюсь только для того, чтобы понять, что на самом-то деле я всё ещё сплю. Каждый раз, когда это случается, я чувствую себя несколько не в своей тарелке. Чтобы этого избежать, я начал считать уровни рекурсии, погружаясь в сон:

public class Sleeper {
    private int level;
    public synchronized int enter(Dream dream) {
        level++;
        try {
            dream.dream(this);
        } finally {
            level--;
        }
        return level;
    }
}

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

Теперь я со спокойной душой ложусь спать следующим образом:

public class Main {
    public static void main(String[] args) {
        if (new Sleeper().enter(new Dream()) != 0) {
            // The goal is to reach this line
            System.out.println("Am I still dreaming?");
        }
    }
}

Есть ли ошибка в моих рассуждениях? Можно ли написать такой класс Dream, что он сломает мою программу, и она напечатать помеченную строку? Изменять классы Sleeper и Main нельзя.

public class Dream {
    public void dream(Sleeper s) {
        // TODO implement me
    }
}

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