Вот две задачи по терверу, которые сами по себе довольно простые и не неожиданные, но в них на мой вкус очень забавные ответы. Итак...

1. Представьте себе, что мы хотим сгенерировать случайный бит следующим странным способом. Возьмем очень-очень большое натуральное n и случайный двудольный граф, в каждой доле которого по n вершин. Посчитаем в нем количество совершенных паросочетаний (наборов из n ребер, которые не имеют общих концов). Четность этого количества и будет нашим битом. Какова вероятность, что этот бит будет равен нулю?

2. Представьте себе, что у нас есть n корзинок, в которые мы случайно бросаем шары. Мы продолжаем процесс, пока в каждой корзинке не будет по крайней мере m шаров. Сколько в среднем шаров мы бросим? Интересует ответ с точностью до константы. Например, хорошо известно, что если m = 1, то в среднем мы бросим шаров.