@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:
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 ...
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.
Since the worst possible case is ...
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
An important note:
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.
The key observation:
Let's see which options are there:
That should be all.
First one, number is in reverse
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 :-).
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 ...