| |
Main
Date: 24 Jul 2006 01:56:05
From:
Subject: Problem (combinatorial, with a chess flavor)
|
Set a lonely white pawn anywhere in the 2ns row.
Position any number of black pieces on the chess
board. Now compute all possible ways the white
pawn can reach the 8th row by going forward
one square onto an unoccupied square, or
two squares forward initially (if theese two
squares are unoccupied), or by capturing a black
piece sideways, the way the pawns are fond
of doing so.
What is the maximal number of ways
for the white pawn to reach the 8th row?
For all practical purposes, this amounts
to finding a board configuration which
allows the maximal number pf paths.
For instance:
the configuration consisting of the white pawn
only allows for 2 ways to reach the 8th rank;
the configuration consisting of white pawn on e2,
and black pieces on d3 and f3 allows for 4 ways;
etc.
***
The problem admits more than one interpretation
Don't worry about it too much. Anyway, let's allow
for any number (legal or not, possibly > 16) of black
pieces (and it doesn't matter what they are; forget
about the black king or put it on a1).
Good luck,
Wlod
|
|
| |
Date: 25 Jul 2006 00:39:59
From: Bjoern
Subject: Re: Problem (combinatorial, with a chess flavor)
|
[email protected] wrote:
> Set a lonely white pawn anywhere in the 2ns row.
>
> Position any number of black pieces on the chess
> board. Now compute all possible ways the white
> pawn can reach the 8th row by going forward
> one square onto an unoccupied square, or
> two squares forward initially (if theese two
> squares are unoccupied), or by capturing a black
> piece sideways, the way the pawns are fond
> of doing so.
>
> What is the maximal number of ways
> for the white pawn to reach the 8th row?
> For all practical purposes, this amounts
> to finding a board configuration which
> allows the maximal number pf paths.
>
Actually, are we just talked about legal positions (that we are to make
only legal moves is presumably a given) ? "Any number of black pieces"
seems to imply that it can be more than 15 capturable black pieces on
the board...
If that's okay, then I believe a solution may be:
white pawn on e2 (or equivalently on d2)
black pieces on:
d3, f3, c4 to g4, b5 to h5, a6 to h6, a7 to h7 and a8 to h8.
Number of paths:
((3*2*2*2-1)*2-2)*2-2 = 86
* 3 moves to the third rank
* 2 moves from each of the reached positions on the third rank
* 2 moves from each of the reached positions on the fourth rank
* 2 moves from each of the reached positions on the fifth rank (except
for h5, which only allows 1 move)
* 2 moves from each of the reached positions on the sixth rank (except
for h6 and a6, which only allows 1 move each)
* 2 moves from each of the reached positions on the seventh rank (except
for h6 and a6, which only allows 1 move each)
Of course this solution requires 23 capturable (i.e. not counting a
king) black pieces more than there are so it only works if we do not
require a legal starting position
> For instance:
>
> the configuration consisting of the white pawn
> only allows for 2 ways to reach the 8th rank;
>
> the configuration consisting of white pawn on e2,
> and black pieces on d3 and f3 allows for 4 ways;
>
Potentially 4*4, depending on how you count a promotion (i.e. does that
make it a different path? I suppose not..).
|
| |
Date: 24 Jul 2006 15:17:58
From:
Subject: Re: Problem (combinatorial, with a chess flavor)
|
tin Brown wrote:
> [email protected] wrote:
> > Set a lonely white pawn anywhere in the 2ns row.
> >
> > Position any number of black pieces on the chess
> > board. Now compute all possible ways the white
> > pawn can reach the 8th row
Thus the number of ways (NOW) depends on the
initial board configuration. The point is to obtain the
maximal NOW over all configurations.
> Seems an amusing little puzzle. A quick and dirty
> solution would be to put the white pawn on d2
A heuristic argument suggests that this (and e2)
is an optimal initial position for the white pawn.
It minimizes the number of squares not reachable
by the white pawns. These are the squares under
the bishop diagonals (45 degrees) which pass
through the square of the white pawn. BTW, it
does not matter what we do with those squares
(setting or not black pieces on them makes no
difference).
> and then place black pieces everywhere but on
> the d-file. It is clear then that putting an extra black
> piece on d8 one path,
Actually 2 paths, since I have allowed for the initial
pawn jump (d2-d4). The problem would me more
elegant without this chessical provision but...
this are chess groups :-)
> is lost but two new captures are possible.
And behind each capture there are a lot of paths
which lead to them. Adding a piece on d8 has
a distinct advantage. You are right.
> This tends to suggest that thinning out carefully
> may give highest mobility.
I am not sure what you mean by the last sentence.
In any case, you solution feels quite close to
optimal but not optimal. Along your own line of thinking,
adding a piece on d7 will further increase NOW.
Compared to your ultimate solution, only 4 paths
are lost, while a huge (:-) number is gained.
Most likely, in the spirit of your solution, we should
cover all squares by black pieces but d2 (occupied
by the white pawn) and d3. And it does not change
anything if we remove the black piece from d4 too
-- the number of ways to reach it would be 2 in either
case.
If you think about a huge board then it is clear
that leaving the column d free (or mostly free)
of black pieces leaves the board divided into
the lrft and right parts, with no (or almost no)
communication between them. True, you have
a diminishing progression of 1-side paths
which deviate from the starting (empty) column
at later and later squares, but it doesn't make up
for the exponential waste due to the lack of
crossovers between the two halves.
> My tentative back of the envelope at lunchtime
> solution is therefore:
>
> pppppppp/ppp1pppp/ppp1pppp/ppp1ppp1/1pp1pp2/2p1p3/3P4/8
>
> It is quite likely there are better ones.
I would put white pawn on d2 (or e2). Let's assume it.
Then I'd say that having black pieces everywhere
except for the two squares d2 d3. (To have a piece
on d3 would be an obvious nonsense!). Removing black
piece from d4 leads to the same NOW. Then removing
black pieces from c4 and/or e4 still gives the same NOW.
More configurations with the same NOW can be created
this way. Possibly they are optimal, it's vey likely.
Regards,
Wlod
|
| |
Date:
From: Martin Brown
Subject: Re: Problem (combinatorial, with a chess flavor)
|
|
|
