New answers tagged optimization
2
I'll get the ball rolling:
No proof of optimality because I doubt this is optimal.
5
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 ...
1
56 moves
9
Smallest sum is
Solutions are
Reasoning
4
This should be optimal.
-1
The worst case has the potential to reach any positive, finite number. I will demonstrate this with a counter-example using the 11-question strategy.
Let's label the guards:
T always tells the truth.
F always lies.
Y always says yes.
N always says no.
R gives a random answer.
State 1:
State 2:
State 3:
State 4:
Now what?
Since the worst possible case is ...
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:
8
New high score :P
List of possible primes is 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2. Distances between those primes are 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 2, 2, 1.
Which?
The key observation:
So
This means
Let's see which options are there:
That should be all.
First one, number is in reverse
9
Improving upon Gareth's answer (the details of which I will not repeat) with consideration of ThomasL's suggestion, a solution with 12 primes is found:
Two solutions with 11 primes were also found:
7
Wrong answer
Well, it might be the right answer for all I currently know, but my argument has multiple errors in it (pointed out by others in comments). I may fix it, but others should feel free to post correct solutions before I do :-).
0
Without borrowing any bottles:
After that:
Prove it's the best answer without borrowing:
By borrowing bottles:
2
An upper bound, at least.
First, forget terms of whole bottles for a minute. A "bottle" is actually a weirdly-named, infinitely-divisible item that can be consumed and then traded.
7
I'm not sure if this is the kind of solution you are looking for:
3
4
Probable answer:
Explanations:
1
I was pointed to this very interesting post by RobPratt, who helped me with a related problem.
After implementing a similar solution to his, using a random scatter of points and looking for a solution by set cover binary linear programming (which works quite well indeed), I thought I'd give a try to a more 'geometry-based' solution.
[BTW, I am using hidden ...
2
Turned out to be the same answer, but followed by a proof:
Prove that a better answer isn't possible:
3
I think you can do this with 9 questions
first
irrespective of the outcome
Now to figure the remaining people
so the final number of questions you need to ask is
Top 50 recent answers are included
