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 choose
s a number between 0 and m-1, inclusive
, and everyone announce
s their number simultaneous
ly (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.