Ahh, I love puzzles like these! I knew some, but not all of them, so thank you for posting this here! Some thoughts:
25 Horses:
Does anybody have a short proof of optimality, i.e. that if you claim the solution is $n$ races, it cannot be accomplished in $n-1$?
Pirate treasure:
I think some sort of tie-break information is required: if a pirate knows that their vote has no infuence on the number of coins they will obtain, will they vote ‘no’ out of spite? Or ‘yes’ to preserve the crew?
Knights and knaves, and What is the name of this god:
If you’re willing to spend considerable time you can find a fully general solution to puzzles of this type, although the answers will be long logical constructions.
Blind maze:
Is there some short elegant solution to this? The shortest answer I have is some concatenation of solutions that works but is ugly.
Prisoners and boxes:
Am I confused, or is there a 100% guaranteed strategy to save all prisoners? There is a similar but related problem where the problem is not `made easier’ and the prisoners are just sent in (one by one) without warning, and if they all find their own piece of paper they are all set free but if at least one fails then they are all kept in prison. Can you find the optimal solution (along with its expected success rate) now?
Nine dots puzzle:
There are actually two different solutions to this one!
And lastly a contribution of my own:
Having become bored with the classical game of Battleship, you and a friend decide to upgrade the rules a bit. Instead of playing on an nxn-square you will play on the entire planar lattice. Furthermore, you always found it unrealistic that these ships are just sitting there while they are getting bombed, so now at the start of the game you pick a movement vector (with integer components) for each ship, and at the start of each of your turns each ship moves by its movement vector. For simplicity we assume ships can occupy the same square at the same time. To clarify: you still only command the standard fleet of the original Battleship game.
Find a shooting strategy which is guaranteed to sink all your friend’s ships.
Hint: Svefg pbafvqre gur pnfr jvgu bayl bar 1k1-fvmrq fuvc cynlvat ba gur yvar bs vagrtref, vafgrnq bs gur 2Q ynggvpr.
Pirate treasure: you’re right that tiebreak information is needed. I’ve added it in now—assume the pirates are spiteful.
Blind maze: nope, it’s a fairly ugly solution.
Prisoners and boxes: yes, you can save all of them. Is the solution to your variant the same as my variant?
Battleships: I’ve found an ugly solution, and I expect it’s the one you intended, but is there anything nicer? Sbe rirel fdhner, pbafvqre rirel cbffvoyr zbirzrag irpgbe, juvpu tvirf hf n ghcyr bs yratgu 4. Gura jr vgrengr guebhtu rirel fhpu ghcyr hfvat qvntbanyvfngvba, naq ng rnpu gvzrfgrc jr pna pnyphyngr jurer n fuvc juvpu fgnegrq ba gung fdhner jbhyq unir raqrq hc ol gur pheerag gvzrfgrc, naq fubbg vg.
Prisoners and boxes: yeah, we are probably thinking of the same solution. Vg vaibyirf gur cebonovyvgl bs svaqvat n x-plpyr va na neovgenel ryrzrag bs gur crezhgngvba tebhc ba a ryrzragf.
Battleships: that’s the intended solution, yes. I don’t know of any nicer one
25 Horses. When you race 5 horses, you know that any horse that doesn’t win isn’t the fastest. Every horse needs to be raced at least once, or you will have no idea how good it is. Each race rules 4 horses out of the running for fastest, so you need 6 races to find the fastest horse.
However you arrange it, you can’t guarantee that the best horse only runs once, so sometimes you will have 2 horses that only lost to the best. Either could be second.
There is no strategy that always finds the first and second in 6 races.
There is a strategy that always finds the best three in 7 races. 5 groups, winners race, those which were directly beaten by at most 2 horses race. (
There is a strategy that always finds the best three in a variable number of races that is sometimes as low as 6.
Ahh, I love puzzles like these! I knew some, but not all of them, so thank you for posting this here! Some thoughts:
25 Horses:
Does anybody have a short proof of optimality, i.e. that if you claim the solution is $n$ races, it cannot be accomplished in $n-1$?
Pirate treasure:
I think some sort of tie-break information is required: if a pirate knows that their vote has no infuence on the number of coins they will obtain, will they vote ‘no’ out of spite? Or ‘yes’ to preserve the crew?
Knights and knaves, and What is the name of this god:
If you’re willing to spend considerable time you can find a fully general solution to puzzles of this type, although the answers will be long logical constructions.
Blind maze:
Is there some short elegant solution to this? The shortest answer I have is some concatenation of solutions that works but is ugly.
Prisoners and boxes:
Am I confused, or is there a 100% guaranteed strategy to save all prisoners? There is a similar but related problem where the problem is not `made easier’ and the prisoners are just sent in (one by one) without warning, and if they all find their own piece of paper they are all set free but if at least one fails then they are all kept in prison. Can you find the optimal solution (along with its expected success rate) now?
Nine dots puzzle:
There are actually two different solutions to this one!
And lastly a contribution of my own:
Having become bored with the classical game of Battleship, you and a friend decide to upgrade the rules a bit. Instead of playing on an nxn-square you will play on the entire planar lattice. Furthermore, you always found it unrealistic that these ships are just sitting there while they are getting bombed, so now at the start of the game you pick a movement vector (with integer components) for each ship, and at the start of each of your turns each ship moves by its movement vector. For simplicity we assume ships can occupy the same square at the same time. To clarify: you still only command the standard fleet of the original Battleship game.
Find a shooting strategy which is guaranteed to sink all your friend’s ships.
Hint: Svefg pbafvqre gur pnfr jvgu bayl bar 1k1-fvmrq fuvc cynlvat ba gur yvar bs vagrtref, vafgrnq bs gur 2Q ynggvpr.
Pirate treasure: you’re right that tiebreak information is needed. I’ve added it in now—assume the pirates are spiteful.
Blind maze: nope, it’s a fairly ugly solution.
Prisoners and boxes: yes, you can save all of them. Is the solution to your variant the same as my variant?
Battleships: I’ve found an ugly solution, and I expect it’s the one you intended, but is there anything nicer? Sbe rirel fdhner, pbafvqre rirel cbffvoyr zbirzrag irpgbe, juvpu tvirf hf n ghcyr bs yratgu 4. Gura jr vgrengr guebhtu rirel fhpu ghcyr hfvat qvntbanyvfngvba, naq ng rnpu gvzrfgrc jr pna pnyphyngr jurer n fuvc juvpu fgnegrq ba gung fdhner jbhyq unir raqrq hc ol gur pheerag gvzrfgrc, naq fubbg vg.
Prisoners and boxes: yeah, we are probably thinking of the same solution. Vg vaibyirf gur cebonovyvgl bs svaqvat n x-plpyr va na neovgenel ryrzrag bs gur crezhgngvba tebhc ba a ryrzragf.
Battleships: that’s the intended solution, yes. I don’t know of any nicer one
25 Horses. When you race 5 horses, you know that any horse that doesn’t win isn’t the fastest. Every horse needs to be raced at least once, or you will have no idea how good it is. Each race rules 4 horses out of the running for fastest, so you need 6 races to find the fastest horse.
However you arrange it, you can’t guarantee that the best horse only runs once, so sometimes you will have 2 horses that only lost to the best. Either could be second.
There is no strategy that always finds the first and second in 6 races.
There is a strategy that always finds the best three in 7 races. 5 groups, winners race, those which were directly beaten by at most 2 horses race. (
There is a strategy that always finds the best three in a variable number of races that is sometimes as low as 6.
I know the 7 races solution, but this proof that 6 doesn’t work is nice!