Category Archives: computation

Computing optimal play for the greedy coins game, part 4

Last time I explained a method for computing best play for instances of the greedy coins game, which is feasible even for large games. This general approach is known as dynamic programming and is applicable whenever we have some recursively … Continue reading

Posted in computation, games, recursion | Tagged , , , , , , , , , , , | Leave a comment

Computing optimal play for the greedy coins game, part 3

In a previous post we saw how we can organize play sequences in the greedy coins game into a tree. Then in the last post, we saw how to work our way from the bottom of the tree upward and … Continue reading

Posted in computation, games, recursion | Tagged , , , , , , , , , | 2 Comments

Computing optimal play for the greedy coins game, part 2

I want to explain in more detail how we can think about computing the best possible score for Alice in the greedy coins game, assuming best play on the part of both players. I glossed over this too quickly in … Continue reading

Posted in computation, games, recursion | Tagged , , , , , , , , , | 1 Comment

Computing optimal play for the greedy coins game

Recall the greedy coins game, in which two players alternate removing one of the coins from either end of a row, and the player with the highest total at the end is the winner. What if we wanted to play … Continue reading

Posted in computation, games, recursion | Tagged , , , , , , , , , | 2 Comments

Golden numbers are Fibonacci

This post is fourth in a series, proving the curious fact that is a Fibonacci number if and only if one (or both) of or is a perfect square; we call numbers of this form golden numbers. Last time, I … Continue reading

Posted in arithmetic, computation, famous numbers, fibonacci, proof | Tagged , , , , , | 2 Comments

Fibonacci numbers are golden

Recall that a “golden number” (this is not standard terminology) is a number such that one (or both) of or is a perfect square. In this post, I’ll explain Gessel’s proof that every Fibonacci number is golden. First, we need … Continue reading

Posted in arithmetic, computation, famous numbers, fibonacci, proof | Tagged , , , , , | 1 Comment

Testing Fibonacci numbers: the proofs

In my last post I stated this surprising theorem: is a Fibonacci number if and only if one of is a perfect square. If one of is a perfect square, then let’s say that is a “golden number” (a nod, … Continue reading

Posted in arithmetic, computation, famous numbers, fibonacci, proof | Tagged , , , | 1 Comment