41–50 of 220 posts
The 'dot-town suicides' is a more general version of a puzzle I know, "The Island with Blue-Eyed People". The solution is an induction, which is unusual in these kinds of problems.
Why can't the visitor say "There are X red, X blue, and 1 yellow?" No one knows about the yellow, thinks it is themself, they all commit suicide on the spot.
Earlier quoted context omitted.
I don't know, why would someone steal a padlock unless it was attached to a box? Maybe so, though.
The wording of the problem is "anything sent through the mail will be stolen unless it is enclosed in a padlocked box".
The problem is fatally flawed by not explicitly stating that boxes locked with padlocks are also not stolen, despite not being enclosed in a padlocked box.
Earlier quoted context omitted.
Do you have any intuition to why it helps to build the query sequence on the data? It seems natural that if you have to plan the queries for everybody in advance, you can't do better than 2^(-100) or perhaps (50!)^2/100!. Yet somehow by using the return values to find our next query point we can do much better. Blows my mind.
Each individual still has a ~50% chance of being unable to find their name using the query sequence protocol. By agreeing to the same query sequence their success modes and failure modes are now linked. If there's a cycle of 51 or greater, all of those individuals in that cycle are guaranteed to fail, while if they're in a cycle of 50 or less, all of those individuals are guaranteed to succeed. What this protocol doe…
The 'dot-town suicides' is a more general version of a puzzle I know, "The Island with Blue-Eyed People". The solution is an induction, which is unusual in these kinds of problems.
https://en.wikipedia.org/wiki/Common_knowledge_(logic)
Spivak has a version of it in his Calculus book, phrased as 17 (heh!) professors who must resign if a flaw is found in their published work (hehehe), and all have a flaw in their papers, known to each other except each author.
"Learning a single variable polynomial" also falls into this camp, although partly due to learned bias. https://jeremykun.com/2014/11/18/learning-a-single-variable-...
Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.
One that I heard last week: There is an 8x8 checkerboard in a room with a coin placed on each square. Each coin is either facing heads or tails up, and the face is determined randomly. Before you can inspect the board, a "master" comes in, picks a square of interest, and must make a manipulation to the board by flipping one of the 64 coins. He then exits the room. You are now allowed to enter, and must read out which…
Are you supposed to be collaborating with the "master"?
One that I heard last week: There is an 8x8 checkerboard in a room with a coin placed on each square. Each coin is either facing heads or tails up, and the face is determined randomly. Before you can inspect the board, a "master" comes in, picks a square of interest, and must make a manipulation to the board by flipping one of the 64 coins. He then exits the room. You are now allowed to enter, and must read out which…
The version you gave is missing information and so can't be solved as stated.