Website founded by Milan Velimirović in 2006
2:33 UTC
 
MatPlus.Net Forum Promenade How many solutions? 



You can only view this page!
  (1) Posted by Andrew Buchanan [Tuesday, May 31, 2022 08:52]  How many solutions? My waking thought today was this:
(= 4+1 ) serh#n
For a given n, how many solutions (including shorter solutions)?   (2) Posted by Hauke Reddmann [Tuesday, May 31, 2022 08:57]  That should be a trivial exercise in binomial coefficients
(if one is a mathematician, that is :)  apply Pascal's
triangle where Black variants fork.   (3) Posted by Andrew Buchanan [Tuesday, May 31, 2022 09:28]  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.   (4) Posted by Georgy Evseev [Tuesday, May 31, 2022 10:27]  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...   (5) Posted by Andrew Buchanan [Tuesday, May 31, 2022 10:57]  1,2,3,5...?   (6) Posted by shankar ram [Tuesday, May 31, 2022 13:58]  Seems to be a fibonacci sequence starting with 1,2?   (7) Posted by Andrew Buchanan [Tuesday, May 31, 2022 15:09]  Hi Shankar,
Yes looks like it! Why would that sequence emerge here? :)
Cheers,
Andrew   (8) Posted by shankar ram [Tuesday, May 31, 2022 15:27]  Hanc marginis exiguitas non caperet.;)   (9) Posted by Andrew Buchanan [Tuesday, May 31, 2022 15:32]  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(n1) + f(n2). Then:
sum(k=1...n1)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 serh#n in EXACTLY n moves is f(n1), 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(n1).]
To find all the solutions in UP TO n moves, we need to sum them together:
sum(k=1...n1)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 serh#n is just f(n+1). A beautiful case of chess mathematics!   (10) Posted by shankar ram [Wednesday, Jun 1, 2022 08:52]  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?   (11) Posted by Olaf Jenkner [Wednesday, Jun 1, 2022 09:26]  An older setting of the Fibonacci sequence:
https://pdb.dieschwalbe.de/P1243505   (12) Posted by James Malcom [Wednesday, Jun 1, 2022 19:16]  It should no surprise that Elkies did it first.   (13) Posted by Joost de Heer [Wednesday, Jun 1, 2022 19:25]  Since I posted the Elkies composition recently on Facebook, perhaps Andrew was inspired by it?   (14) Posted by shankar ram [Wednesday, Jun 1, 2022 19:50]  Andrew himself had uploaded it to PDB back in 2012.   (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 4chain (see also P1243525). My own problem above also uses a 4chain 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 twosided 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 5cycle 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 nchain, consider a (2n+2)cycle:
xxxxxx =>
xxxxxx
...............
x..............x
...............
xxxxxx
ncycles are more symmetric than nchains, 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 longterm growth rate in the number of paths is dominated by the eigenvalues with largest magnitude. It turns out that the eigenvalues of nchain & (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 nchain. 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 nchain paths: they either have odd or even length.
So the growth rate of an nchain 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:
1chain: 0 (no movement can happen)
2chain: 1 (just deterministic pendulum)
3chain: _/2 ~= 1.4142
4chain: golden ratio = (1+_/5)/2 ~= 1.618
5chain: _/3 ~= 1.7321
6chain: ~= 1.8019
7chain: ~= 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 nchain is a subgraph of the ncycle (just missing 1 edge), and the ncycle 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_(n1)  p_(n2)
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 headtohead 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!   No more posts 
MatPlus.Net Forum Promenade How many solutions? 


