Chapter 274

Can You Cheat At Rock, Paper, Scissors?

The Riddler for July 31, 2020. The Express is a sudden-death rock-paper-scissors final against an opponent whose two possible throws you can read each round. The Classic lines a graduating class around a circle and asks when a relative-position coincidence is forced.

Riddler Express

In sudden-death rock-paper-scissors (first to win a round takes the title, ties replay), you can read your opponent each round: they will play one of two throws, each with probability $\tfrac12$ , and you can tell which pair it is, $\{$ rock, paper $\}$ , $\{$ paper, scissors $\}$ or $\{$ rock, scissors $\}$ . Playing optimally, what is your chance of winning the tournament?

The Riddler, FiveThirtyEight, July 31, 2020(original post)

Solution

Each throw is beaten by exactly one other throw, so to never lose a round you just avoid the throw your opponent could beat, and play the one that beats one of their two options while tying the other: $\begin{aligned} \{\text{rock, paper}\} &\to \text{paper}, &\quad \{\text{paper, scissors}\} &\to \text{scissors},\\ \{\text{rock, scissors}\} &\to \text{rock}. \end{aligned}$ Take $\{$ rock, paper $\}$ : paper beats rock and ties paper, and your opponent never throws scissors, so paper cannot lose. In every category such a safe throw exists, so each round you win with probability $\tfrac12$ and tie with probability $\tfrac12$ , never losing. A tie just replays (a fresh round, again unlosable), so your chance of having won by round $k$ is $\tfrac12 + \tfrac14 + \tfrac18 + \cdots$ , which sums to $\boxed{100\%}.$ You are guaranteed to win eventually.

The computation

Encode the rounds: each round draws the opponent’s category, you play the safe throw, and the match ends on the first non-tie (always a win). Over many matches the win rate is $1$ .

import random
rng = random.Random(0)
beats = {'R': 'S', 'P': 'R', 'S': 'P'}              # key beats value
safe = {frozenset(c): t for c, t in
        [('RP', 'P'), ('PS', 'S'), ('RS', 'R')]}    # never-lose throw per category
wins = 0
for _ in range(200_000):
    while True:
        cat = rng.choice(['RP', 'PS', 'RS'])
        opp = rng.choice(cat)
        me = safe[frozenset(cat)]
        if me == opp: continue                       # tie -> replay
        wins += beats[me] == opp                     # always true here
        break
print(wins / 200_000)                                # 1.0

You win every match, a probability of $100\%$ .

Riddler Classic

More than $100$ graduates stand around a circle. They should be in rank order (Val at a fixed spot, the rest counterclockwise). In the actual arrangement everyone but Val is misplaced, and the principal claims no two are in the correct position relative to each other (graduates $A$ and $B$ are correct relative to each other if $A$ is as many places counterclockwise of $B$ as intended). Val argues such an arrangement is impossible for this class size. What is the minimum number of graduates?

The Riddler, FiveThirtyEight, July 31, 2020(original post)

Solution

Number the $N$ positions $0$ to $N-1$ and let graduate intended for spot $i$ actually stand at spot $\sigma(i)$ . Two graduates $i$ and $j$ are correct relative to each other exactly when $\sigma(i) - \sigma(j) \equiv i - j \pmod N$ , that is, when their displacements $E(i) = \sigma(i) - i \pmod N$ are equal. So “no two correct relative to each other” means all $N$ displacements are distinct, hence are a permutation of $0, 1, \ldots, N-1$ .

Now sum the displacements. The actual spots and the intended spots are both the full set $\{0, \ldots, N-1\}$ , so $\sum_i E(i) = \sum_i \sigma(i) - \sum_i i \equiv 0 \pmod N$ . But if the displacements are all distinct, their sum is $0 + 1 + \cdots + (N-1) = \tfrac{N(N-1)}{2}$ . This is a multiple of $N$ only when $N$ is odd (for $N$ even it equals $\tfrac{N}{2}$ modulo $N$ ). So an arrangement with no relative coincidence exists only when $N$ is odd; when $N$ is even, two graduates are always correct relative to each other. Val’s argument therefore forces $N$ even, and the smallest such class above $100$ is $\boxed{102}.$

The computation

Encode the claim: search for an arrangement with Val fixed and all displacements distinct (a complete mapping). It exists exactly for odd $N$ , so the least even $N > 100$ is the answer.

from itertools import permutations
def coincidence_free_exists(N):          # Val fixed at 0, all displacements distinct
    return any(s[0] == 0 and len({(s[i]-i) % N for i in range(N)}) == N
               for s in permutations(range(N)))
for N in range(3, 9):
    print(N, coincidence_free_exists(N))            # True for odd, False for even
print(next(N for N in range(101, 200) if N % 2 == 0))   # 102

A coincidence-free arrangement exists only for odd $N$ , so the minimum even class size above $100$ , where a relative coincidence is forced, is $102$ .