KG

Skilled in Python, number theory, code golf, and messing about with calculators.

less than 1 minute read

Autumn and Yvonne love to play “falling leaves” this time of year. They play on a tree containing some number of leaves (possibly none) on its left and right sides. Starting with Autumn, each player takes turn choosing a leaf. All leaves at or below the chosen leaf on the same side of the tree fall to the ground. The game ends once the tree is out of leaves; whoever is the last to choose a leaf is the winner.

A sample game with 2 leaves on the left and 3 on the right, with Autumn’s choices in red and Yvonne’s in yellow, is shown below. In this game, Yvonne is the winner.

  1. Solve this game. That is, for each $L$, $R \geq 0$, determine if, on a tree with $L$ leaves on the left and $R$ on the right, a win is forced for Autumn or Yvonne, and if so, outline a strategy for the winner to respond to any move from their opponent.

  2. Read about https://en.wikipedia.org/wiki/Nim, either because you want to know more about combinatorial game theory, or you need a hint.

You May Also Enjoy

Teensy Problems: Sum of Factorials

1 minute read

Let $\mathrm{sf}(n)$ be the sum-of-factorials function: $0! + 1! + … n!$. Its first few values are $1$, $2$, $4$, $10$, $34$, ….

Teensy Problems: Coprime Labeling

1 minute read

Let $G$ be a graph with $n$ vertices. We say a graph is coprimely labeled if its vertices are labeled using all the integers from 1 to $n$ in such a way wher...

Teensy Problems: Marvin Numbers

less than 1 minute read

Marvin is interested in numbers whose sum of their digits equals the product of their digits. Call a nonnegative integer a $b$-Marvin number if it has this p...

Teensy Problems: Counting Carol

less than 1 minute read

Carol really likes counting, but can only keep track of so many numbers at once. She’s devised a family of sequences that matches these aptitudes, in the fol...