Another
generalization of this
problem is if there are n
people and you need to make a
decision using an m-sided
coin. First,
enumerate all the
outcomes, i.e., each outcome gets a
unique number between 0 and m-1. Then, each person
randomly chooses a number between 0 and m-1,
inclusive, and everyone
announces their number
simultaneously (on
fingers, or
what have you*). The
sum modulo m of these numbers is the outcome we choose.
Since each person is equally likely to choose any number between 0 and m-1, the sum modulo m of these numbers is also equally likely to be anywhere between 0 and m-1. Note that the randomness of this algorithm is independent of n, the number of people that pick numbers at random. Furthermore, no person can introduce bias (cheating is impossible) because no one knows what the other randomly chosen numbers will be. For example, should I decide that choosing 5 will give me an unfair advantage, 5 added to a random number (everyone else's numbers) is just as random, so I really have no unfair advantage.
If we let m=n, this is a simple coordinator election algorithm (i.e., for choosing who sits shotgun,etc.)
*note that you can represent a range of 1024 numbers on ten fingers if you use a binary representation instead of unary, so we're not limited to m being at most 10.