Hacker News new | ask | show | jobs
by IngoBlechschmid 1622 days ago
Another is Conway's Soliders:

A variant of peg solitaire, it takes place on an infinite checkerboard. The board is divided by a horizontal line that extends indefinitely. Above the line are empty cells and below the line are an arbitrary number of game pieces, or "soldiers". As in peg solitaire, a move consists of one soldier jumping over an adjacent soldier into an empty cell, vertically or horizontally (but not diagonally), and removing the soldier which was jumped over. The goal of the puzzle is to place a soldier as far above the horizontal line as possible. (https://en.wikipedia.org/wiki/Conway%27s_Soldiers)

How many soldiers have to be put below the line before the game starts to enable at least one soldier to reach a given height over the line?

For height 1, you need 2 soldiers.

For height 2, you need 4.

For height 3, you need 8.

For height 4, you need ... 20.

For height 5, it's impossible, by the golden ratio.

2 comments

> For height 5, it's impossible, by the golden ratio.

Strictly speaking, it's Conway's proof uses the golden ratio. But it could be that there's an alternate proof that doesn't use the golden ratio.

Yes, you are right! In fact, to people working in foundations of mathematics it is routine to compile away any explicit use of the golden ratio in Conway's proof and thus obtain a proof which only refers to the integers. However the resulting proof will be less perspicuous. I don't know of any transparent proof avoiding the golden ratio, though it definitely could exist.
In one of Numberphile's more in-depth videos (41 minutes), they have a full video proof of this, including the derivation of where the golden ratio comes from: https://www.youtube.com/watch?v=Or0uWM9bT5w&t=10s