# Tag Info

19

Probably not optimal, but here's an approach that saves at least

13

The optimal strategy takes Here's why this is necessary: And here's a way to do it: Fun fact:

8

@StephenTG's answer is the best. Here's a proof: Since there are 100 possible numbers, they must encode into 100 "states". In other words,

6

Nuclear Hoagie's remark is a good start. I evaluated the best strategy with a computer and here is what came out:

5

@Deusovi was a few hours earlier, but perhaps this answer gives a simpler argument for the lower bound and a more practical description of an optimal strategy. Let N (=52) be the number of cards and k (=6) the smallest integer such that $N \le 2^k$. First, let us show that at least k operations are required: Optimal algorithm:

5

Question 1 Question 2 improved How to encode: Question 2 initial

4

99 prisoners: The way to transmit more than one bit of information from the placement of the envelope and paper comes from a legalistic interpretation of the rule: If they are wrong then they are allowed to... a) open the envelope, b) see the secret number and c) place it back in the envelope. Then they are shot. ... They have no other means to communicate.

3

Here's an answer to question 1 which saves at least prisoners. The strategy makes use of and requires that Here's the strategy: Here's why it works: A slight modification makes this work for question 2 to save at least prisoners. An important note:

3

A stronger solution. Here is an illustration of the process.

2

Edit: I started out trying to get a formal proof of optimality, but abandonded that. I leave the work here for someone else to continue if they see any merit. I did run some simulations if anyone wants to come up with a strategy they will have to do better than this. There are two ways to win as stated in the puzzle; Everyone wins if you get 100 coins If ...

2

Just some remarks I wanted to make.

2

I have a different way of getting the same amount of prisoners as @StephenTG: Here's the strategy: Here's why it works:

2

I wrote a simple Python program that implements the classic solution, and the classic solution applied row-wise to the 2d version. Some things I've found: It takes a non-trivial amount of time to run. It took me a few minutes to run 100 random test cases. As I mentioned in a comment, there is no feasible way to fully extend the classic solution to 2d, as ...

2

What I'm going to describe is a rather gung-ho strategy which, frankly, shoudn't work, but to my surprise hasn't failed a single time in all of 100,000 trials I performed. It finds the secret pattern after or fewer trials. As pattern space is vast this doesn't rule out that there are worst case patterns defeating the strategy. Strategy The heuristics that ...

1

We start with usual Mastermind logic: Now the interesting part: Therefore Nice twist on the usual Mastermind logic and should be “gettable” for a solver who is switched on. Great puzzle!

1

The strategy by Alex Jones for Question 1 can be improved for the average case, to save an expected number of approximately prisoners. The following part is the same: Now, here's how to improve the average case: This results in the following number of prisoners saved on average (if my calculation is correct): (Edit: removed bogus improved worst case ...

1

(I'm generalizing the question here, and substituting 100 by $N$) Claim: @iBug 's answer explains: Therefore, let's consider a criterion $A$. Then, for any number-in-envelope, it either satisfies or doesn't satisfy $A$. Conclusion:

Only top voted, non community-wiki answers of a minimum length are eligible