2

So there's a puzzle I heard, and I think I know the answer to, but I wanted to share my logic to see if I am correct. I am also interested in a more mathematical way to solve it which escapes me. Here's the setup:

There are 4 boxes labelled A,B,C and D. Each box contains one of the 4 letters and exactly one box contains the same letter as labelled on it. What is the minimum number of boxes required to open in order to know exactly which box contains the letter matching its label?

I am fairly confident that the answer is 2, because on the first choice I either find the correct box or I don't. If I don't then I know that box is not correct (obviously) but it also can't be the box with the label matching the letter in the one I opened. So then I just choose any of the other two boxes, and either I get the correct box, or I know it is the other.

When I'm asking for a more mathematical method, I feel like there should be a way to do this with permutations and combinations but I am stuck on how. My idea was to determine the number of possible arrangements and see how many possibilities go away with each choice. I thought the number of arrangements should be $4!$, but then I couldn't get a number for the reduction of possibilities of each choice.

Is this another way to solve this problem and if so, how does it work? If this isn't, what is another, more formal mathematical way of considering this situation and finding the solution?

PiGuy314
  • 637
Josh Knight
  • 99
  • 3
    Only 8 out of the 4! arrangements have exactly one letter in the right box: ACDB, ADBC, CBDA, DBAC, BDCA, DACB, BCAD, CABD. One of the 4 letters is correct, and the other three are cycled around in one of two directions, giving 4*2=8 possible arrangements. Unfortunately every letter occurs in each position twice amongst those arrangements, so whatever is in the first box you open, there are still two arrangements possible. If you didn't get the right box first time, you will need a second box to distinguish between the two arrangements. – Jaap Scherphuis Aug 30 '21 at 13:37
  • 1
    The same underlying logic as appears in both your question and the comment above, but using cycle decompositions of permutations. The correspondence between the box labels and contents defines a permutation in $S_4$, and by the hypotheses, that permutation must have the form $(W;X;Y)(Z)$ where ${W,X,Y,Z}={A,B,B,D}$ in some order. Opening one box either tells you the $(Z)$ part if you're luck, or tells you $(W;X;?)(?)$. In the second case, opening a second box directly fixes what one of these "?"'s is, and indirectly tells you the other "?". – David Sheard Aug 30 '21 at 13:45
  • "What is the minimum" is ambiguous. Presumably they mean, you select k, then you open those k, then you have to know? Or they could mean open, check, open , check... and they could be asking the shortest guaranteed sequence or the shortest possible sequence... – DanielV Sep 07 '21 at 13:13

0 Answers0