By Stephen Meskin
You’re sitting in the living room while a small child is playing on the floor in front of you. The child has six blocks numbered 1, 1, 2, 2, 3, 3 and has arranged them in a row as follows:
You look at the blocks and there is something special about that arrangement, but you can’t quite figure out what it is. And then it hits you—there is exactly one block between the two 1s, exactly two blocks between the two 2s, and exactly three blocks between the two 3s. That’s interesting. So, you go over to the child’s toybox and find two more blocks, both of which you label 4.
Problem 1. Arrange eight blocks (1,1,2,2,3,3,4,4) in a row so that there is exactly one block between the two 1s, exactly two blocks between the two 2s, exactly three blocks between the two 3s and exactly four blocks between the two 4s.
Let’s call Problem 1 the4-block problem. (The child has exhibited a solution to the 3-block problem.)
Problem 2. Show that there is no solution to the 5-block problem.
(Remember that a solution to the 5-block problem would use 10 blocks.)
There is also no solution to the 6-block problem, but I’m not asking you to show that. However:
Problem 3. Exhibit a solution to the 7-block problem. (Remember again that this problem uses 14 blocks.)
There is a theorem that says there is a solution to the n-block problem if and only if n or n+1 is divisible by 4. I am not asking for a proof of that theorem; it is not easy. All the problems posed here can be done using elementary methods. But the theorem suggests that the number of solutions to the n-block problem depends on n, which is the case.
If you have a solution to the n-block problem, then writing that solution in reverse order is also a solution to the n-block problem. For example,
is a second solution to the 3-block problem. The 3-block and 4-block problems each have exactly two solutions, which are reverses of one another. However, for n≥7, there are many solutions (as long as n or n+1 is divisible by 4).
Problem 4. Give an answer to Problem 3 that is not the answer you gave to Problem 3, nor the reverse of that answer.
These problems can be solved without a computer. However, if you want to use a computer, then your Problem 4 is to give the number of distinct pairs of solutions to the 7-block problem.
Solutions may be emailed to firstname.lastname@example.org.
In order to make the solver list, your solutions must be received by February 1, 2022.
Solution to Previous Puzzles: Squid Game
1. Assume there are 18 players, 16 steps, and every player can see each player’s moves. What is the probability that each player survives?
Note that for the first player, the probability is simply (0.5)16, as there are 16 steps and the player has a 50/50 chance of survival on each. For the second player, note that there is a 50% chance the player will know only the first piece, a 25% chance they will know only the first two pieces, a 12.5% chance they will know only the first three pieces, etc. We can easily set up a sum product in a spreadsheet to compute the probabilities of each scenario. For example, if a player knows exactly five pieces, that player has a (0.5)(16-5) probability of surviving. We can compute these for every player, and come up with the answers below.
2. Assume players only see the broken glass and not the moves of the previous player. How does this change the probabilities?
The probability for player 1 stays the same. However, for player 2, there is a (0.5)16 probability that they will have no information (the first player made it unscathed and gave no new info to the remaining players), and 1-(0.5)16 probability that there will be one broken pane of glass, which means that player 2’s probability of survival is now (0.5)(16-1). We can continue to set up conditional probabilities for each of the remaining players and come up with results below. Note that in this situation player 18 is not guaranteed to make it safely across, as if a bunch of previous players get lucky and make a reasonable number of correct guesses, there still can be unknown choices for the final player.
Bob Byrne, Bob Conger, Andrew Dean, David Engelmayer, Rui Guo, Clive Keating, Chi Kwok, Paul Navratil, David Promislow, Michael Schachet, Noam Segal, John Snyder, Al Spooner, and Daniel Wade.