Take a very large chessboard (NxN, where N is huge).
Remove some fraction 1-p of the squares at random, leaving a fraction p of 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 value p_queen.
For different pieces, the critical value is different, e.g. p_rook for a rook. (Note that p_queen ⇐ p_rook.)
Question 1: What is p_queen + p_rook?
Bonus Question: Why didn’t I ask you for the values p_queen and p_rook separately?
Now let’s invent a new chess piece, the bondsman. This piece can move like a rook, and is also allowed to move along northeast-southwest diagonals between white squares, and along northwest-southeast diagonals between black squares. (There’s also the antibondsman who has the same abilities, but with the words “white” and “black” swapped.)
Question 2: What is p_bondsman?
Bonus Question: Why did I call the piece that?
Answers to follow in a later post.
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.
I am stumped on bonus question 2 and await the answer eagerly.
Delightful puzzle!
Question 1:
For any given value of p, consider the probability of a queen being able to traverse the board vertically as being q(p), and the probability of a rook being able to traverse the board horizontally (ie. from left edge to right edge) as being r(p). This notation is to emphasise that these values are dependent on p.
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 1−p of its squares intact.
Next, notice that every board with fraction p of the squares intact has a “transpose board” (flipped along the leading diagonal) which has the exact same fraction p intact. Any piece which can traverse a board vertically can traverse its transpose board vertically, and vice-versa. This means for a given p, 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 p) the probability r(1−p) 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 r(1−p)+q(p)=1.
This gives us q(p)=1−r(1−p). In the neighbourhood of the critical value pqueen, we have q(pqueen+ϵ)≈1, and q(pqueen−ϵ)≈0, so r((1−pqueen)−ϵ)≈0 and r((1−pqueen)+ϵ)≈1. But this is only true if (1−pqueen) is the critical value for a rook, ie. pqueen+prook=1.
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, 2⋅pbondsman=pbondsman+pantibondsman=1, ie. pbondsman=12.
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.
What a great cover art!
Clarification: pieces can’t move “over” the missing squares. Where the words end, the world ends. You cannot move forward in an absence of space.
Correct.
[eerie removed]
I can see the smiley through the spoiler protection. This is eerie.
Retracted due to spoilers and not knowing how to use spoiler tags.
Consider hiding your answer using spoiler tags.
Retracted, thanks.
Search here for spoiler for instructions on how to use spoiler tags: https://www.lesswrong.com/posts/2rWKkWuPrgTMpLRbp/lesswrong-faq
In clear, one must start with :::spoiler and end with :::