Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to 87investor,longview,Sussexlad,niord,staffordian, for Donating to support the site

Into unpopulated areas...

Gengulphus
Lemon Quarter
Posts: 3362
Joined: November 4th, 2016, 1:17 am
Been thanked: 1837 times

Into unpopulated areas...

#332703

Postby Gengulphus » August 12th, 2020, 3:34 pm

Consider a chess-style board of squares, with a boundary to the north, but extending as far as desired to the south, east and west:

. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Each square can have at most one piece on it, represented by a letter - I'm using different letters so that I can say which piece I'm talking about, there is otherwise no difference between pieces with different letters. A piece may move by jumping over an horizontally or vertically (but not diagonally) adjacent piece, removing it from the board.

A very trivial question is how many pieces I need on the board to be able to get one on the top row - the answer is obviously just one piece starting on the top row. But suppose I am restricted to not having any pieces on the top row to start with - how many pieces do I then need to be able to get one on the top row? That's almost as trivial - two pieces will do, one on the second row and one immediately below it on the third row:

. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | A | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | B | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Piece B jumps over piece A to land on the top row, removing piece A in the process.

OK, make it harder by not allowing any pieces on the top two rows to start with - how many pieces do I then need on the board to start with? It's fairly easy to eliminate the possibilities of doing it with one, two or three pieces, but four is doable:

. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | A | B | C | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | D | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Piece D jumps over piece A and removes it from the board, then piece C jumps over pieces B and D to land on the top row.

In increasing order of difficulty:

* What's the smallest number of starting pieces I need on the board to get one to the top row if they're not allowed to start on the top, second or third rows?

* What's the smallest number of starting pieces I need on the board to get one to the top row if they're not allowed to start on the top, second, third or fourth rows?

* What's the smallest number of starting pieces I need on the board to get one to the top row if they're not allowed to start on the top, second, third, fourth or fifth rows?

Not my original puzzle, by the way - but I'll acknowledge my source after people have had a go at solving it.

Gengulphus

UncleEbenezer
Lemon Half
Posts: 5180
Joined: November 4th, 2016, 8:17 pm
Has thanked: 658 times
Been thanked: 1034 times

Re: Into unpopulated areas...

#332739

Postby UncleEbenezer » August 12th, 2020, 6:01 pm

Gengulphus wrote:In increasing order of difficulty:

Did you mean to ask the general question for [n] socially-distanced rows? No, I haven't solved it! Nor am I going to try drawing any board or position.

My first thought is to work backwards inductively. The final move must be the jump to the top row; the penultimate move sets up that move by placing two pieces atop each other in the next two rows. Your third case demonstrates two moves to get to there.


* What's the smallest number of starting pieces I need on the board to get one to the top row if they're not allowed to start on the top, second or third rows?


In this case, we can set up the previous 4-piece position with one jump into each spot. A-C from behind; D from the left. Also fairly obvious you can't do it with fewer. This leads to speculating, is this an exponential solution? But the naïve approach doesn't (obviously) extend beyond three empty rows. Neither is it obvious that better-than-exponential solutions don't exist as the number of rows grows.


Not my original puzzle, by the way - but I'll acknowledge my source after people have had a go at solving it.
Gengulphus


Some visualisation tool might help with getting a grip on this one. Any suggestions?

Gengulphus
Lemon Quarter
Posts: 3362
Joined: November 4th, 2016, 1:17 am
Been thanked: 1837 times

Re: Into unpopulated areas...

#332747

Postby Gengulphus » August 12th, 2020, 6:36 pm

UncleEbenezer wrote:Did you mean to ask the general question for [n] socially-distanced rows?

No, and there's a good reason why I didn't...

With my change of spoiler-concealing colour, as UncleEbenezer's is a bit too readable against the pale yellow background of quotes:

UncleEbenezer wrote:
* What's the smallest number of starting pieces I need on the board to get one to the top row if they're not allowed to start on the top, second or third rows?

In this case, we can set up the previous 4-piece position with one jump into each spot. A-C from behind; D from the left. Also fairly obvious you can't do it with fewer. This leads to speculating, is this an exponential solution? But the naïve approach doesn't (obviously) extend beyond three empty rows. Neither is it obvious that better-than-exponential solutions don't exist as the number of rows grows.

Yes, that's the answer to my first question, give or take a more detailed explanation of "fairly obvious". And it's why the second question is harder than the first!

UncleEbenezer wrote:Some visualisation tool might help with getting a grip on this one. Any suggestions?

A Go set would be ideal, but a chess set might do at a pinch...

Gengulphus

modellingman
Lemon Slice
Posts: 292
Joined: November 4th, 2016, 3:46 pm
Has thanked: 50 times
Been thanked: 129 times

Re: Into unpopulated areas...

#333245

Postby modellingman » August 14th, 2020, 5:10 pm

Gengulphus wrote:Consider a chess-style board of squares, with a boundary to the north, but extending as far as desired to the south, east and west:

. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Each square can have at most one piece on it, represented by a letter - I'm using different letters so that I can say which piece I'm talking about, there is otherwise no difference between pieces with different letters. A piece may move by jumping over an horizontally or vertically (but not diagonally) adjacent piece, removing it from the board.

A very trivial question is how many pieces I need on the board to be able to get one on the top row - the answer is obviously just one piece starting on the top row. But suppose I am restricted to not having any pieces on the top row to start with - how many pieces do I then need to be able to get one on the top row? That's almost as trivial - two pieces will do, one on the second row and one immediately below it on the third row:

. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | A | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | B | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Piece B jumps over piece A to land on the top row, removing piece A in the process.

OK, make it harder by not allowing any pieces on the top two rows to start with - how many pieces do I then need on the board to start with? It's fairly easy to eliminate the possibilities of doing it with one, two or three pieces, but four is doable:

. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | A | B | C | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | D | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

Piece D jumps over piece A and removes it from the board, then piece C jumps over pieces B and D to land on the top row.

In increasing order of difficulty:

* What's the smallest number of starting pieces I need on the board to get one to the top row if they're not allowed to start on the top, second or third rows?

* What's the smallest number of starting pieces I need on the board to get one to the top row if they're not allowed to start on the top, second, third or fourth rows?

* What's the smallest number of starting pieces I need on the board to get one to the top row if they're not allowed to start on the top, second, third, fourth or fifth rows?

Not my original puzzle, by the way - but I'll acknowledge my source after people have had a go at solving it.

Gengulphus


Possible answers...



As UncleEbenezer has noted there is a solution to the first question which involves 8 pieces. This solution generates Gengulphus' 4 piece solution to the puzzle with the top 2 rows empty. For completeness, this solution which I will call the "3 row solution", is below.

. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | D | E | F | G | H | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | A | B | C | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .


Pieces A, B and C jump over pieces F, G and H respectively leaving D to jump over E to generate the previous 2 row solution.

So far the "n row" solutions (n=1,2,3) have involved 2,4 and 8 pieces respectively. It therefore seems reasonable to ask whether there is a 4 row solution that a) involves 16 pieces and b) generates the 3 row solution noted above.

If there is, I could not find it. The best I was able to come up with was a 20 piece solution but which did generate the 3 row solution above.

Following broadly the same approach used to derive the 3 row solution from the 2 row solution:
  • Pieces D, E, F, G, H in the 3 row solution should be generated from the 4 row solution by being placed in the 6th row and jumping over 5 pieces in the 5th row. Call the 5 removed pieces I, J, K, L and M. This positions 5 of the 8 pieces in the 3 row solution.
  • Piece C in the 3-row solution can be dealt with in the 4 row solution by placing it and another piece (N) to the right of piece M, allowing it to jump left into its desired position in the 5th row once M is removed. However, such sideways jumps are not possible for pieces A and B because of the original placement of pieces I and J in row 5. Neither are jumps from row 7 possible for A and B because of the original placement of pieces F and G in row 6 and their subsequent jump to row 4.
  • It is possible, however, to position pieces A and B into their correct positions in row 5 using pieces placed in rows 7 and 8. The approach uses the same L-shaped pattern as the 2 row solution of 4 pieces presented by Gengulphus. Two "L''s are required symmetrically arranged, one for piece A and one for piece B, and are denoted by the sets of pieces {A, O, P, Q} and {R, S, T, B}, respectively.
This 4 row solution looks like:

. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| I | J | K | L | M | N | C |
. . . . +---+---+---+---+---+---+---+ . . . .
| D | E | F | G | H | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| A | O | P | R | S | B | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | Q | T | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .


So my answer to the second question is 20 pieces.

I struggled with extending the approach to get a 5 row solution. The problem that defeated me was placing pieces F and G into the 4 row solution above. The 18 pieces I did place involved starting from 54 pieces on or below row 6.

I strongly suspect, but lack the skills to prove, that any 3 row rectangle fully occupied by pieces with more than 4 columns cannot be created from a shape whose pieces are all below the rectangle's top row. The 4 row solution above contains a rectangle with 3 rows and 5 columns (bounded by pieces I and S at top-left and bottom-right corners). If my suspicion is correct, it will be impossible to find a 5 row solution capable of creating this 4-row solution. That is not to say there is no 5 row solution, just that it if there is one, it will not pass through my 4 row solution.

Gengulphus wrote:
UncleEbenezer wrote:Did you mean to ask the general question for [n] socially-distanced rows?

No, and there's a good reason why I didn't...


I suspect that the good reason is that at some point, the solutions don't exist. My guess (and at this stage it is a guess) is that 4 empty rows is the limit.

There is a second solution to the 3 row problem that is worth a mention, it involves 10 pieces and is shown below.


. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | X | X | B | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | A | X | E | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | X | X | D | | |
. . . . +---+---+---+---+---+---+---+ . . . .
| | | C | | | | |
. . . . +---+---+---+---+---+---+---+ . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .


Pieces marked X are removed. Other pieces jump in order as follows A, B, B (A removed), C, D, D (C removed), E, E (D removed), E (B removed). Piece E ends up on the top row in the shape's leftmost column. One feature of this pattern is that if rotated 90 degrees clockwise, it can be used to move a piece 3 columns right of its top-right corner or two pieces 1 and 2 columns right of the same position. Although the 8 piece solution can also be similarly rotated, it has the disadvantage that it starts with pieces occupying the two rows above the piece(s) being moved.

It is possible to generate a 4 row solution from this second 3 row solution. The best I got was a 26 piece solution, though this had a similar problem to the one I noted above - namely a filled rectangle with 3 rows and more than 4 columns.

UncleEbenezer
Lemon Half
Posts: 5180
Joined: November 4th, 2016, 8:17 pm
Has thanked: 658 times
Been thanked: 1034 times

Re: Into unpopulated areas...

#334166

Postby UncleEbenezer » August 18th, 2020, 4:30 pm

Gengulphus wrote:
UncleEbenezer wrote:Did you mean to ask the general question for [n] socially-distanced rows?

No, and there's a good reason why I didn't...

Can't say I'm entirely surprised. Might there be a "show it's impossible" case lurking?

A Go set would be ideal, but a chess set might do at a pinch...

Gengulphus


Indeed. I might have something, but have yet to dig it up (as I write, I think I may know where to find an old backgammon set). But I was rather hoping for something ont' web, with extra goodies like backward and forward moves.

Hitherto I have neither motivated myself to solve it beyond the simple part I posted, nor spoiled it by reading Modellingman's answer whose rec suggests it's not merely longer than mine but also more complete! But I probably won't get a round tuit.

BTW, reading the start of your statement of the puzzle, I thought for a moment this was a close relative of phutball!

Gengulphus
Lemon Quarter
Posts: 3362
Joined: November 4th, 2016, 1:17 am
Been thanked: 1837 times

Re: Into unpopulated areas...

#336038

Postby Gengulphus » August 26th, 2020, 11:36 am

Well done to modellingman for finding a 20 piece solution to the 4-row problem. 20 is in fact the minimal number of pieces, and there are two 20-piece solutions, plus their left-to-right reflections.

I probably didn't make my comment about there being a good reason why I didn't mean to ask the general question for N rows cryptic enough, because both modellingman and UncleEbenezer correctly picked up on what it was hinting at: it's impossible to get a piece on to the top row if the top five rows are required to be empty to begin with, no matter how large a finite number of pieces one starts with in lower rows. I'll spoiler-protect the proof in case anyone wants to continue looking for it...

Suppose that from some starting position, it is possible to get a piece on to the square labelled "0" in the following diagram:

. . . . +---+---+---+---+---+---+---+---+---+---+---+---+---+ . . . .
| 6 | 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
. . . . +---+---+---+---+---+---+---+---+---+---+---+---+---+ . . . .
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
. . . . +---+---+---+---+---+---+---+---+---+---+---+---+---+ . . . .
| 8 | 7 | 6 | 5 | 4 | 3 | 2*| 3*| 4*| 5*| 6 | 7 | 8 |
. . . . +---+---+---+---+---+---+---+---+---+---+---+---+---+ . . . .
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 4 | 5*| 6*| 7 | 8 | 9 |
. . . . +---+---+---+---+---+---+---+---+---+---+---+---+---+ . . . .
| 10| 9 | 8 | 7 | 6 | 5 | 4 | 5 | 6 | 7 | 8 | 9 | 10|
. . . . +---+---+---+---+---+---+---+---+---+---+---+---+---+ . . . .
| 11| 10| 9 | 8 | 7 | 6 | 5 | 6 | 7 | 8 | 9 | 10| 11|
. . . . +---+---+---+---+---+---+---+---+---+---+---+---+---+ . . . .
| 12| 11| 10| 9 | 8 | 7 | 6 | 7 | 8 | 9 | 10| 11| 12|
. . . . +---+---+---+---+---+---+---+---+---+---+---+---+---+ . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .

in which each square is labelled with the minimum number of horizontal and vertical (but not diagonal) steps required to get from it to the square labelled "0", and the asterisks are to allow me to refer to a particular position below.

Give a piece in a square labelled n a score of t^n, where t = (sqrt(5)-1)/2 = 0.6180339887..., the reciprocal of the 'golden ratio'. Give any position a score equal to the sum of the scores of the pieces it contains - for example, the position with pieces on the six asterisked squares has score t^2 + t^3 + t^4 + 2t^5 + t^6.

An important property that the number t has is that t + t^2 = 1, and so by multiplying through by t, we also have t^2 + t^3 = t, t^3 + t^4 = t^2, etc. This often allows scores to be simplified - e.g. the score of that example position is t^2 + t^3 + t^4 + 2t^5 + t^6 = (t^2+t^3) + (t^4+t^5) + (t^5+t^6) = t + t^3 + t^4 = t + t^2 = 1.

It's easy to check that every possible move is a jump over a square labelled n for some n, starting on a square labelled either n-1 or n+1. If it starts on a square labelled n-1, it always ends on a square labelled n+1, while if it starts on a square labelled n+1, it ends either on a square labelled n-1 or a square labelled n+1. So we can work out what changes can possibly be made to a position's score by performing a move - the scores for the starting square and for the jumped square get subtracted and the score for the ending square gets added:

* If the jump starts on a square labelled n-1 and ends on a square labelled n+1, the change is -t^(n-1) - t^n + t^(n+1) = (-1-t+t^2) * t^(n-1) < 0 because -1-t+t^2 is negative and t^(n-1) is positive.

* If the jump starts on a square labelled n+1 and ends on a square labelled n+1, the change is -t^(n+1) - t^n + t^(n+1) = -t^n < 0 because t^n is positive.

* If the jump starts on a square labelled n+1 and ends on a square labelled n-1, the change is -t^(n+1) - t^n + t^(n-1) = (1-t-t^2) * t^(n-1) = 0 because 1-t-t^2 = 0.

So every move we make either reduces the position's score or leaves it unchanged. Since the score of the square labelled "0" is t^0 = 1, it's impossible to end up with a piece on that square from any starting position whose score is less than 1. (Note that the converse isn't true: if a starting position's score is greater than or equal to 1, it's not necessarily possible to end up with a piece on the square labelled "0". For example, while the position with pieces on the six asterisked squares has score 1, it's not too difficult to check that one cannot get a piece to "0" starting from it.)

Now look at total available scores:

For pieces on the square labelled "0" and all squares to its right on the top row, the total available score is s = 1 + t + t^2 + t^3 + t^4 + t^5 + ... Multiplying by 1-t, we get (1-t)*s = 1 - t + t - t^2 + t^2 - t^3 + t^3 - t^4 + t^4 - t^5 + ... = 1, since all positive terms except 1 cancel with the immediately preceding negative term. So s = 1/(1-t). But 1-t = t^2, so s = 1 / t^2 = t^(-2).

For pieces on squares to the left of the square labelled "0" on the top row, the total available score is t + t^2 + t^3 + t^4 + t^5 + ... = t*s = t^(-1). So for pieces on top row squares, the total available score is t^(-2) + t^(-1) = (t + t^2) * t^(-3) = t^(-3).

Each square on the second row scores t times the score of the top row square immediately above it, so the total available score for pieces on the second row is t * t^(-3) = t^(-2). Similarly, the total available score for pieces on the third row is t * t^(-2) = t^(-1), the total available score for pieces on the fourth row is t * t^(-1) = 1, the total available score for pieces on the fifth row is t * 1 = t, the total available score for pieces on the sixth row is t * t = t^2, etc.

So the total available score for pieces on the sixth row and below is t^2 + t^3 + t^4 + t^5 + t^6 + ... = t^2 * s = 1. So if the starting position has no pieces on the first five rows and pieces on every square on the sixth row and below, it would have score 1, but if it has no pieces on the first five rows and only a finite number of pieces on the sixth row and below, it has score less than 1, and so cannot possibly be moved to a position with a piece on the square labelled "0".

This also leads to proofs about how many pieces are needed for the four-row problem. In particular, if the starting position has no pieces in the first four rows, the score for a starting position with 19 pieces is at most t^4 for the single square labelled "4" that is available, plus 3t^5 for the three available squares labelled "5", 5t^6 for the five available squares labelled "6", 7t^7 for the seven available squares labelled "7" and 3t^8 for three of the nine available squares labelled "8". That sum is t^4 + 3t^5 + 5t^6 + 7t^7 + 3t^8 = t^4 + 3t^5 + 5t^6 + 4t^7 + 3(t^7 + t^8) = t^4 + 3t^5 + 8t^6 + 4t^7 = t^4 + 3t^5 + 4t^6 + 4(t^6 + t^7) = t^4 + 7t^5 + 4t^6 = t^4 + 3t^5 + 4(t^5 + t^6) = 5t^4 + 3t^5 = 2t^4 + 3(t^4 + t^5) = 3t^3 + 2t^4 = t^3 + 2(t^3 + t^4) = 2t^2 + t^3 = t^2 + (t^2 + t^3) = t + t^2 = 1.

So firstly, the 4-row problem cannot be solved with fewer than 19 pieces in the starting position, and secondly, any solution with 19 pieces in the starting position must have pieces on all of the asterisked squares and three of the question-marked squares in the following diagram ("0" as before indicating the square where a piece is to be finally delivered):

. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | | | | 0 | | | | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | | | | | | | | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | | | | | | | | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | | | | | | | | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | ? | * | * | * | * | * | * | * | ? | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | ? | * | * | * | * | * | ? | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | | ? | * | * | * | ? | | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | | | ? | * | ? | | | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | | | | ? | | | | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
| | | | | | | | | | | |
. . . . +---+---+---+---+---+---+---+---+---+---+---+ . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .

This is a useful first step in proving that it cannot be done with fewer than 20 pieces - it still leaves the number of conceivable 19-piece solutions fairly large, but much smaller than it would be without that restriction on where the pieces can be to start with. As it turns out, none of those conceivable 19-piece solutions actually works (not something I'm going to try to prove here!), and so 20 pieces is the minimal number for the 4-row problem.

Finally, I should attribute my source for this puzzle as promised: it is Elwyn R. Berlekamp's, John H. Conway's and Richard K. Guy's book "Winning Ways for your Mathematical Plays". A big and tremendously valuable source of information about mathematical games and puzzles, published in two volumes originally (in 1982) and then in a 4-volume second edition between 2001 and 2004. But unfortunately also a tremendously expensive book - the second edition will probably set you back about £40-£60 per volume...

Gengulphus

UncleEbenezer
Lemon Half
Posts: 5180
Joined: November 4th, 2016, 8:17 pm
Has thanked: 658 times
Been thanked: 1034 times

Re: Into unpopulated areas...

#336044

Postby UncleEbenezer » August 26th, 2020, 11:58 am

Gengulphus wrote:I probably didn't make my comment about there being a good reason why I didn't mean to ask the general question for N rows cryptic enough,


Just to pick up on that (and I expect I speak for other regulars here), I don't think a more cryptic comment would've made any difference. My question already had in mind the likelihood that solutions would not extend indefinitely without those restrictive rules.

Finally, I should attribute my source for this puzzle as promised: it is Elwyn R. Berlekamp's, John H. Conway's and Richard K. Guy's book "Winning Ways for your Mathematical Plays".

I first heard Conway in 1979, and already then he was self-promoting that ;)

Your own contributions in general here strike me as something a Conway-disciple might make. That is, someone who has kept up his maths, not let it all lapse into decrepitude like mine.

UncleEbenezer
Lemon Half
Posts: 5180
Joined: November 4th, 2016, 8:17 pm
Has thanked: 658 times
Been thanked: 1034 times

Re: Into unpopulated areas...

#336149

Postby UncleEbenezer » August 26th, 2020, 6:00 pm

OK, a followup problem for the serious.

As the number of blank rows grows, overcrowding rapidly becomes an issue. Iterating from the easy solutions upwards would be straightforward if squares could be re-used, placing more than one piece on a square, and removing exactly one piece when it is jumped.

So instead of a square grid, consider an n-dimensional grid. n=1 is easy, this thread deals with n=2. What about a cubic grid? Being able to approach from an orthogonal direction enables us to extend the iterative approach (and exponential solution) at least one row further.

Can you prove, or find a counterexample, to UncleE's conjecture. Namely, that for an N-dimensional grid, the exponential solution extends to N+1 blank rows?

UncleEbenezer
Lemon Half
Posts: 5180
Joined: November 4th, 2016, 8:17 pm
Has thanked: 658 times
Been thanked: 1034 times

Re: Into unpopulated areas...

#336252

Postby UncleEbenezer » August 27th, 2020, 8:26 am

UncleEbenezer wrote:Can you prove, or find a counterexample, to UncleE's conjecture. Namely, that for an N-dimensional grid, the exponential solution extends to N+1 blank rows?

Um, apart from the trivial counterexample that stares us in the face. :oops: Can you tell I indulged rather well in "eat out to help out" yesterday lunchtime?

Gengulphus
Lemon Quarter
Posts: 3362
Joined: November 4th, 2016, 1:17 am
Been thanked: 1837 times

Re: Into unpopulated areas...

#336276

Postby Gengulphus » August 27th, 2020, 9:58 am

UncleEbenezer wrote:OK, a followup problem for the serious.

As the number of blank rows grows, overcrowding rapidly becomes an issue. Iterating from the easy solutions upwards would be straightforward if squares could be re-used, placing more than one piece on a square, and removing exactly one piece when it is jumped.

So instead of a square grid, consider an n-dimensional grid. n=1 is easy, this thread deals with n=2. What about a cubic grid? Being able to approach from an orthogonal direction enables us to extend the iterative approach (and exponential solution) at least one row further.

Can you prove, or find a counterexample, to UncleE's conjecture. Namely, that for an N-dimensional grid, the exponential solution extends to N+1 blank rows?

I think some care needs taking about the question. I assume that one is working in an N-dimensional half-space: in 2 dimensions, that means everything in a 1-dimensional subspace (the 'top row') and to one side of it. That gives us a natural ordering on the rows parallel to the top row - there's the row 1 away from the top row, the row 2 away from the top row, etc, which we call the second row, the third row, etc. In 3 dimensions, it means everything in a 2-dimensional subspace (the 'top plane') and to one side of it, and we similarly have a natural ordering on the planes parallel to the top plane - but we don't have any natural ordering on 1-dimensional rows. So talking about the first N planes being blank makes sense, but not similar talk about the first N rows. In 4 dimensions, it means everything in a 3-dimensional subspace (the 'top hyperplane') and to one side of it, and we have a natural ordering on the hyperplanes parallel to the top hyperplane, but not on the rows or the planes. So talking about the first N hyperplanes being blank makes sense, but not similar talk about the first N rows or the first N planes. And so on...

So I think the 3-dimensional question should be: The board consists of a 3-dimensional grid of cubelets centred at positions (x,y,z), with x, y and z all integers and z <= 0. The cubelets centred at points (x,y,0) form the top plane, the cubelets centred at (x,y,-1) form the second plane, the cubelets centred at (x,y,-2) form the third plane, etc, and moves consist of jumping a piece in the cubelet centred at (x,y,z) over a piece in the cubelet centred at any of (x,y,z+1), (x,y,z-1), (x,y+1,z), (x,y-1,z), (x+1,y,z) or (x-1,y,z) into an empty cubelet centred at (x,y,z+2), (x,y,z-2), (x,y+2,z), (x,y-2,z), (x+2,y,z) or (x-2,y,z) respectively, removing the jumped piece from the board. What's the smallest finite number of pieces required in a starting position from which it is possible to end up with a piece in the top plane, if the first H planes are required to be empty in the starting position?

And there are analogous questions for an N-dimensional half-space board with the first H (N-1)-dimensional hyperplanes being required to be empty. My partial solution, spoiler-protected:

As in my previous argument for the 2-dimensional case, label the top-hyperplane (hyper)cubelet that we will get a piece into with "0" and every other cubelet with the minimum number of orthogonal (but not diagonal) steps required to get from it to the cubelet labelled "0", and give a piece in a cubelet labelled "n" a score of t^n, where t = (sqrt(5)-1)/2 = 0.6180339887... Give a position a score equal to the sum of the scores of its pieces, and as before, every move made from a position either decreases its score or leaves it unchanged. Since we're aiming to get to a position with a piece in the "0" cubelet, our final position must have a score of at least t^0 = 1, so it is impossible to achieve that aim from any starting position with a score less than 1.

As before, the total score available from a row containing the "0" cubelet is 1 + 2t + 2t^2 + 2t^3 + 2t^4 + ... = t^(-3). A plane containing the "0" cubelet consists of such a row, two rows parallel to and 1 away from it, two rows parallel to and 2 away from it, two planes parallel to and 3 away from it, etc. Since each cubelet in a row parallel to and i away from the row containing the "0" cubelet has an available score that is t^i times that of the corresponding cubelet in the row containing the "0" cubelet, the total available score from such a row is t^i times the total available score from the row containing the "0" cubelet, i.e. t^(-3) * t^i. So the total available score from a plane containing the "0" cubelet is:

t^(-3) * (1 + 2t + 2t^2 + 2t^3 + 2t^4 + ...) = t^(-3) * t^(-3) = t^(-6)

For the three-dimensional board, that tells me that the total available score from the top plane is t^(-6). That from the second plane is t times that, from the third plane t^2 times that, etc, so the total score available from the entire board is:

t^(-6) * (1 + t + t^2 + t^3 + t^4 + ...) = t^(-6) * t^(-2) = t^(-8)

If we forbid starting with pieces on the top H planes, the cubelets we are allowed to use are basically those of an entire board, but each only allowed a score that is t^H times as much. So the total available score for the starting position is t^(-8) * t^H = t^(H-8). So if H >= 8, the total available score for the starting position is <= 1, and furthermore it can only equal 1 if H=8 and every cubelet in the planes below the top 8 is occupied by a piece. So for H >= 8, every finite starting position has a score less than 1, and so cannot move to a position containing a piece in the "0" cubelet. So the problem is unsolvable for the 3-dimensional board if 8 or more top planes are to be avoided by the starting position.

For the 4-dimensional board, an analogous argument says that the total available score from the top hyperplane is t^(-6) * t^(-3) = t^(-9), that the total available score from the whole board is t^(-9) * t^(-2) = t^(-11), and that if H >= 11, every finite starting position that avoids the top 11 hyperplanes has a score less than 1, and so cannot move to a position containing the "0" cubelet. And more generally, that argument extends to say that the question "On an N-dimensional half-space board, what's the smallest finite number of pieces required in a starting position from which it is possible to end up with a piece in the top (N-1)-dimensional hyperplane, if the first H (N-1)-dimensional hyperplanes are required to be empty in the starting position?" has no answer if H >= 3N-1 because there is no such starting position.

That's a partial solution because it only says that the question has no answer if H >= 3N-1, not whether it has an answer when H <= 3N-2, let alone what the answer is when it does have one. I have a strong impression that it always will have an answer when H <= 3N-2 - strong enough that I would dignify it with the description "conjecture". And indeed, I have a rough idea about how I might go about proving that conjecture - though I've got to do some work on that idea before I'll know whether it does indeed work out.

What the answer is when it exists may well be a harder problem - showing that an answer exists only involves exhibiting a suitable starting position with some number S of pieces, but showing that the answer is S involves both doing that and showing that no position with < S pieces is a suitable starting position, which I suspect is a significantly harder thing to do!

Gengulphus

Gengulphus
Lemon Quarter
Posts: 3362
Joined: November 4th, 2016, 1:17 am
Been thanked: 1837 times

Re: Into unpopulated areas...

#336297

Postby Gengulphus » August 27th, 2020, 11:59 am

Gengulphus wrote:So I think the 3-dimensional question should be: The board consists of a 3-dimensional grid of cubelets centred at positions (x,y,z), with x, y and z all integers and z <= 0. The cubelets centred at points (x,y,0) form the top plane, the cubelets centred at (x,y,-1) form the second plane, the cubelets centred at (x,y,-2) form the third plane, etc, and moves consist of jumping a piece in the cubelet centred at (x,y,z) over a piece in the cubelet centred at any of (x,y,z+1), (x,y,z-1), (x,y+1,z), (x,y-1,z), (x+1,y,z) or (x-1,y,z) into an empty cubelet centred at (x,y,z+2), (x,y,z-2), (x,y+2,z), (x,y-2,z), (x+2,y,z) or (x-2,y,z) respectively, removing the jumped piece from the board. What's the smallest finite number of pieces required in a starting position from which it is possible to end up with a piece in the top plane, if the first H planes are required to be empty in the starting position?

Another partial solution, again spoiler-protected:

For that 3-dimensional question, there is a starting position from which it is possible to end up with a piece in the top plane, in which the first 5 planes are initially empty. More generally, for the N-dimensional question, there is a starting position in which it is possible to end up with a piece in the top (N-1)-dimensional hyperplane, in which the first 2N-1 (N-1)-dimensional hyperplanes are initially empty. The proof is simple:

For the 1-dimensional board, we have the very trivial solution in which the top square is empty:

+---+
| |
+---+
| A |
+---+
| B |
+---+
| |
+---+
. .
. .

and by extending it out into a second dimension, we can produce a 2-dimensional solution in which the top 3 rows are empty:

. . +---+---+---+---+---+ . .
| | | | | |
. . +---+---+---+---+---+ . .
| | | | | |
. . +---+---+---+---+---+ . .
| | | | | |
. . +---+---+---+---+---+ . .
| A1| A2| A3| B1| B2|
. . +---+---+---+---+---+ . .
| | | A4| B3| B4|
. . +---+---+---+---+---+ . .
| | | | | |
. . +---+---+---+---+---+ . .
. . . . . . . .
. . . . . . . .

in which the four pieces labelled "A1"-"A4" are moved with three jumps to produce the piece labelled "A" in the 1-dimensional solution and the four pieces labelled "B1"-"B4 are moved with three jumps to produce the piece labelled "B" in the 1-dimensional solution.

Now look at that 2-dimensional solution from its side, so that the second dimension goes 'into the page' rather than left-to-right, and it becomes a stack of five 1-dimensional positions, each with its top three cells empty:

+---+       +---+       +---+       +---+       +---+
| | | | | | | | | |
+---+ +---+ +---+ +---+ +---+
| | | | | | | | | |
+---+ +---+ +---+ +---+ +---+
| | | | | | | | | |
+---+ +---+ +---+ +---+ +---+
| A1| | A2| | A3| | B1| | B2|
+---+ +---+ +---+ +---+ +---+
| | | | | A4| | B3| | B4|
+---+ +---+ +---+ +---+ +---+
| | | | | | | | | |
+---+ +---+ +---+ +---+ +---+
. . . . . . . . . .
. . . . . . . . . .

But using exactly analogous moves, that position can be obtained from a stack of five 2-dimensional positions, each with its top five rows empty:

. . +---+---+---+---+---+ . .       . . +---+---+---+---+---+ . .       . . +---+---+---+---+---+ . .       . . +---+---+---+---+---+ . .       . . +---+---+---+---+---+ . .
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
. . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . .
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
. . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . .
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
. . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . .
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
. . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . .
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
. . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . .
| A1| A1| A1| | | | A2| A2| A2| | | | A3| A3| A3| A4| A4| | B1| B1| B1| B3| B3| | B2| B2| B2| B4| B4|
. . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . .
| | | A1| | | | | | A2| | | | | | A3| A4| A4| | | | B1| B3| B3| | | | B2| B4| B4|
. . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . .
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
. . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . . . . +---+---+---+---+---+ . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

now with each piece in the turned-on-its-side 2-dimensional solution derived by making three jumps with the four similarly-labelled pieces in this stack of 2-dimensional positions. But this stack of 2-dimensional positions is a 3-dimensional position with its top 5 planes empty, which is the thing I wanted to prove exists.

This construction works because every vertical column through the 8-piece solution for 2 dimensions with 3 empty rows has no more than 2 adjacent pieces in it - no more than the 2-piece solution for 1 dimension with one empty cell. It produces a 32-piece solution for 3 dimensions with 5 empty planes, that again has no more than 2 adjacent pieces in any vertical column. So a similar construction extending into a 4th dimension will produce a 128-piece solution for 4 dimensions with the top 7 hyperplanes empty, still with no more than 2 adjacent pieces in any vertical column, and doing it again to extend into a 5th dimension will produce a 512-piece solution for 5 dimensions with the top 9 4-dimensional hyperplanes empty, and so on.

I can similarly use the 20-piece 2-dimensional solution with 4 empty rows to extend the 8-piece solution for 2 dimensions with 3 empty rows to an 80-piece solution for 3 dimensions with 6 empty rows - but that extension has up to four adjacent pieces in each vertical column, so the same technique cannot be used to extend it further to a solution for 4 dimensions. But I can use the 20-piece 2-dimensional solution with 4 empty rows to extend any of the solutions in the last paragraph - such an extension can follow any number of extensions using the 8-piece solution for 2 dimensions with 3 empty rows, it just cannot be followed by any more such extensions.

Putting these last two posts together, I've shown that the 3-dimensional problem:

* with 5 empty planes has a solution with 32 pieces (which doesn't rule out the possibility that it has a solution with fewer pieces);
* with 6 empty planes has a solution with 80 pieces (which again doesn't rule out the possibility that it has a solution with fewer pieces);
* with 7 empty planes might or might have a solution with a finite number of pieces (I would conjecture that it does);
* with 8 or more empty planes does not have a solution with a finite number of pieces.

For the 4-dimensional problem, the corresponding numbers are 128 pieces for 7 empty hyperplanes and 320 pieces for 8 empty hyperplanes; it's unknown whether it's possible (but I conjecture that it is) for 9 or 10 empty hyperplanes; and it's impossible for 11 or more empty hyperplanes. And for the N-dimensional problem, 2^(2N-1) pieces will do the job for 2N-1 empty (N-1)-dimensional hyperplanes; 5*2^(2N-2) pieces will do the job for "N such empty hyperplanes; I don't know whether it's possible (but conjecture that it is) for 2N+1 up to and including 3N-2 such empty hyperplanes; and it's impossible for 3N-1 or more such empty hyperplanes.

Gengulphus

UncleEbenezer
Lemon Half
Posts: 5180
Joined: November 4th, 2016, 8:17 pm
Has thanked: 658 times
Been thanked: 1034 times

Re: Into unpopulated areas...

#336304

Postby UncleEbenezer » August 27th, 2020, 12:20 pm

Gengulphus wrote:And there are analogous questions for an N-dimensional half-space board with the first H (N-1)-dimensional hyperplanes being required to be empty.

Indeed, that was the question. AFAICS it's the only direct generalisation of yours to make sense. My use of "rows" is loose, and should indeed read "(n-1)-dimensional hyperplane".
My partial solution, spoiler-protected:

Kudos for taking a shot at it. I shall probably read your spoiler (and the followup), but not yet.


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 2 guests