World Cup Standings and Number Shuffling

Riddler Express

In the World Cup group stage, a group of four teams plays a round robin: every team plays the other three once. A win is worth $3$ points, a draw $1$ point, and a loss $0$ points. For a given group, how many different final standings, including point totals, are possible?

The Riddler, FiveThirtyEight, March 23, 2018(original post)

Solution

Read the question carefully. A "final standing including point totals" is an assignment of a point total to each of the four named teams, so the answer is the count of distinct $4$-tuples $(P_A, P_B, P_C, P_D)$ over all possible round-robin outcomes, not the count of unordered point multisets. Two different game-by-game outcomes can yield the same tuple, so the answer is below the naive $3^6 = 729$.

Why the naive count is $729$. Six games are played (each pair plays once), and each game has three outcomes: team $i$ wins, draw, or team $j$ wins. So there are $3^6 = 729$ game-by-game outcomes, each of which determines a point tuple.

Why $729$ overcounts. Several distinct game-outcome assignments produce the same point tuple. The cleanest example is a $3$-cycle: if $A$ beats $B$, $B$ beats $C$, $C$ beats $A$, every team in the cycle gains $3$ and loses $3$, just as if the wins ran the other way ($B$ beats $A$, $C$ beats $B$, $A$ beats $C$). Holding the three games involving $D$ fixed, those two outcomes give the same $(P_A, P_B, P_C, P_D)$. There are also less obvious coincidences (for example, replacing two wins by two draws keeps a team’s total at $3 + 0 = 1 + 1 \cdot 2 =$ wait, $3$ vs $2$, not equal; cancellations are rarer than the $3$-cycle case but exist for $4$-team configurations).

Direct count. The cleanest path is direct enumeration. Run through all $3^6 = 729$ assignments, compute the point tuple, and take the cardinality of the resulting set. The answer is $$\boxed{\,556\,\text{distinct standings.}\,}$$

Reconciliation with the official’s bookkeeping. The official write-up reaches $556$ by listing every unordered point multiset that can occur, counting (a) the number of distinct game-outcome constructions producing each multiset and (b) the number of permutations of the multiset over the four teams. For multisets such as $\{4,4,4,4\}$ the six constructions all give the single tuple $(4,4,4,4)$, so the construction redundancy is $6 - 1 = 5$. Summing redundancies across all multisets yields $173$ duplicates, and $729 - 173 = 556$. Direct enumeration confirms.

The computation

Brute-force every round-robin outcome and count distinct point tuples.

1. List the six unordered pairs of teams.

2. Loop over the $3^6 = 729$ outcome assignments; for each, accumulate points.

3. Collect the resulting point tuples in a set and report its size.

from itertools import product

games = [(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]
standings = set()
for outcome in product(range(3), repeat=6):
    pts = [0, 0, 0, 0]
    for (i, j), o in zip(games, outcome):
        if o == 0:   pts[i] += 3                # i wins
        elif o == 1: pts[i] += 1; pts[j] += 1    # draw
        else:        pts[j] += 3                # j wins
    standings.add(tuple(pts))
print("distinct (P_A, P_B, P_C, P_D) tuples:", len(standings))

The script prints $556$.

Riddler Classic

Take a positive integer and move its last digit to the front. For example, $1{,}234$ becomes $4{,}123$. What is the smallest positive integer such that this operation yields exactly twice the original?

The Riddler, FiveThirtyEight, March 23, 2018(original post)

Solution

Write the mystery number as $N = 10b + a$, where $a$ is its last digit and $b$ is the block of $n$ digits in front. Moving the last digit to the front puts $a$ in the $10^n$ place, giving $a \cdot 10^n + b$, and we want this to equal $2N$: $$a \cdot 10^n + b = 2(10b + a) \quad\Longrightarrow\quad a\,(10^n - 2) = 19\,b.$$ The right side is a multiple of $19$, and since $a$ is a single digit not divisible by $19$, the factor $10^n - 2$ must be. So we need $10^n \equiv 2 \pmod{19}$, and the smallest valid $N$ is the one with the smallest such $n$.

The powers of $10$ modulo $19$ cycle with period $18$, running $10, 5, 12, 6, 3, 11, 15, 17, 18, 9, 14, 7, 13, 16, 8, 4, 2, 1$. The value $2$ first appears at $n = 17$. Then $b = a \cdot (10^{17} - 2)/19 = a \cdot 5{,}263{,}157{,}894{,}736{,}842$, and $b$ must itself have exactly $17$ digits. Taking $a = 1$ gives only a $16$-digit $b$ (a leading zero, not allowed), so the smallest valid digit is $a = 2$, giving $b = 10{,}526{,}315{,}789{,}473{,}684$ and $$N = 10b + a = \boxed{105{,}263{,}157{,}894{,}736{,}842}.$$ Indeed $2N = 210{,}526{,}315{,}789{,}473{,}684$, which is $N$ with its final $2$ moved to the front.

The computation

Find the smallest $n$ with $10^n \equiv 2 \pmod{19}$, build the number from $a = 2$, and check directly that moving its last digit to the front doubles it.

n = 1
while pow(10, n, 19) != 2:
    n += 1
b = (10**n - 2) // 19 * 2          # a = 2
N = 10 * b + 2
rotated = int(str(N % 10) + str(N // 10))   # last digit to the front
print(n, N, rotated == 2 * N)               # 17, 105263157894736842, True