Это модификация задачи, использованной на официальном раунде. К сожалению, авторское решение к оригинальной формулировке оказалось неверным, поэтому задача была изменена специально для архива.

Жил да был в Тридевятом царстве Царь, и была у него прекрасная дочь Василиса. Жили они не тужили, пока не случилась беда лихая: налетел на Тридевятое царство злобный Змей Горыныч и украл Василису. Закручинился Царь, однако собрал своих храбрых молодцев, и пообещал полцарства и руку дочери тому, кто спасет его дочь от супостата иноземного.

Долго ли, коротко ли, нашли молодцы логово Змея Горыныча, и завалились в него спасать Василису Прекрасную всей толпой. Каждый из них плюнул в супостата один раз, и, будучи очень нежным и легкоранимым существом, бедный Змей Горыныч умер от разрыва сердца. Храбры же молодцы доставили Василису Прекрасную Царю и передрались из-за того, кому же достанется ее рука.

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