Education Zone
Fibonacci Nim
With SUMM's Golden Evening around the corner on 5/8, we're thinking about the Fibonacci numbers:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
It's a fun sequence to explore because it's so rich in patterns. While these numbers are generated in a simple way (by adding two consecutive terms to get the next), some of their patterns can be surprisingly complex.
One of my favorite things about the Fibonacci numbers is that they form a divisibility sequence. Take a pair of numbers with one dividing the other, like 7 and 28. The 7th and 28th Fibonacci numbers are 13 and 317811, and what do you know? 13 divides 317811. It turns out that this is no coincidence -- if M divides N, the Mth Fibonacci number divides the Nth Fibonacci number!
As long as we're playing with the Fibonacci numbers, let's literally play with them in a game called Fibonacci Nim. I'll explain the "Fibonacci" part in a bit, but you might like to try the game first, unspoiled. You'll need a friend to play against.
How to Play Fibonacci Nim
Start with a pile of 20 stones (or other tokens). The first player may remove any number of stones from 1-19. Players alternate removing stones but can only take up to twice as many as the other player did on the previous turn. (If the first player starts by taking 6 stones, for example, the second player can then take any number up to 12.) The player to take the last stone wins.
So... where's the Fibonacci in Fibonacci Nim? The game's analysis relies on an interesting property of Fibonacci numbers: every positive integer can be written uniquely as a sum of distinct, nonconsecutive Fibonacci numbers. (For example, 20 = 13 + 5 + 2.) This way of writing a number is called its Zeckendorf representation.
A winning strategy can be built around finding the Zeckendorf representation for the number of stones and then removing its smallest number. Starting with 20 = 13 + 5 + 2 stones, the first player would take 2 stones.
The second player can't respond by taking 5 stones, since 5 is more than twice 2. After their move, however, the remaining number of stones will have a smallest number in its Zeckendorf representation that the first player can take. The first player can win with this strategy as long as the starting stone count is not a Fibonacci number -- otherwise, the second player can win with it.
Wild to see the Fibonacci numbers crop up in a game that ostensibly has nothing to do with them, right? That's the beauty of math! Seemingly unrelated things can sometimes be linked, allowing ideas from one area of math to become the language we use to solve problems in another.
What's your favorite fact about Fibonacci numbers?