Друзья, представляю вам пса Палтуса, нового члена редакции и единственного настоящего американца в нашей больнице. Он представляет из себя сардельку породы Вельш-корги пемброк (Pembroke Welsh Corgi), которая сначала открывает рот, а потом только ищет, что в него засунуть.

Пёс ожидаемо становится звездой инстаграма Нади, поэтому советую заранее подписаться или отписаться, в зависимости от вкуса. Ну и напомню про свой тогда уж.

Далее — решение задачи про загаданные числа и монетку. Если вы ещё над ней думаете, советую продолжать думать.

*

*

*

*

*

*

*

*

*

*

В общем, оказывается, что всё довольно просто. Итак, оппонент сказал вам число X.

Пример решения от Ярика: вы начинаете подбрасывать монетку до тех пор, пока не выпадет орёл. Число получившихся подбрасываний минус один — целое число Y, которое вам скоро пригодится. Бросаем монетку ещё раз, и у числа Y появляется знак. Так вот, если Y<X, то вы отвечаете, что X это большее из двух. Если Y>X, то отвечаете, что оно меньшее. Иначе повторяете процедуру.

Более общее решение таково. Подбираем функцию f(x) так, что она:

• непрерывно возрастает;
• стремится к 0 при аргументе стремящемуся к минус бесконечности;
• стремится к 1 при аргументе, стремящемуся к плюс бесконечности.

Например, f(x)=arctan(x)/pi+1/2.

Берём значение f(X) (напоминаю, что X нам сказал оппонент), подбрасываем монетку сколько надо раз, чтобы с вероятностью f(X) ответить, что X это большее из двух чисел, а с вероятностью 1-f(X) ответить, что меньшее. Можно доказать, что шанс угадать будет 1/2+(f(b)-f(a))/2, где a<b — первоначально загаданные оппонентом числа.

Пёс Палтус задумался, как сгенерировать событие с вероятностью f(X), если f(X) иррационально? В нашем случае это не проблема, на самом деле. Поскольку аргумент всегда целый, то f(X) всегда можно округлить так, чтобы оно всё же отличалось от f(X-1) и f(X+1). Округлённое значение всегда рационально, а значит событие с такой вероятностью всегда можно сгенерировать монеткой.

Все доказательства и опровержения — на дом и в комменты.