This is a linkpost for https://adam.scherlis.com/2023/07/04/two-percolation-puzzles/

Two Percolation Puzzles

16Yair Halberstadt

5Charlie Steiner

4interstice

2AK1089

1Adrià Garriga-alonso

1justinpombrio

1Adam Scherlis

1Ilio

3Thomas Sepulchre

1WilliamKiely

2Yair Halberstadt

1WilliamKiely

2Yair Halberstadt

1Ilio

New Comment

A queen can make it from front to back, iff a rook can't make it from left to right only on the removed pieces.

An ombudsman can make it from front to back iff an ombudsman can't make it from left to right only on removed pieces.

So Q1 is 1, Q2 is 0.5.

**Question 1:**

For any given value of , consider the probability of a queen being able to traverse the board vertically as being , and the probability of a rook being able to traverse the board **horizontally** (ie. from left edge to right edge) as being . This notation is to emphasise that these values are dependent on .

The key observation, as I see it, is that for any given board, exactly one of the conditions "queen can traverse the board vertically" and "rook can traverse the board horizontally using the missing squares of the board" is true. If the rook has a horizontal path across the missing squares, then this path cuts off the queen's access to a vertical path. This "virtual board" consisting of the missing squares has fraction of its squares intact.

Next, notice that every board with fraction of the squares intact has a "transpose board" (flipped along the leading diagonal) which has the exact same fraction intact. Any piece which can traverse a board vertically can traverse its transpose board vertically, and vice-versa. This means for a given , the fraction of boards the rook can traverse horizontally is the same as the fraction of boards it can traverse vertically.

Thus (again for fixed ) the probability of a rook being able to traverse a random board's complement horizontally is the same as the probability of a rook being able to traverse a random board's complement vertically. But we know that exactly one of "a queen can traverse the board vertically" and "a rook can traverse the board horizontally on the missing squares" is true, so .

This gives us . In the neighbourhood of the critical value , we have , and , so and . But this is only true if is the critical value for a rook, ie. .

I suppose the reason you asked for both probabilities together is that it helps to consider when either or both pieces can or cannot traverse certain boards, as I did. It would have been significantly more effort, if not impossible to deduce the probability of either individually without consideration as to the other.

**Question 2:**

We use the same argument as with the queen and the rook, but instead consider the bonsdman and antibondsman. By symmetry, they have the same probabilities, and the bondsman can traverse a board vertically if and only if an antibondsman cannot traverse the board's complement horizontally. This means for the same reason as before, , ie. .

With regard to your bonus question, I have a hunch that this is somehow related to the bond problem in percolation theory (somehow, your title may have provided a hint here). Maybe this is the transition / critical probability for when bonds form in some specific type of lattice.

Considering squares as representing nodes here and the bondsman's ability to travel between two squares to be an edge, this means every square is linked to exactly six squares (four cardinal directions and the two possible diagonals). This gives six edges, which indicates that we might be dealing with a cubic lattice?

**Reflections:**

I'm very interested to see the answers to these questions. I have never met percolation theory before, and found these problems really compelling (I'm a fairly new reader of this site, and this post inspired me to make my first comment here). I hope I've not done anything wrong with this comment (the spoiler tags should be working, and I don't think I've broken any rules). Thank you for the puzzles!

*NB. A previous version of this comment had the right answer to Q1 by a mostly right method with an error, and the right answer to Q2 by a completely incorrect method. My comment has since been edited to reflect the correct version.*

Search here for spoiler for instructions on how to use spoiler tags: https://www.lesswrong.com/posts/2rWKkWuPrgTMpLRbp/lesswrong-faq

Take a very large chessboard (NxN, where N is huge).

Remove some fraction

1-pof the squares at random, leaving a fractionpof them.Can you place a queen on the first row and then, via some sequence of legal moves, get it to the last row?

This is probabilistic, of course, but it turns out the probability of success undergoes a sharp phase transition -- near-zero for small values of

p, then suddenly rising almost to one in the vicinity of a critical valuep_queen.For different pieces, the critical value is different, e.g.

p_rookfor a rook. (Note thatp_queen<=p_rook.)Question 1:What isp_queen + p_rook?Bonus Question:Why didn't I ask you for the valuesp_queenandp_rookseparately?Now let's invent a new chess piece, the

bondsman. This piece can move like a rook, and is also allowed to move alongnortheast-southwestdiagonals betweenwhitesquares, and alongnorthwest-southeastdiagonals betweenblacksquares. (There's also theantibondsmanwho has the same abilities, but with the words "white" and "black" swapped.)Question 2:What isp_bondsman?Bonus Question:Why did I call the piece that?Answers to follow in a later post.