Card game only by talking - e.g. werewolf

Question

Recently I was wondering if it was possible to play card games with my math friends without having anything else than communication (no computing device, no sheets of paper), e.g. to play werewolf or mafia without cards.

Formally, for n cards and n players, I want an algorithm such that:

• At the end, each player is assigned a number between 1 and n
• All assigned numbers are different
• No player knows the assigned numbers of other players without doing a substantial computation that one can easily not think about.
• All computations can be done in a reasonable time by a human brain.
• Nothing is secret except internal thinking

I was able to devise a probabilistic algorithm that seems to work for n=3

1. Each player independently picks a random number between [1,3,5]
2. Each player creates a 3-digit number whose modulo 7 is the chosen random number.
3. Each player shares its 3-digit number.
4. If the sum of these three numbers modulo 7 is 2 and the product modulo 7 is 1, then we have the guarantee that these numbers are 1, 3 and 5 in any order. If not, restart at 1.
5. Add 1 to the chosen number and divide by 2.

However, there is only 6 chances over 27 that this algorithm works... Could there be an algorithm that always works? For example that obtains permutation in an uniform way, such that each participant is expected to compute their own card number? And for more cards?

Answer 1

Obviously whether a computation is in your "Goldilocks zone":

• a substantial computation that one can easily not think about, but

• can be done in a reasonable time by a human brain

is entirely a matter of opinion. If you take the (dubious) position that modulo arithmetic qualifies, then here is a scheme that works all the time (i.e. no re-tries needed), for $n=3$ (I'm not sure if it's generalizable).

The basic idea is to randomly generate a number modulo $6$, and then map each residue to one of the $3!$ possible permutations. The harder (and fun) part is to invent computations that are contrived enough and that will only calculate a player's own position in the permutation.

Generating a random number mod $6$ is easy enough: Everyone independently picks a uniform $32$-bit unsigned integer and publish it. (If you insist on precision, round up or down from $2^{32} - 1$ to the next multiple of $6$.) Let $S$ be the sum of the $3$ integers. We have $S = 6k + r$ where $r$ is the residue and $r \sim Uniform(\{0,1,2,3,4,5\})$.

This table describes how $r$ maps to a permutation. The columns A, B, C denote what card each player will receive as a function of $r$:

r | A  B  C
--|--------
0 | 0  1  2
1 | 0  2  1
2 | 1  2  0
3 | 1  0  2
4 | 2  0  1
5 | 2  1  0

It so happens these $3$ formulas work:

• $A = \lfloor r/2 \rfloor \pmod 3 = \lfloor S/2 \rfloor \pmod 3$

• $B = \lfloor (r-3)/2 \rfloor \pmod 3 = \lfloor (S-3)/2 \rfloor \pmod 3$

• $C = (2 - r) \pmod 3 = (2 - S) \pmod 3$

So, this solution is acceptable to the extent that these computations are in your "Goldilocks zone" (IMHO dubious). I have some additional concern that a human doing $A$ (or $B$) might "unintentionally" notice the answer to $B$ (or $A$). Perhaps in $B$, instead of $(r-3)$ it might be more confusing (to a human) if we use e.g. $(r - 6666663)$. :)