rem wrote: You have to organize a fair procedure to randomly select someone from $ n$ people so that every one of them would be chosen with the probability $ \frac {1}{n}$. You are allowed to choose two real numbers $ 0 < p_1 < 1$ and $ 0 < p_2 < 1$ and order two coins which satisfy the following requirement: the probability of tossing "heads" on the first coin $ p_1$ and the probability of tossing "heads" on the second coin is $ p_2$. Before starting the procedure, you are supposed to announce an upper bound on the total number of times that the two coins are going to be flipped altogether. Describe a procedure that achieves this goal under the given conditions. Taken from http://www.artofproblemsolving.com/Forum/viewtopic.php?p=967228#967228. My general approach to this--I'm not going to rigorously fill in all the details--is to pick a sufficiently large power of $ n - 1$--let's say $ (n - 1)^k$--such that "most" of the $ (n - 1)^k + 1$ integers $ \binom {(n - 1)^k}{0}$, $ \binom {(n - 1)^k}{1}$, $ \binom {(n - 1)^k}{2}$, ..., $ \binom {(n - 1)^k}{(n - 1)^k}$ are divisible by $ n - 1$. (If $ n - 1$ is prime this is very easy.) We then toss a coin--its heads probability not yet determined--exactly $ (n - 1)^k$ times. Our strategy is that if it comes up heads $ i$ times, and $ (n - 1)\not|\binom {(n - 1)^k}{i}$, to pick the first person--and if $ (n - 1)|\binom {(n - 1)^k}{i}$ to pick one of the remaining $ n - 1$ people. Because there are $ \binom {(n - 1)^k}{i}$ outcomes where there are $ i$ heads, all equally likely, these can be fairly assigned to the $ n - 1$ remaining people when $ (n - 1)|\binom {(n - 1)^k}{i}$. It remains only to pick the heads probability, $ p$, such that the probability of the number of heads satisfying $ (n - 1)|\binom {(n - 1)^k}{i}$ is exactly $ \frac {n - 1}{n}$. I claim that this is possible as long as "most" values of $ i$ satisfy $ (n - 1)|\binom {(n - 1)^k}{i}$. Specifically we require that $ \sum_{0\le i\le (n - 1)^k: (n - 1)|\binom {(n - 1)^k}{i}} \frac {1}{2^{(n-1)^k}} \binom {(n - 1)^k}{i} > \frac {n - 1}{n}$ and it should always be possible to satisfy this inequality if we pick $ k$ to be large enough. My question, though, is this approach actually requires only one coin, not two coins as contemplated by the problem. Although there are many individual values of $ n$ for which I can find a better solution--requiring fewer coin tosses--if we are allowed two coins, I cannot get any improvement in the general case of all $ n$--either in terms of elegance of solution or number of coin tosses required--by allowing two coins. The "worst case" which is attained for some values of $ n$ is pretty much as described above. So I'm wondering if others who solved this problem found the same thing or if having the second coin really helps us at all in the general case.

In a town of $n$ people, a president is to be elected. The people have decided that the best way to do this is randomly: they want to construct a random process that elects exactly one of the $n$ people, all with equal probability of being elected president. However, these are ancient times and the only way these people can obtain random results is by flipping a coin. However, they know that the process is probably impossible with a fair coin, so they have asked their blacksmith to build a skewed coin, which comes up heads with probability $p$ and tails with probability $1-p$, for some $0<p<1$. Is it always possible to choose an adequate $p$, such that the fair election of a president is possible?

I'm rooting for the blacksmith. (This problem is a generalization of the original problem, using only 1 coin).