New answers tagged strategy
3
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!
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 ...
6
Question 1
Question 2 improved
How to encode:
Question 2 initial
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:
13
The optimal strategy takes
Here's why this is necessary:
And here's a way to do it:
Fun fact:
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 ...
0
Let's say there're $K\gt 50$ chips in the pot and it's your move. The drama of the game is this: should you adopt the selfish strategy of betting $K-1$, or the cooperative strategy of betting $100-K$? I claim there exists an Nash equilibrium for this game, and in that equilibrium the threshold number of chips for cooperation to happen is
4
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:
2
I have a different way of getting the same amount of prisoners as @StephenTG:
Here's the strategy:
Here's why it works:
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:
-4
So they were having time to make strategies so my strategy would be that the first prisoner who will go will tell any no. If number is correct by luck it's good otherwise he will see the number if number is greater then 50 he will leave envelope facing upwards else downwards the same process other prisoner will repeat till one no. Is left during this ...
-5
In worst case scenario 94 prisoners can be saved
We just need to use k/2 formula,
In case of 100 if the number is less than 50 then envelope is down and if more than 50 then envelope is up
If less than 50 then divide into two parts 25-25 and in case of odd numbers i.e. 25 choose the even one i.e. 12
And so on...
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.
2
Just some remarks I wanted to make.
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,
19
Probably not optimal, but here's an approach that saves at least
0
OPTIMAL STRATEGY to escape in less than 2^n days
I proved above that it is always possible to escape in less than 2^n days with optimal play. Here I will also show 'how' to do it (strategy), and prove that it is optimal and always possible.
Strategy
Generate ordered list of 'win/optimal positions' ( arrangements of n H/T coins ):
starts with HH..HH at ...
0
Had another answer that turned out to be the same as @bobble's.
Another attempt:
-1
You can escape in LESS than 2n days
It was already proven that you can ALWAYS escape in 2n "cycles" (each cycle has n days) which means escape is always possible in n*2n days (but that is not optimal play).
Optimal play require that you never repeat same position (arrangement of the coins) - because that would mean Devil has won since it will ...
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 ...
Top 50 recent answers are included
