In one city, $N$ Petya, Vasya and Tolya hide from zombies in an underground bunker. But they have no connection with the outside world and they don’t know if the zombies remained in the city or left. They decided that someone needs to go out and find out the situation. they will throw a coin. Think about how to organize the tossing process so that they have an equal chance of being on the surface?

I tried to count the probabilities but nothing came of it . Please help to solve it.

  • $\begingroup$ I’m not sure what the problem is asking. $\endgroup$ – NicNic8 Mar 29 '20 at 16:41
  • $\begingroup$ @JeanMarie In my opinion... $\endgroup$ – IPHO2022 Mar 29 '20 at 16:41
  • 1
    $\begingroup$ Could you explain what probabilities you "tried to count"? $\endgroup$ – prt13463 Mar 29 '20 at 16:45
  • $\begingroup$ @prt13463 I don’t know, I counted something there, but nothing worked... $\endgroup$ – IPHO2022 Mar 29 '20 at 16:49
  • $\begingroup$ See also math.stackexchange.com/questions/2898509. $\endgroup$ – joriki Mar 29 '20 at 18:09

First, a simple method : they toss twice their coin, keeping memory of the order (heads = 0 or tails = 1) :

  • if it is 00, choose Petya,

  • if it is 01, choose Vasya

  • if it is 10, choose Tolya

  • if it is 11, they repeat the process (toss again twice their coin...) until it is no longer outcome (11).

The process terminates with probability 1. This very simple algorithm can be called recursive (terminal recursivity).

Second : a more sophisticated approach, the Rao-Sandelius algorithm :

Selecting one person (in a uniform manner) among $n$ can be casted into a more general issue : generating a random (equiprobable) permutation of the $n$ persons; being undestood that finally, one has to keep the first ranked person.

This could be useful even in your problem in case the first chosen person doesn't come back in your scenario...

The algorithm we are going to describe uses three (+ eventually one) ordered tosses of a coin. Its principle is as follows for 3 entities $a,b,c$ (the new names of our heroes). We want to attribute them an equiprobable order among:

$$\{abc, \ \ acb, \ \ bac, \ \ bca, \ \ cab, \ \ cba\}$$

We place $a,b,c$ on consecutive chairs. We flip a coin in front of each one. Those who have received a "0" (if any) take the first chair(s), the others the remaining chairs.

  • In the case where two "zeros" (exactly) have been given, a fourth flip of the coin will say if the persons occupying the front chairs will stay still (case $0$) or exchange their places (case $1$).

  • A symmetric case of move will be done if there are exactly two "ones" (being understood that the third person having received a "0" remains seated in the front chair) : if the fourth flip indicates $0$, they stand still, otherwise, they commute their places.

  • If all flips have given the same result, either $000$ or $111$, we flip the coin three + one times again.

Here are the different outcomes ( = rankings) generated by this algorithm :

$$\begin{cases}000&&\text{flip again}\\ 001&\text{abc}&\\ 001&\text{bac}&a\leftrightarrow b\\ 010&\text{acb}&\\ 010&\text{cab}&a\leftrightarrow c\\ 011&\text{abc}&\\ 011&\text{acb}&b\leftrightarrow c\\ 100&\text{bca}&\\ 100&\text{cba}&b\leftrightarrow c\\ 101&\text{bac}&\\ 101&\text{bca}&a\leftrightarrow c\\ 110&\text{cab}&\\ 110&\text{cba}&a\leftrightarrow b\\ 111&&\text{flip again} \end{cases}$$

$12$ "terminal cases" with each permutation present twice.

Therefore, each permutation is likely to appear with the same probability $1/6$.

In the "non-attributed cases" $000, \ \ 111$, the coin is flipped three times again (+ eventually one time). Here also, the process terminates with probability $1$.

I give an implementation of this recursive algorithm (Matlab program) because it can help to understand in a different way how we operate:

function main;
clear all;close all;
rp=RP, % random permutation requested
function rp=RP
rb=@(n)(rand(1,n)>0.5);%random list of n bits (0/1)
L=rb(3);% let us assume that 1 0 1 has been obtained
% that we place in front of the numbers 1 2 3 
z=find(L==0); % then z=[2] : list of people with a "0" in font of their number
u=find(L==1); % and u=[1 3] : the same for a "1"
rp=[z,u]; % "a priori", we place people with a "0" first, then with a "1"
switch length(z) % according to the length of "z"
    case 1, % if z has a single element, u has 2 elements that 
        % can be "flipped" if random bit rb(1) is equal to 1 :
        if rb(1);rp=[z,fliplr(u)];end; 
    case 2,
        if rb(1);rp=[fliplr(z),u];end; % symmetrical case here
    otherwise, rp=RP; % recursive call

This algorithm for $n=3$ persons isn't worth using it because it is more complicated than the first proposal and demanding more coins' flips. Its interest is for generating permutations for any number of persons (see reference below).

Reference : You will find different coin-flipping sorting algorithms there. Rao-Sandelius algorithm is explained on page 5 of this document.

  • $\begingroup$ I did not find anything (did not understand), can you write a solution? $\endgroup$ – IPHO2022 Mar 29 '20 at 16:56
  • $\begingroup$ I didn’t understand anything, here are some kind of integrals, vectors, differentials, I don’t know them, I'm a schoolboy. Can You write a solution here? $\endgroup$ – IPHO2022 Mar 29 '20 at 17:06
  • $\begingroup$ I have tried to be more explicit for the Rao-Sandelius algorithm. $\endgroup$ – Jean Marie Mar 31 '20 at 16:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.