A Reusable Calendar and the Game of Hip

The Riddler for January 6, 2017. The Express hunts a year whose calendar waits an unusually long time to return; the Classic is Martin Gardner’s square-dodging board game.

Riddler Express

Sometime in the 21st century someone says: “Don’t throw out that calendar, you can reuse it in 40 years, and in fact this calendar has never had a 40-year gap before.” What year is it?

The Riddler, FiveThirtyEight, January 6, 2017(original post)

Solution

A year’s calendar is fixed by two things: which weekday January 1 falls on, and whether it is a leap year. A calendar can only return on a year with the same pair. Common years recycle quickly, every 6 or 11 years; leap-year calendars normally return after 28 years, because $28$ is the smallest multiple of both $4$ (the leap cycle) and $7$ (the weekday cycle).

The 28-year rhythm breaks whenever the gap would span a centurial year that the Gregorian rule denies a leap day, $1700$, $1800$, $1900$, $2100$, none of which is divisible by $400$. Skipping that leap day shifts the weekday count and stretches the gap from $28$ to $40$ years. In the 21st century the culprit is $2100$, and the leap years whose next recurrence straddles it are $2072, 2076, 2080, 2084, 2088$. The clue “never had a 40-year gap before” singles out the earliest of these, the one whose calendar (a leap year starting on a Friday, like $2016$) is making this long jump for the first time: $$\boxed{2072},$$ which next repeats in $2112$. The other candidates share their calendars with earlier leap years that already made a 40-year jump across $1800$ or $1900$, so only $2072$ fits “never before”.

The computation

Encode the calendar test, weekday of January 1 plus leap status, find each year’s next recurrence, and list the 21st-century years whose gap is 40. The earliest is the answer, and it straddles $2100$.

from datetime import date
def cal_type(y):
    leap = (y % 4 == 0 and y % 100 != 0) or (y % 400 == 0)
    return (date(y, 1, 1).weekday(), leap)        # 0=Mon .. 4=Fri
def next_reuse(y):
    yy = y + 1
    while cal_type(yy) != cal_type(y): yy += 1
    return yy
gap40 = [y for y in range(2001, 2101) if next_reuse(y) - y == 40]
print("21st-century years with a 40-year gap:", gap40)
print("earliest:", gap40[0], "-> reuses in", next_reuse(gap40[0]),
      "; Friday-start leap?", cal_type(gap40[0]) == (4, True))
# 21st-century years with a 40-year gap: [2072, 2076, 2080, 2084, 2088]
# earliest: 2072 -> reuses in 2112 ; Friday-start leap? True

Riddler Classic

In Hip, two players take turns placing their checkers on an $N\times N$ board. A player loses if four of their own checkers ever form the corners of a square, of any size and tilted to any angle. What is the largest board on which the game can end in a draw, with the whole board filled and neither colour forming a square?

The Riddler, FiveThirtyEight, January 6, 2017(original post)

Solution

A draw means the $N^2$ cells can be two-coloured, evenly, with neither colour containing four cells at the corners of a square, including the many tilted squares whose vertices are lattice points (like the one through $(0,1),(1,3),(3,2),(2,0)$). The largest board that admits such a colouring is $$\boxed{6\times 6}.$$ A $6\times 6$ board has $105$ squares of all sizes and tilts, and they can all be avoided. One drawn board (W and B for the two colours), found by local search and verified below, is $$\begin{array}{cccccc} \textsf{B}&\textsf{W}&\textsf{W}&\textsf{W}&\textsf{B}&\textsf{W}\\ \textsf{W}&\textsf{W}&\textsf{B}&\textsf{B}&\textsf{B}&\textsf{B}\\ \textsf{B}&\textsf{W}&\textsf{W}&\textsf{B}&\textsf{W}&\textsf{B}\\ \textsf{B}&\textsf{W}&\textsf{B}&\textsf{W}&\textsf{W}&\textsf{B}\\ \textsf{B}&\textsf{B}&\textsf{B}&\textsf{B}&\textsf{W}&\textsf{W}\\ \textsf{W}&\textsf{B}&\textsf{W}&\textsf{W}&\textsf{W}&\textsf{B} \end{array}$$ with $18$ of each colour and not one monochromatic square. For every board larger than $6\times 6$ no such colouring exists: on a $7\times 7$ board the minimum number of monochromatic squares forced is $3$, never $0$, and since no $7\times 7$ board can have all four of its overlapping $6\times 6$ corners be valid $6\times 6$ solutions, the impossibility propagates to all larger boards. So $6\times 6$ is the last board that can be drawn.

The computation

Encode the square-detection exactly: enumerate every square (all sizes and tilts) whose four vertices lie in the grid, then verify the exhibited $6\times 6$ board has none monochromatic. The same enumerator, run as the scoring function inside a search, is what produced the board.

def squares(n):                              # all axis-aligned and tilted squares in n x n
    S = set()
    for x in range(n):
        for y in range(n):
            for dx in range(-n, n + 1):
                for dy in range(0, n + 1):
                    if dx == 0 and dy == 0: continue
                    pts = [(x, y), (x + dx, y + dy),
                           (x + dx - dy, y + dy + dx), (x - dy, y + dx)]
                    if all(0 <= a < n and 0 <= b < n for a, b in pts):
                        S.add(frozenset(a * n + b for a, b in pts))
    return [tuple(s) for s in S]

board = ["BWWWBW", "WWBBBB", "BWWBWB", "BWBWWB", "BBBBWW", "WBWWWB"]
col = [1 if ch == "B" else 0 for row in board for ch in row]
SQ = squares(6)
mono = sum(all(col[c] == col[sq[0]] for c in sq) for sq in SQ)
print("6x6 squares:", len(SQ), " colours:", col.count(0), "/", col.count(1),
      " monochromatic squares:", mono)
# 6x6 squares: 105  colours: 18 / 18  monochromatic squares: 0