﻿﻿ MatPlus.Net Website founded by
Milan Velimirović
in 2006

16:36 UTC ISC 2022

Remember me

 CHESS SOLVINGTournamentsRating lists1-Apr-2022 B P C F  MatPlus.Net Forum Promenade How many solutions?

### How many solutions? (= 4+1 )
ser-h#n

For a given n, how many solutions (including shorter solutions)?

That should be a trivial exercise in binomial coefficients
(if one is a mathematician, that is :-) - apply Pascal's
triangle where Black variants fork. Hi Hauke, thanks for your guess. It's intended to be simple yet surprising, but I'd say it's closer to Conway's Soldiers than Pascal's thing.  If I am not missing something obvious, there is exactly one solution in 1, 2, or 3. Then every next move adds two more solutions. So, as the stipulation was formulated, there is a sequence of: 1,2,3,5,7,9,11,... etc.

Sorry, incorrect...  1,2,3,5...?  Seems to be a fibonacci sequence starting with 1,2?  Hi Shankar,
Yes looks like it! Why would that sequence emerge here? :)
Cheers,
Andrew  Hanc marginis exiguitas non caperet.;-)  Non est ad astra mollis e terris via! :-)

Let's look at something apparently irrelevant: Peg Solitaire (aka Conway's Soldiers). https://en.wikipedia.org/wiki/Peg_solitaire

In this, a peg hops 2 squares orthogonally, capturing the mandatory hurdle. (Is there a fairy chess piece with this movement?) Imagine a long line of them. e.g.

.1234567890abcde.

(We put a space at each end to show the termination.) Split them conceptually into two alternating lines:

.1.3.5.7.9.a.c.e.
&
..2.4.6.8.0.b.d..

No captures can be made, but if we "borrow" one additional peg on the left of each line:

*1.3.5.7.9.a.c.e.
&
.*2.4.6.8.0.b.d..

then these two pegs can hop over all the other pegs in their lines:

................f
&
...............e.

Then combining them again, e can capture f:

.................g

Fibonacci numbers behave exactly the same way when you add them! There is a capturing rule: f(n) = f(n-1) + f(n-2). Then:

sum(k=1...n-1)f(k) = f(n+1) - f(0) - f(1)

The two correction terms correspond to the "*" terms that we added on the left in order to get the cascade started!

So back to chess. Ignoring for now the odd solution with n=1, the number of ser-h#n in EXACTLY n moves is f(n-1), where f(k) is the kth fibonacci number 1,1,2,3,5,8,13,21,34...

[This comes from bK being able to occupy just 4 squares.
A(n) is the number of ways to reach d8 or e8 in n moves, B(n) is the number of ways to reach c8 or f8.
A(n+1) = A(n)+B(n)
B(n+1) = A(n)
You can see that this formula is just the "capturing rule" again.
And to get started: A(1)=0,B(1)=1.
So A(n)=B(n+1)=f(n-1).]

To find all the solutions in UP TO n moves, we need to sum them together:

sum(k=1...n-1)f(k) = f(n+1) - f(0) - f(1)

f(0)+f(1) is just 0+1=1. So this is why we need the extra solution with bKh8.

"Summing it all up", the number of ser-h#n is just f(n+1). A beautiful case of chess mathematics!  Beautiful indeed! And the first Fibonacci sequence that I can remember seeing in a chess problem setting. Well done, Andrew!

Can it be extended? What happens if the BK has more than the 4 free squares?  An older setting of the Fibonacci sequence:
https://pdb.dieschwalbe.de/P1243505  It should no surprise that Elkies did it first.  Since I posted the Elkies composition recently on Facebook, perhaps Andrew was inspired by it?   (15) Posted by Andrew Buchanan [Wednesday, Jun 1, 2022 20:32]

Thanks folks,

Noam's earlier setting https://pdb.dieschwalbe.de/P1243505 is the first afaik to show the whole Fibonacci sequence, and is one of two he published with the 4-chain (see also P1243525). My own problem above also uses a 4-chain as the easiest way to get Fib going, but (1) concentrates the mates onto just 2 of the 4 squares in the chain, (2) tots up the cumulative sum from 1 to n, and (3) exploits the curious diversion to h8. And is seriesmover, as there's not much interest in the two-sided play.

The earlier https://pdb.dieschwalbe.de/P1259074 was the first I think to show a Fibonacci number. There is a clockwise rotation of 3 pieces within a 5-cycle of squares comprising h5, h4, h3, f3 & f5. There are two cyclic patterns: a = XXX00 & b = XX0X0. Only an X which has an 0 to the right of it can move. Thus in a, there is only one X that can move, so it becomes XX0X0 = b. On the other hand, in b, there are two X that might move, resulting in X0XX0 & XX00X, which cyclically are just b & a. So we get the (a,b)->(a+b,a) transformation characteristic of Fibonacci. The clockwise rotation is driven by the requirement to shift bPh5 to h3. Pawns can't go in circles, hence using this matrix we cannot see Fibonacci numbers beyond 34. But it's sweet how Fibonacci emerges. C+ under Jacobi.

Shankar Ram asks: what happens if the BK has more than the 4 free squares? There is a sneaky trick to get the answer quickly: instead of an n-chain, consider a (2n+2)-cycle:

x-x-x-x-x-x =>

x-x-x-x-x-x
|...............|
x..............x
|...............|
x-x-x-x-x-x

n-cycles are more symmetric than n-chains, so easier to analyze.

Counting paths in a graph systematically involves finding the "resonances", termed eigenvalues, which for a graph are always real numbers. The long-term growth rate in the number of paths is dominated by the eigenvalues with largest magnitude. It turns out that the eigenvalues of n-chain & (2n+2)-cycle are mostly the same! The dominant eigenvalues of the (2n+2)-cycle are +-1, but those are the only ones which *don't* carry over to the n-chain. The other eigenvalues are 2*cos(j*pi/(n+1)) for j=1..n, and they *do* carry over. The largest are where j=1 or n, and have opposite sign. We can ignore the sign from the perspective of the overall growth rate, but it's this sign that gives the "parity" in the n-chain paths: they either have odd or even length.

So the growth rate of an n-chain is 2*cos(pi/(n+1)). This "explains" why the golden ratio (which contains _/5) is the growth rate when n=4, which doesn't seem to have anything to do with 5.

Here's a few values of growth rates from n=1 upwards:
1-chain: 0 (no movement can happen)
2-chain: 1 (just deterministic pendulum)
3-chain: _/2 ~= 1.4142
4-chain: golden ratio = (1+_/5)/2 ~= 1.618
5-chain: _/3 ~= 1.7321
6-chain: ~= 1.8019
7-chain: ~= 1.8477
etc.

Some other random observations. As n increases, so does the growth rate, but it will always be less than 2 because the n-chain is a subgraph of the n-cycle (just missing 1 edge), and the n-cycle always has a growth rate of 2. The growth rate increases with n, because the missing edge is increasingly negligible. There is also a recursive formula for the polynomial of degree n, p_n(t) which contain the eigenvalues as roots:

p_n = - t*p_(n-1) - p_(n-2)

which is reminiscent of both Fibonacci & Pascal, although is more general.

Having posted, I saw others have briefly replied. So just as briefly:

(1) The composition was posted in Discord in response to someone requesting a problem with f(n) solutions. Maybe that Japanese requester had seen Joost's post - I had not.
(2) I could of course not compete in any head-to-head math contest with Noam, who is literally one of the most celebrated mathematicians of the modern age! Nevertheless I hope that I have my occasional moments :)

Thanks all! MatPlus.Net Forum Promenade How many solutions?