riddle of the day

Some processes look as though they could go on forever: you fix one thing, disturb others, and the game starts again. But sometimes there is a hidden measure that always decreases, even when it is not visible at first.

The Coins That Cannot Play Forever

Strategist
Pure logic

Riddle statement

Several coins are arranged in a row. Each coin shows either heads or tails.

A move consists of choosing a coin that is showing tails, turning it to heads, and also flipping the state of every coin to its left: heads become tails, and tails become heads.

Can there be an infinite sequence of moves?

Show solution

Solution

There cannot be an infinite sequence.

The idea is to assign a value to each configuration.

Number the coins from left to right and assign their positions the values:

$ 1,\ 2,\ 4,\ 8,\ 16,\dots $

That is, the leftmost coin is worth 1, the next is worth 2, the next is worth 4, and so on.

Now interpret:

heads = 0; tails = 1.

In this way, each row of coins represents a number.

When you choose a coin showing tails, that coin changes from 1 to 0. Suppose its value is $2^k$.

The coins to its left have smaller values:

$ 1,\ 2,\ 4,\dots,2^{k-1} $

By flipping all those coins, the number can increase by at most:

$ 1+2+4+\cdots+2^{k-1}=2^k-1 $

But the chosen coin decreases the number by:

$ 2^k $

So the total number decreases by at least 1.

Each move decreases a non-negative integer. Therefore, the process cannot continue forever.

Answer: no. Every sequence of moves must eventually end.