Two Lovely Puzzles
These two puzzles were given to me by Andrey Khesin.
Puzzle. My friend and I are going to play the following game at a casino. Each round, each of us (my friend, the dealer, and I) secretly chooses a black or white stone and drops it in the same bag. Then, the contents of the bag are revealed. If all three stones are the same color, my friend and I win the round. If not, we lose to the dealer. One extra caveat. I have a superpower: as soon as we sit down, I can read the dealer’s mind and learn the dealer’s choices for all future rounds. Unfortunately, at that time, it’s too late for me to give this information to my friend and win all the rounds. The only thing we can do is agree on a strategy before the game.
- Design a strategy to win 6 out of 10 rounds.
- Design a strategy to win 7 out of 11 rounds.
- Is it possible to win 6 out of 9 rounds?
Puzzle. In a crowd of 70 people, one person is a murderer, and another person is a witness to said murder. A detective can invite a group into his office and ask if anyone knows anything. The detective knows that everyone except the witness would say nothing. The witness is a responsible person who is more afraid of the murderer than they desire to fulfill their civic duty. If the witness is in the same group as the murderer, the witness will be silent; otherwise, the witness will point to the murderer. The detective knows this will happen and wants to find the murderer in as few office gatherings as possible. What is the minimum number of times he needs to use his office, and how exactly should the detective proceed?
Share:
Zarunias:
For the second puzzle I can do it in 12. On the one hand I would be surpised if there is a better solution. On the other hand I can do 81 persons with that many gatherings.
Strategy: Every person gets a card from the game SET. For each of the twelve properties (red, green, purple, 1, 2, 3, ellipse, squiggle, diamond, full, half, empty) you have a gathering with all persons that have such a card.
13 March 2024, 9:22 pmLazar Ilic:
Online Matching Pennies by Olivier Gossner, Penelope Hernandez, and Abraham Neyman in the Center For The Study Of Rationality. It is possible to win 6 out of 9 rounds. In fact, there exists a relatively simple strategy for winning 3X out of 4X+1 rounds:
https://puzzling.stackexchange.com/questions/30214/strategy-to-beat-the-casino
”
1. To start, play 0 until you lose a round.
2. Play the value played by the leader in the last round that was lost. Do this for 3 rounds, unless 3d or 3e happens.
3a. If you only won 2 of the 3 rounds, do step 2 again.
3b. If you won all 3 rounds, keep playing the value until you lose a round. Do step 2 again.
3c. If you won only 1 round, go to Exception 1.
3d. If you played the same value as the Casino, but Leader didn’t, and you’re at or after Round 5, go to Exception 2.
3e. If you played the same value as the Casino, but Leader didn’t, and you’re before Round 5, go to Exception 3.
Exception 1. Look at the bits played in the last 2 rounds you lost. Let those be A and B. Play the next 5 rounds as: A ~A A B ~B.
Exception 2. Let the bit you played in the last round you lost be A. Play ~A until round 7, then play 1 0 in rounds 8 and 9.
Exception 3. Play the same bit you played in the last round until round 4. Let A be the bit Leader played in the last round that the Casino played a different bit than you did. If you had already won a round when you came to this exception, play ~A A A 0 1 for the last 5 rounds. Otherwise play A A ~A 0 1.
”
8 canonically as the set of the 70 people’s inclusion in asked subsets must form an antichain and [8 choose 4] = 70 conveniently for the bounds of this problem. That is, assign to each person a unique subset of size 4 from [1, 2, 3, 4, 5, 6, 7, 8] ask them on their assigned rounds. For example, if the witness is assigned [2, 5, 6, 8] and the murderer [2, 4, 6, 8] then the witness will identify the murderer on questioning round 5. If not forming an antichain then the murderer could be present during every asking session where the witness is present.
14 March 2024, 5:39 amOscar Cunningham:
For the second puzzle, the answer is 8.
We will call each person into the office for 4 out of the 8 gatherings. Since 8C4 = 70, we can assign each person a different 4 gatherings. So the murder and the witness are called in the same number of times, but not on exactly the same occasions. So there must be one time when the witness is in and the murderer is not.
To show that it can’t be done in 7, note that since 70 > 2^6 there must be some pair of people who are called into the office on exactly the same gatherings out of the first 6. If these people are the witness and the murderer in some order, then one further gathering isn’t enough to deduce which is which.
14 March 2024, 8:18 amZarunias:
Nice solution, Oscar. Haven’t thought of the problem in this way.
14 March 2024, 9:47 amzielaj:
There seems to be a subtle difference between Puzzle 1 from this blog post and the Casino puzzle from stackexchange: in this blog’s version, if player 1 (“I”) and the dealer choose different colors, then player 2 (“my friend”) is not able to tell who cast which stone. In the stackexchange version, player 2 can tell.
While the difference is small, I believe it may be crucial for the “6 out of 9” case. For example, the condition “If you played the same value as the Casino, but Leader didn’t” is not testable in this blog’s version of the puzzle. Of course, there may be another strategy that still guarantees 6 out of 9, so I wrote a short C++ program that attempts to estimate the maximum number of wins that can be guaranteed for a given number of rounds. (The program is not perfect, as enumerating all possible strategies seems prohibitively expensive, but the results seem plausible. For example, by backtracking the computation, I was able to convince myself that a “3 out of 5” strategy actually exists.)
https://gist.github.com/zielaj/f130fe15d36340538fa0743c0bd4c351
Here are a few results. In each row, the first number is the number of rounds, the second the maximum number wins in the stackexchange version, and the third is the maximum number of wins in this blog’s version:
1 0 0
2 1 1
3 1 1
4 2 2
5 3 3
6 3 3
7 4 4
8 5 5
9 6 5 ***
10 6 6
11 7 7
12 8 8
13 9 8 ***
…
1000 806 768
The value for 1000 rounds also is also mildly encouraging because it is not that far from the asymptotic value derived in “Online Matching Pennies” (0.810710…). This also suggests that this blog’s version is asymptotically harder.
https://oeis.org/A320084
Still, at 1000 rounds I’d expect a better agreement than 0.806 ≈ 0.810710…, so it may be that my program misses some strategies.
17 March 2024, 10:30 pmLazar Ilic:
Oh interesting, thanks zielaj! I believe that Dr. Peter Winkler stated in writing in his book Mathematical Puzzles [which is now free] that he would post up a solution soon for the 6 out of 9 case. Maybe he can comment here.
I should have referenced Sperner’s Theorem as part of the canonical numerical convenience above in Puzzle 2.
19 March 2024, 8:52 amSanandan Swaminathan:
Well, Dr. Winkler’s Matching Coins puzzle in his book is equivalent to the casino puzzle on stackexchange. The follower can hear what the leader said for the previous coin toss, or the follower can see the actual result of the previous toss (the coin result is equivalent to the “dealer’s choice” in the casino puzzle). So, the “6 out of 9” scenario can be solved. Dr Winkler’s puzzle doesn’t have the additional handicap that zielaj has identified in the bag and stones puzzle here where all the stones are mixed up. Just like zielaj, I can’t think of a way to achieve 6 out of 9 in the bag and stones version. This will haunt until Dr. Tanya or the puzzle submitter Andrey Khesin confirm that 6 out of 9 can or cannot be achieved in this version :).
19 March 2024, 2:22 pmzielaj:
I’ve made some performance improvements to my program, and was able to run it for 100,000 rounds. For the stack exchange version of the puzzle, I get 81065 wins, which is pretty close to the bound from the paper (0.810710…). This makes me a bit more confident in my program, so I’ll comment a bit on what it does exactly and how this affects the “6 out of 9” case (see the comments in the program for details, the link is my previous comment).
My program is not given the question “are 6 out of 9 wins possible?”. Instead, it’s given the question, “how much do we need to constrain the dealer to make 6 out of 9 possible?”. In other words, “what is the maximum size of the family of binary sequences of length 9 that we allow the dealer to choose from in order to make scoring 6 out of 9 always possible?”. If the answer is 512 (all sequences), then a strategy exists, if the answer is smaller, then it doesn’t.
My program does not compute the exact answer, instead it computes an upper bound. This is because it doesn’t check that all the sequences in the family of sequences are distinct. Instead (for tractability), it just assumes that if we take a family of size A and union it with a family of size B, the union will have A + B elements (modulo some rudimentary checks for overlaps that are not comprehensive).
In this case, for this blog’s version of the “6 out of 9”, my program outputs that we need to restrict the dealer to at most 464 sequences out of the 512 possible. So unless there’s a bug in the reasoning or in the implementation, this should mean that the actual number of sequences is at most 464, which would imply that this blog’s version of “6 out of 9” has no solution. For the stack exchange version, my program says 512 out of 512 sequences are possible, which is consistent with the strategy for “6 out of 9” existing (which we know it does from other sources, but we can’t infer that from the output of my program alone).
20 March 2024, 9:32 amLazar Ilic:
For the written record, there exist simple strategies for the 6 out of 10 and 7 out of 11 cases. Our strategy involves partner playing Black any time they are not in an indicated range. We do opt to take free wins as they come under this convention, so we also play Black if the casino is playing Black. One may use the first casino White turn to indicate to our partner the majority colour of the casino in the following 3 moves. When we do not win on this turn, our partner deduces to remove a White from the 2 pebbles they see and thereby discover our indication. Then we can also take 3 out of 3 wins if that occurs from there or else use a loss case similarly to indicate to our partner the majority for the 3 following this chunk of 3. So we basically have a W prefix followed by a L[LWW] block [which can chain off in to [LWW] blocks ad infinitum or a [WWW] block which transitions back in to the starting position] or a L[WWW] block which also transitions back in to the starting position. If there are less than 3 left we may still indicate majority on such a chunk. Inspection reveals the worst case scenarios are L[LWW]WWWL[LW] tied with L[LWW][LWW][LWW] for 6 out of 10 and so on and so on. Sorry for the mediocre writing here, after that paper via Internet Archive I have doubts the optimal general strategy here would include taking wins as they come and simply indicating 3 majorities.
24 March 2024, 10:03 amGregory:
For the first puzzle:
To win 6 out of 10 rounds, choose a stone opposite to the majority in the bag, and alternate your strategy after 5 rounds. For 7 out of 11, agree on a fixed sequence and adjust the 11th round based on prior rounds and the dealer’s choices.
For the second puzzle:
25 March 2024, 4:26 amTo find the murderer in the fewest gatherings, divide the 70 people into two groups and invite one after the other. If the witness remains silent in the first group, they are in the second; otherwise, question both groups after the first gathering Check Vine Density Calculator
Lazar Ilic:
Perhaps this puzzle is worth exploring further. There exists a very easy proof that strategy is not optimal. For example, we could produce a dominating strategy by adding in a new condition. If we add a new conditional where we intentionally lose 3 out of 3 in some indicated range of 3 and our partner can deduce our 1 signal bit… say the casino will go WWWWBBBBB…B where there are 30 opposite Blacks in a row. Then we can go W on move 1 so our partner goes B and gets the signal to go W for moves 2-4. And then on moves 2-4 we actually go BBB then our partner gets the indication now for the special condition and goes B on moves 5-34 actually and we can win all of those then we get 30 wins out of 34 which is better than we would have done otherwise, and in all of the other cases we get the same outcome so… I will think more about how to actually formally extend the paper and think about the communicational information theory in the bits in this scenario.
25 March 2024, 7:34 amLazar Ilic:
I meant to write down WBBBWWWWW…W with a streak of 30 Whites at the end rather… where we go WWW on round 2-4 to signal off a 30 streak of Whites to the partner we can then go in on… in any case I suggest removing the AmazonSmile suggestion from your donation blurb now it has ended.
25 March 2024, 7:51 am