Skip to content
Get started

Losing positions in Wythoff's game

Two piles of counters. On a turn a player removes any positive number of counters from one pile, or the same positive number from both piles. The player who takes the last counter wins. How many positions (a,b)(a, b) with 1≤a≤b≤1001 \le a \le b \le 100 are losing for the player about to move?

Show hints (3)+
  1. List the losing positions for small piles. What pattern do the differences b−ab - a follow?
  2. Each positive integer appears in exactly one losing pair. Think of ⌊kφ⌋\lfloor k\varphi \rfloor.
  3. Count the kk with ⌊kφ2⌋≤100\lfloor k\varphi^2 \rfloor \le 100.

Answer

Reveal answer →

38

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Prop Trading

Related questions