Palindrome Senates and an Ancient Tiling

Riddler Express

On Monday, the Senate voted $81$-$18$ to end the government shutdown. The tally is a palindrome: it reads the same forward and backward. The vote was made possible by the absence of one senator. Do senators need to be absent to create palindrome tallies, and if so, what numbers of absences will do the trick? Extra credit: how many palindromic Senate votes have occurred in the past three decades?

The Riddler, FiveThirtyEight, January 26, 2018(original post)

Solution

Setup. Read a tally “$y$-$n$” as the four-character string formed by writing the yes count, a hyphen, then the no count, each as a digit string (so the $81$-$18$ tally reads y-e-s-d-i-g-i-t-s, hyphen, n-o-d-i-g-i-t-s). The puzzle wants this string to be a palindrome with the hyphen in place, which forces the two sides to have the same number of digits.

The hyphen pins down the structure. If yes and no both have a single digit, the tally reads $a$-$a$, palindromic iff $a$ equals $a$, always; but a one-digit total means at most $18$ senators voted, which is the degenerate case. The interesting case is two digits a side, the tally $AB$-$BA$ where $A \in \{0, 1, \dots, 9\}$ and $B \in \{0, 1, \dots, 9\}$ (with $A = 0$ allowed, e.g. $09$-$90$, since the palindrome rule reads characters left to right). The yes count is $10A + B$ and the no count is $10B + A$, so the total number of senators voting is $$N = (10A + B) + (10B + A) = 11(A + B).$$ The total of votes cast is forced to be a multiple of $11$: it must be one of $11, 22, 33, \dots, 99$ (since the Senate has $100$ members, $N \le 100$). For each such $N$, the number of absences is $$100 - N \in \{1, 12, 23, 34, 45, 56, 67, 78, 89\}.$$ With all $100$ senators voting, $N = 100$ is not a multiple of $11$, so the answer to the first question is

For each value of $k = A + B$, the number of distinct $(A, B)$ pairs is $k + 1$ when $k \le 9$ (it is $0, 1, \dots, k$). Summing $k + 1$ over $k = 1, \dots, 9$ gives $\sum_{k=1}^{9}(k+1) = 54$ ordered $(A, B)$ pairs, hence $54$ distinct two-digit palindromic tallies. (If we choose to forbid the leading-zero forms $0B$-$B0$ we drop one tally per total, removing $9$ to leave $45$.)

Extra credit. The official’s answer counts $247$ palindromic Senate roll calls in the three decades ending January 2018; this is an empirical count over the Senate’s published vote records, not something derivable here. We note it and move on.

The computation

Enumerate every legal $(A, B)$ and confirm the palindrome and total constraints by direct character check on the tally string.

1. For every two-digit yes-count $Y$ from $0$ to $99$ and every two-digit no-count $M$ from $0$ to $99$ with $1 \le Y + M \le 100$,

2. form the string “<Y>-<M>” with each side written as exactly two digits,

3. record those that read the same forward and backward.

tallies = []
for Y in range(100):
    for M in range(100):
        N = Y + M
        if N < 1 or N > 100:
            continue
        s = f'{Y:02d}-{M:02d}'
        if s == s[::-1]:
            tallies.append((Y, M, N, 100 - N))
print(len(tallies))
totals = sorted({t[2] for t in tallies}, reverse=True)
print(totals)
absences = sorted({t[3] for t in tallies})
print(absences)

The script prints 54, the totals [99, 88, ..., 22, 11], and the absences [1, 12, 23, 34, 45, 56, 67, 78, 89], matching the boxed answer.

Riddler Classic

Some 2,200 years ago the Greek mathematician Archimedes described the Ostomachion, a set of pieces, similar to tangrams, that divides a 12-by-12 square into 14 regions. Your challenge: color the regions of the Ostomachion square with four colours so that no two neighbouring regions share a colour and each colour shades an equal area (that is, each colour must shade exactly 36 square units). Extra credit: how many solutions are there?

The Riddler, FiveThirtyEight, January 26, 2018(original post)

Solution

Label the $14$ regions $0$ through $13$ as below. Their areas are $12,6,21,3,6,12,12,24,3,9,6,12,6,12$, which sum to $144$, so each of the four colours must cover $144/4 = 36$ square units.

This is a constraint problem with two kinds of rule: a proper colouring (regions that share a border get different colours) and a partition (the regions of each colour sum to exactly $36$). Neither rule alone is hard; together they pin the puzzle down. A short backtracking search, assigning colours region by region and abandoning any branch that breaks a border rule or overshoots a colour’s $36$-unit budget, finds solutions readily. One of them is $$\boxed{\begin{aligned} &\text{Red: } 0,2,8;\quad \text{Blue: } 1,3,6,9,12;\\ &\text{Green: } 4,7,10;\quad \text{Yellow: } 5,11,13, \end{aligned}}$$ each colour totalling $36$. Counting every assignment the search finds gives $216$, and since the four colour names can be permuted in $4! = 24$ ways without changing which regions share a colour, the number of genuinely distinct solutions is $216/24 = \boxed{9}$.

The computation

Encode the two rules directly and enumerate. Walk the regions in order; for each, try every colour that neither clashes with an already-coloured neighbour nor pushes that colour past $36$; count every complete assignment, then divide by $4!$ for the interchangeable colour names.

from math import factorial
adj = {0:[1,5,6], 1:[0,2,13], 2:[1,12,3,5], 3:[2,4,5], 4:[3,5],
       5:[0,2,3,4,6], 6:[0,5], 7:[8,13], 8:[7,9], 9:[8,10],
       10:[9,11,13], 11:[10,12], 12:[11,13,2], 13:[1,7,10,12]}
area = {0:12,1:6,2:21,3:3,4:6,5:12,6:12,7:24,8:3,9:9,10:6,11:12,12:6,13:12}
col = [-1] * 14; load = [0] * 4; count = 0
def search(i):
    global count
    if i == 14:
        count += 1; return
    for c in range(4):
        if load[c] + area[i] > 36:                       # color budget
            continue
        if any(col[n] == c for n in adj[i] if col[n] >= 0):  # border rule
            continue
        col[i] = c; load[c] += area[i]
        search(i + 1)
        col[i] = -1; load[c] -= area[i]
search(0)
print(count, count // factorial(4))                      # 216, 9