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*.