Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf](math.dartmouth.edu)
math.dartmouth.edu
Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
https://math.dartmouth.edu/~pw/solutions.pdf
219 comments
Let F be the only person who is permitted to turn the light oFF.
The N be every body else---they will be turning the lights oN.
F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing.
Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if their counter is more than 0 and the light is off, turn it on and decrement their counter.
If the light starts on, F will turn it off once, putting their counter at 1. Then, if their counter gets to 198 = 1 + 197, they will know all 99 N people has been in the room once, (and will be certain all but one have been twice).
If the light starts off, some N will turn it on. F's counter gets to 198 when everybody else has been in the room at least twice.
If any prisoner is queried, they should answer "I don't know" unless they are F and their counter is at 198.
F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing.
Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if their counter is more than 0 and the light is off, turn it on and decrement their counter.
If the light starts on, F will turn it off once, putting their counter at 1. Then, if their counter gets to 198 = 1 + 197, they will know all 99 N people has been in the room once, (and will be certain all but one have been twice).
If the light starts off, some N will turn it on. F's counter gets to 198 when everybody else has been in the room at least twice.
If any prisoner is queried, they should answer "I don't know" unless they are F and their counter is at 198.
This is indeed the standard solution. There is also a more difficult version: Every prisoner is required to have the same strategy (so you cannot pick a unique person F). (Every thread runs the same program, and threads do not have access to a unique thread identifier.)
I'll just solve this assuming the light starts off, because otherwise I have a feeling it will get miserable to think through.
Every prisoner starts at c=1. If light is on, turn it off and decrement c. If the light is off, turn it on and increment c. It c hits 0, always do nothing. If c=101, everyone has been to the room.
Everyone wants to turn off 1 more light than they turn on, but that means one person has to turn on the light 99 more times than they turn it off (and then they have to see it off, indicating the 99th person has reached c=0, and turn it on for themself to reach c=101).
Edit: Thinking back through, I think just starting at c=2 and waiting for c=200 works for an uncertain initial state of the light.
Edit 2: One of the problems with this method is that you are essentially waiting for the nature of random distributions to select people unevenly to get people to hit c=0 and be "removed". At higher average c (excluding 0s), this may take a while. It can probably be made faster by having a chance to not turn on the light at low c and not turn off the light at high c, but I wouldn't be surprised if that doesn't actually end up being faster. At the very minimum a prisoner could stop lowering c once it got above the 50% mark.
Every prisoner starts at c=1. If light is on, turn it off and decrement c. If the light is off, turn it on and increment c. It c hits 0, always do nothing. If c=101, everyone has been to the room.
Everyone wants to turn off 1 more light than they turn on, but that means one person has to turn on the light 99 more times than they turn it off (and then they have to see it off, indicating the 99th person has reached c=0, and turn it on for themself to reach c=101).
Edit: Thinking back through, I think just starting at c=2 and waiting for c=200 works for an uncertain initial state of the light.
Edit 2: One of the problems with this method is that you are essentially waiting for the nature of random distributions to select people unevenly to get people to hit c=0 and be "removed". At higher average c (excluding 0s), this may take a while. It can probably be made faster by having a chance to not turn on the light at low c and not turn off the light at high c, but I wouldn't be surprised if that doesn't actually end up being faster. At the very minimum a prisoner could stop lowering c once it got above the 50% mark.
Very nice solution.
I wonder if it can be made not rely on randomness at all. The 'standard' solution just required that every prisoner would be taken to the room infinitely many times. As long as this was the case, the warden could try any devious sequence they liked.
I wonder if it can be made not rely on randomness at all. The 'standard' solution just required that every prisoner would be taken to the room infinitely many times. As long as this was the case, the warden could try any devious sequence they liked.
Interesting question. Haven't solved it yet, but it did give me an idea for an optimization.
If the prisoner stores c_max, they can decide to only ever turn off the light (until c=0) if c < c_max - 1.
This is because there is at least 1 other prisoner still turning on the light (they could turn off the light they turned on to reach c = c_max - 1, but only get lower if someone else turns on the light for them).
Unfortunately an adversarial sequence still hangs progress, as prisoners can be juggled between c_max and c_max-1.
If the prisoner stores c_max, they can decide to only ever turn off the light (until c=0) if c < c_max - 1.
This is because there is at least 1 other prisoner still turning on the light (they could turn off the light they turned on to reach c = c_max - 1, but only get lower if someone else turns on the light for them).
Unfortunately an adversarial sequence still hangs progress, as prisoners can be juggled between c_max and c_max-1.
Ugh. This gives me a headache.
Why does each person need to enter the room twice? F is allowed to turn the light off, each other person can only turn the light on ONCE. Every time F enters and the light is ON he turns it off and increments his counter. When F's count gets to 100 they go free (99 turned it on ONCE and there was at most one false positive) and, obviously, F has entered at least 100 times.
If the initial state of the light is known to F then you only need once per person.
However if the initial state of the light is unknown to F then your proposal would deadlock at 99 wherever the light starts off, because it will only ever be turned on 99 times, so 100 will never be reached.
The twice entry solution avoids this issue because if the light starts on then the most that 98 people will turn it on is 196 times, for a total of 197 "on" count, with 198 guaranteeing 99 people involved, but if the light starts off the 99 people will turn it on 198 times as well.
However if the initial state of the light is unknown to F then your proposal would deadlock at 99 wherever the light starts off, because it will only ever be turned on 99 times, so 100 will never be reached.
The twice entry solution avoids this issue because if the light starts on then the most that 98 people will turn it on is 196 times, for a total of 197 "on" count, with 198 guaranteeing 99 people involved, but if the light starts off the 99 people will turn it on 198 times as well.
The 198 solution has the same problem. F cannot tell if the light is on because it was originally on, or G preceded F and the light started off. You're always going to be susceptible to off-by-one errors.
[deleted]
> If the light is on when F gets to the room, they turn the light off, and they increment their counter.
Who is they???
Who is they???
Good grief. If you want to write objective, do so, and ommit personal pronouns all together, but don't employ this archaic, confusing grammatical quirk. I'd like to point out to you, ekke's comment was much better understandable and shorter.
Edit: Did you even read what you linked?
> One explanation given for some uses of they referring to a singular antecedent is notional agreement, when the antecedent is seen as semantically plural
F was definitely singular.
> Distributive constructions apply a single idea to multiple members of a group. They are typically marked in English by words like each, every and any.
That is indeed something I often wondered about, sadly that part is inconclusive.
> Referential and non-referential anaphors
I didn't even try to read. That looks like it should be it's own article.
> On the other hand, when the pronoun they was used to refer to known individuals ("referential antecedents, for which the gender was presumably known", e.g my nurse, that truck driver, a runner I knew), reading was slowed when compared with use of a gendered pronoun consistent with the "stereotypic gender" (e.g. he for a specific truck driver).
You might ommit personal pronouns, as I said, or use 'it' on the object of the sentence using passive verbs.
Edit: Did you even read what you linked?
> One explanation given for some uses of they referring to a singular antecedent is notional agreement, when the antecedent is seen as semantically plural
F was definitely singular.
> Distributive constructions apply a single idea to multiple members of a group. They are typically marked in English by words like each, every and any.
That is indeed something I often wondered about, sadly that part is inconclusive.
> Referential and non-referential anaphors
I didn't even try to read. That looks like it should be it's own article.
> On the other hand, when the pronoun they was used to refer to known individuals ("referential antecedents, for which the gender was presumably known", e.g my nurse, that truck driver, a runner I knew), reading was slowed when compared with use of a gendered pronoun consistent with the "stereotypic gender" (e.g. he for a specific truck driver).
You might ommit personal pronouns, as I said, or use 'it' on the object of the sentence using passive verbs.
Although you allege ekke's comment was "much better understandable", it commits the same use of they as singular.
> Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing.
"They" cannot possibly be referring to the group---"they" is referring to each person individually. If it's referring to the others as a group, it's not a solution to the puzzle.
And yet, you found it understandable.
> Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing.
"They" cannot possibly be referring to the group---"they" is referring to each person individually. If it's referring to the others as a group, it's not a solution to the puzzle.
And yet, you found it understandable.
"Others" is not singular. "they" is a reference to individuals out of a group. "they each" is a common disambiguation, but it doesn't actually matter who turns the light on. The generic he was also used, anyway. This "they" is commonly used to refer to groups of only males, too, and has nothing to do with gendering.
In contrast, F was really singular.
In contrast, F was really singular.
You seem to be very angry with a feature of English grammar. Using they/them/their is a perfectly reasonable, consistent and well-understood way to refer in the third person to someone of unknown gender.
How would you rewrite the sentence "If the light is on when F gets to the room, they turn the light off, and they increment their counter." without using they?
How would you rewrite the sentence "If the light is on when F gets to the room, they turn the light off, and they increment their counter." without using they?
I am not angry with a feature of the language. I am angry with the people abusing a bug, for lack of a better word, that makes a simple language overly complicated. I am angry, because I didn't understand the whole comment. In my opinion that is not just my fault. It was, in many ways, terribly written. I think a little meta discussion is beneficial. Seeing that it is a question of logic and we are in a logic puzzle thread, I think, you should try to answer your question yourself.
> consistent
If that was a consistent feature, or better to say regular, there would be the -s inflexion on the verb, that the singular third person requires.
> well-understood
What does that even mean? In the referred article, were, as I said, at least two counts against the particular usage in the GP.
> How would you ...
What does it matter? Are you saying there is no other way? Why don't you give it a try yourself, it's not hard. For starters, just try replacing "they" with "F".
> consistent
If that was a consistent feature, or better to say regular, there would be the -s inflexion on the verb, that the singular third person requires.
> well-understood
What does that even mean? In the referred article, were, as I said, at least two counts against the particular usage in the GP.
> How would you ...
What does it matter? Are you saying there is no other way? Why don't you give it a try yourself, it's not hard. For starters, just try replacing "they" with "F".
>What does it matter? Are you saying there is no other way? Why don't you give it a try yourself, it's not hard. For starters, just try replacing "they" with "F".
Lol. It does matter because you are bitching about using they when you don't even say what on earth are we supposed to say instead.
Replace they with the name? "If the light is on when Franklin gets to the room, Franklin turns the light off, and Franklin increments his or her counter." Yeah sounds perfectly natural. Pronouns are for losers.
Lol. It does matter because you are bitching about using they when you don't even say what on earth are we supposed to say instead.
Replace they with the name? "If the light is on when Franklin gets to the room, Franklin turns the light off, and Franklin increments his or her counter." Yeah sounds perfectly natural. Pronouns are for losers.
So, my personal ability to rephrase the sentence is attacked, the pretense that there would be no alternatives is kept and my idea is dismissed as petty. That's just as expected.
Note that the above sentence is written in the objective way that I mentioned before. There is no way a third person singular gendered pronoun could creep in there, even if I was talking about you in the third person.
Unless Franklin was a transfinite gender fluid with multiple personalities, the use of they would be wrong there, according to the article you linked.
Note that the above sentence is written in the objective way that I mentioned before. There is no way a third person singular gendered pronoun could creep in there, even if I was talking about you in the third person.
Unless Franklin was a transfinite gender fluid with multiple personalities, the use of they would be wrong there, according to the article you linked.
Yes, your alternative of simply repeating the noun several times instead of using a pronoun, which you avoid using because you feel its gender neutrality is a tool of the "transfinite gender fluid sjw brigade", despite being in use for 600 years now, is a petty solution indeed.
The first sentence of my last comment was what I had called objective. All the while, going by the repeated mentioning of me, ie. "you", the answer I got seemed much more focused on me. Well, I'm very egoistic, going by my mentioning myself so often here, so I'm flattered by your attention, but I suppose you are missing the point.
Nice talking to you, thanks for the link.
Nice talking to you, thanks for the link.
Good one!
A naive strategy where they never die, and hopefully stay in prison for slightly less than a few billion years:
One prisoner is the light-counter (Mr C). Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing.
Mr C enters the room, if the light is on, remembers it, and turns it off.
When Mr C has entered the room 99 times with light on, he can say 'Yes' and they are safe.
This can be optimized. How?
A naive strategy where they never die, and hopefully stay in prison for slightly less than a few billion years:
One prisoner is the light-counter (Mr C). Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing.
Mr C enters the room, if the light is on, remembers it, and turns it off.
When Mr C has entered the room 99 times with light on, he can say 'Yes' and they are safe.
This can be optimized. How?
You have to be careful, because if the light starts out on, Mr C could be fooled when only 98 other people have entered the room.
This is essentially the same solution I came up with. I'm not sure it needs to be optimized assuming we can set the starting state and the strategy for every prisoner.
Here's a much harder variation. There are three changes:
(1) No prisoner is distinguishable from any other. In other words, they must all have the same strategy.
(2) The prisoners are all given coins, so that they can make random decisions.
(3) The goal is now to find a strategy that will eventually halt with probability 1 (in other words, how long it takes can depend on the coin flips, but any run that takes infinite time must happen only with probability 0). However, the prisoners are not allowed to take chances when answering "yes"; they can only say "yes" if they are certain that every prisoner has visited the room.
It has a very elegant solution.
(1) No prisoner is distinguishable from any other. In other words, they must all have the same strategy.
(2) The prisoners are all given coins, so that they can make random decisions.
(3) The goal is now to find a strategy that will eventually halt with probability 1 (in other words, how long it takes can depend on the coin flips, but any run that takes infinite time must happen only with probability 0). However, the prisoners are not allowed to take chances when answering "yes"; they can only say "yes" if they are certain that every prisoner has visited the room.
It has a very elegant solution.
>The "easiest" solution would simply be to wait a few billion years
Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%.
I know of two legitimate answers to this problem, it took me awhile when I first heard it.
Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%.
I know of two legitimate answers to this problem, it took me awhile when I first heard it.
True. I alluded to that further down, as even with the perfect strategy this means that "it is theoretically possible that the goal state never happens", i.e. the probability that the algorithm will terminate will never be 100% (but it terminates with probability 1).
>Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time.
IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't terminate).
IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't terminate).
I think dsugarman meant "at least once over any FINITE amount of time", in which case each prisoner might visit again an infinite number of times, but it can be arbitrarily many turns in the future.
So, if you wait a finite amount of time (in this case a "few" billion years") it's possible that the visiting condition might not yet be satisfied.
So, if you wait a finite amount of time (in this case a "few" billion years") it's possible that the visiting condition might not yet be satisfied.
So? It doesn't have to be true that each prisoner will be visited within any particular time frame.
The solution only requires that they will eventually be visited; you can keep deferring until they are. There's no specific time frame in which you have to make a guess.
> There's no specific time frame in which you have to make a guess
This is correct.
> The solution only requires that they will eventually be visited; you can keep deferring until they are.
This is false; you can't "keep deferring until everyone is visited" because you have no way of assessing whether that's happened. As a strategy, it is impossible to implement.
This is correct.
> The solution only requires that they will eventually be visited; you can keep deferring until they are.
This is false; you can't "keep deferring until everyone is visited" because you have no way of assessing whether that's happened. As a strategy, it is impossible to implement.
Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.
That is a completely different strategy than "if we wait long enough, it's bound to work". Waiting is worthless, no matter how long you wait.
But under the corrected assumption about the problem, you can reliably know when it is safe to say that all prisoners have been in the room and when you should keep deferring. In the other version of the problem, I agree there's no such guarantee; hence why I bought up the difference.
I like Cheryl's transfinite logic puzzle, which takes logic puzzles to a ridiculous extreme.
http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-ch...
The puzzle is inspired by Cantor's transfinite ordinal numbers, which are pretty cool. You don't need to know anything about transfinite numbers to solve the puzzle, but they are interesting in their own right. The simplified idea is suppose you count 1, 2, 3, ... up to infinity (ω). Everyone knows adding 1 to infinity doesn't get you anywhere, but suppose you can do it and get ω+1, ω+2, ... The limit is 2ω. But then you can go 3ω, 4ω, ... Which obviously :-) gets you to ω*ω = ω^2. Then you can keep going with bigger and bigger infinities. See https://en.wikipedia.org/wiki/Ordinal_number
http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-ch...
The puzzle is inspired by Cantor's transfinite ordinal numbers, which are pretty cool. You don't need to know anything about transfinite numbers to solve the puzzle, but they are interesting in their own right. The simplified idea is suppose you count 1, 2, 3, ... up to infinity (ω). Everyone knows adding 1 to infinity doesn't get you anywhere, but suppose you can do it and get ω+1, ω+2, ... The limit is 2ω. But then you can go 3ω, 4ω, ... Which obviously :-) gets you to ω*ω = ω^2. Then you can keep going with bigger and bigger infinities. See https://en.wikipedia.org/wiki/Ordinal_number
"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-...
https://jeremykun.com/2014/11/18/learning-a-single-variable-...
This is beautiful.
Thank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.
I solved it a little differently than the suggested method.
The suggested solution requires a box that is capable of being locked in both the lid and box by two padlocks. It also requires (Spoiler!) the ring to make two pointless transits, which could be expensive if it was large.
What if, instead, the box was capable of admitting only one padlock? Then Jan would padlock it closed. On receiving the locked box, Maria locks her padlock to Jan's, and returns the box (still locked with Jan's padlock, and not necessarily containing anything.) Then, on receiving the box back from Maria, Jan can form a chain that can be broken by either his padlocks (which he can remove) or by Maria's padlock (which she can remove). Then he can attach the chain to any box. Perhaps he should clip one more of his padlocks only to hers, so she can also select a new box.
Of course, this relies on some properties of padlocks that are not necessarily transferrable to cryptography.
The suggested solution requires a box that is capable of being locked in both the lid and box by two padlocks. It also requires (Spoiler!) the ring to make two pointless transits, which could be expensive if it was large.
What if, instead, the box was capable of admitting only one padlock? Then Jan would padlock it closed. On receiving the locked box, Maria locks her padlock to Jan's, and returns the box (still locked with Jan's padlock, and not necessarily containing anything.) Then, on receiving the box back from Maria, Jan can form a chain that can be broken by either his padlocks (which he can remove) or by Maria's padlock (which she can remove). Then he can attach the chain to any box. Perhaps he should clip one more of his padlocks only to hers, so she can also select a new box.
Of course, this relies on some properties of padlocks that are not necessarily transferrable to cryptography.
> Jan can form a chain that can be broken by either his padlocks or by Maria's padlock
The box cannot be opened by Maria, breaking the rear end of chain wouldn't help at all.
The box cannot be opened by Maria, breaking the rear end of chain wouldn't help at all.
The chain would start:
And the arrangement
Box - J - Lid
Box - J - Lid
|
M
Box - J - M - J - Lid
Box - M - J - Lid
And the arrangement
Box - M - J - Lid
| |
J M
Nicely done. Understood the chaining solution now. One small assumption in that would be that the chain remains taut enough to not leave any gaps to slide the hands into the box (since the lid's hook is no longer in touch with the box).
That puzzle needed more clarification. The solution talks about having two padlocks affixed to the same box, but I can't imagine any kind of box that can have 2 padlocks affixed to it unless the box is specifically designed to allow 2 locks.
A quick search for padlocked box will show many, many such boxes. It seems more common for there to be space for two or more locks, than for just one.
My point is that the puzzle should be updated to inform the reader that designing the right kind of box is a part of the puzzle:
"Jan and Maria each have plenty of padlocks, but none to which the other has a key. Using only the padlocks, keys, and a custom-designed box, how can Jan get the ring safely into Maria’s hands?"
"Jan and Maria each have plenty of padlocks, but none to which the other has a key. Using only the padlocks, keys, and a custom-designed box, how can Jan get the ring safely into Maria’s hands?"
You could always take a one-lock box and build an adapter that accepts two locks, and keeps the box locked if either lock is present.
This just isn't true. I mean, yes they exist, but the norm is overwhelmingly a single latch with room for a single lock.
Without a third party showing sales of padlock boxes with and without space for two or more locks, there's no actual way of being SURE which is more common.
Even if there are ten times as many boxes available that only have space for a single lock, what matters in the case of the puzzle is, a box with space for two or more locks is readily available. Suggesting in the puzzle "by the way the box has space for two locks" really kind of destroys the "puzzle" aspect.
Even if there are ten times as many boxes available that only have space for a single lock, what matters in the case of the puzzle is, a box with space for two or more locks is readily available. Suggesting in the puzzle "by the way the box has space for two locks" really kind of destroys the "puzzle" aspect.
I'm mad at myself for not managing to figure this out myself.
I guess i made more assumptions about the limitations than there were in the description of the problem.
I guess i made more assumptions about the limitations than there were in the description of the problem.
I think you'd enjoy The Code Book by Simon Singh.
> I guess I made more assumptions about the limitations than there were in the description of the problem.
This accounts for some high percentage of the failures in figuring out brain teasers :)
This accounts for some high percentage of the failures in figuring out brain teasers :)
[deleted]
Assuming cryptography exists in Kleptopia, couldn't he use a padlock with a combination and transmit this electronically?
Two points -- one, that's outside of the problem statement, so no, you can't use cryptography. Two, public-key cryptography uses an exact analogy of the physical-world method, so if you have access to a cryptographic solution you've already solved the problem.
Interesting to me that there is an analogy with a 1000 year old puzzle.
https://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_pu...
https://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_pu...
There isn't really an analogy here, it just seems like it.
The apparent similarity between these two is due to there being multiple trips in both -- across the river in one, and through the mail in the other. But the reason for the multiple trips are entirely dissimilar, and so the similarity is purely superficial.
The apparent similarity between these two is due to there being multiple trips in both -- across the river in one, and through the mail in the other. But the reason for the multiple trips are entirely dissimilar, and so the similarity is purely superficial.
My sister's solution: Send the ring in a box with a combination lock ;)
Edit: Ah, charlesdenaul already proposed that. You wouldn't need cryptography, as the problem doesn't state that the postal service also monitors the Internet.
Edit: Ah, charlesdenaul already proposed that. You wouldn't need cryptography, as the problem doesn't state that the postal service also monitors the Internet.
It's a really good metaphor for explaining public key cryptography.
Alternative solution: send her a model of the key to 3d-print
How are you sending the model safely?
After she gets the package. If the post staff just break into your house to take your stuff based on internet communication, they'd find out about your ring the next time one of you mentioned it, among other problems.
I presume email, and that GP misspoke when they said "model" and meant a file that the key could be modeled and printed from. That being said, that solution definitely skirts the intention of the puzzle, but would certainly work given the restrictions the puzzle did list.
model as in 3D model
:). OTOH, as someone interested in high latency communication protocols I wish cryptographers would hesitate to suggest a three round trip protocol at postal latency.
My solution is that Jan should send the ring in a padlocked wooden box with an inner protective but unlocked box and Maria should apply a saw to the outer box.
(To be fair, I can certainly imagine that in Kleptopia they know how to make excellent boxes).
My solution is that Jan should send the ring in a padlocked wooden box with an inner protective but unlocked box and Maria should apply a saw to the outer box.
(To be fair, I can certainly imagine that in Kleptopia they know how to make excellent boxes).
Even simpler: send it in a padlocked cardboard box which Maria can rip open with her hands. Nothing in the problem statement says that the box itself has to be resistant to attack.
I noticed that one proposed solution is pretty pointless: attach a key to the hasp of the first locked box. The key can then be copied ("stolen" in today's copyrights-holder's parlance) by anyone along the mailing route, and the first person to use the key gets the ring.
This, aside from the fact that the key on the hasp is not "inside a padlocked box" ...
This, aside from the fact that the key on the hasp is not "inside a padlocked box" ...
I knew "the" solution was something DH-like, but my solution was:
Maria mails Jan one of her padlocks, and he mails her the ring back in a box that's locked by that padlock.
...I think others are overcomplicating this.
Maria mails Jan one of her padlocks, and he mails her the ring back in a box that's locked by that padlock.
...I think others are overcomplicating this.
> Maria mails Jan one of her padlocks
I think the idea is that that padlock would get stolen unless it would be sent in a padlocked box.
I think the idea is that that padlock would get stolen unless it would be sent in a padlocked box.
Or even better: a thief replaces the padlock with one of his own, then later steals the ring.
What you really need is a trusted "padlock authority" that can verify the authenticity of your padlocks...
What you really need is a trusted "padlock authority" that can verify the authenticity of your padlocks...
I don't know, why would someone steal a padlock unless it was attached to a box? Maybe so, though.
If not steal, can definitely make a copy of the key :)
The wording of the problem is "anything sent through the mail will be stolen unless it is enclosed in a padlocked box".
Jan constructs an enormous box around the entire country of Kleptopia, and places his own padlock on it from the inside. Then he mails the ring with no additional security measures.
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.
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.
Jan takes a normal box and locks it. He declares the space enclosed by the box to be the "outside," and the world to be "inside."
Unfortunately, the mail thieves declare "outside" to be the volume in conformal space on the side of the boundary definition that contains the point at infinity, and "inside" to be the volume that does not, and thus steal the ring.
Those jerks, they're always one step ahead.
Of course the point at infinity had been stolen some time ago, and its whereabouts are currently unknown.
> anything sent through the mail will be stolen unless it
is enclosed in a padlocked box
If someone stole the padlocked box then they would necessarily also steal whatever's inside. Therefore (non-empty) padlocked boxes are safe to mail.
If someone stole the padlocked box then they would necessarily also steal whatever's inside. Therefore (non-empty) padlocked boxes are safe to mail.
Aha!
Then you put a tiny corundum crystal inside a tiny padlocked box, and permanently affix it to the ring. (Or perhaps the ring has a lockable box portion.) Now the ring cannot be stolen without also stealing an object that is inside a padlocked box. Safe to mail.
Then you put a tiny corundum crystal inside a tiny padlocked box, and permanently affix it to the ring. (Or perhaps the ring has a lockable box portion.) Now the ring cannot be stolen without also stealing an object that is inside a padlocked box. Safe to mail.
I collect riddles like these! Here are a few of them.
Numbered Hats
A warden places a hat on the head of each of 100 prisoners, each with a random number from 1 to 100. There may be duplicates. Each prisoner can see everybody's hat but their own. Each prisoner then guesses their own number; if any guess correctly, they all go free. The group may not communicate in any way during the trial, but may strategize beforehand. What strategy has the best chance of success?
Colored Hats
A warden lines up a group of 30 prisoners so they can see everybody in front of them and nobody behind them, then places either a red or a blue hat on each of their heads, randomly. He then goes from the back of the line to the front, telling each prisoner to guess the color of their own hat. Each who guesses correctly is freed. The prisoners cannot see the color of their own hat, and cannot communicate with each other, but can hear each others' guesses and can strategize beforehand. What strategy saves the greatest number of prisoners?
Coins on a Chessboard
A warden takes prisoner A into a room containing a chessboard, on each square of which is a coin randomly showing heads or tails. He then indicates a random square on that board. Prisoner A is given the chance to flip one coin (or none), then taken from the room, after which prisoner B is taken into the room and must say which square the warden indicated. The two prisoners may strategize beforehand, but may not communicate during the trial (except with the single coin flip). What should be their strategy?
Numbered Hats
A warden places a hat on the head of each of 100 prisoners, each with a random number from 1 to 100. There may be duplicates. Each prisoner can see everybody's hat but their own. Each prisoner then guesses their own number; if any guess correctly, they all go free. The group may not communicate in any way during the trial, but may strategize beforehand. What strategy has the best chance of success?
Colored Hats
A warden lines up a group of 30 prisoners so they can see everybody in front of them and nobody behind them, then places either a red or a blue hat on each of their heads, randomly. He then goes from the back of the line to the front, telling each prisoner to guess the color of their own hat. Each who guesses correctly is freed. The prisoners cannot see the color of their own hat, and cannot communicate with each other, but can hear each others' guesses and can strategize beforehand. What strategy saves the greatest number of prisoners?
Coins on a Chessboard
A warden takes prisoner A into a room containing a chessboard, on each square of which is a coin randomly showing heads or tails. He then indicates a random square on that board. Prisoner A is given the chance to flip one coin (or none), then taken from the room, after which prisoner B is taken into the room and must say which square the warden indicated. The two prisoners may strategize beforehand, but may not communicate during the trial (except with the single coin flip). What should be their strategy?
Ah, the Colored Hats is awsome (Haven't tried the other ones, thanks for those)!
It gets even more interesting by using three colors instead of two. The solution stays the same in principle, but [guvaxvat zbqhyb guerr vf n ybg yrff boivbhf guna jbexvat jvgu rira naq bqq.] (ROT13)
EDIT: Happy now? ;P
EDIT: Happy now? ;P
EDIT: Yes :-)
Numbered hats: I'm not sure this is optimal.
When the prisoners are together, they assign each person a unique ID from 1 to 100.
Once the round starts, each looks around and adds up the total on everybody else's hat, mod 100. Suppose you see a total of h (mod 100). Then you should make a guess g = h - your ID (mod 100).
With 1000 repeated experiments of 1000 trials each, this saved the prisoners ~ 630±17 ~= 63±2 percent of the time.
When the prisoners are together, they assign each person a unique ID from 1 to 100.
Once the round starts, each looks around and adds up the total on everybody else's hat, mod 100. Suppose you see a total of h (mod 100). Then you should make a guess g = h - your ID (mod 100).
With 1000 repeated experiments of 1000 trials each, this saved the prisoners ~ 630±17 ~= 63±2 percent of the time.
If each person just guesses a random number you succeed the same amount of the time. You have a 99% chance of guessing wrong. The chance of 100 people guessing wrong is 0.99 ^ 100. So the chance of at least 1 person guessing right is 1 - 0.99 ^ 100, which is 63.4%.
Well then, I guess my strategy accomplishes nothing!
There's a strategy that guarantees success. And you're so very close to it. So close, in fact, that I'm going to guess you've heard this before and just don't fully remember the solution.
[deleted]
Numbered Hats: Are the guesses secret?
Colored Hats:
The first one makes a sacrifice and says the color of the next hat. He has a 0.5 chance. The next person thus has a chance of 1. The third has to make a sacrifice again. Naively that is an average 0.75 chance over all. An exact calculation is too complicated for my taste.
Colored Hats:
The first one makes a sacrifice and says the color of the next hat. He has a 0.5 chance. The next person thus has a chance of 1. The third has to make a sacrifice again. Naively that is an average 0.75 chance over all. An exact calculation is too complicated for my taste.
Numbered hats: yes, they don't hear what the others guess. Of course, they could still "know", if they'd agreed upon guesses beforehand.
Colored hats: true, but you can do better than 75%-ish.
Colored hats: true, but you can do better than 75%-ish.
Can you post the solution to the numbered hats one?
Sure.
Call the sum of all assigned numbers N. No prisoner knows N, but they do know that there are exactly 100 possible last two digits of N, from "00" up to "99". Beforehand, assign a different last digit pair to each prisoner. When the prisoner guesses, he sums everybody else's number, then guesses the number between 1 and 100 that, when added to his partial sum, results in his assigned last two digits.
Call the sum of all assigned numbers N. No prisoner knows N, but they do know that there are exactly 100 possible last two digits of N, from "00" up to "99". Beforehand, assign a different last digit pair to each prisoner. When the prisoner guesses, he sums everybody else's number, then guesses the number between 1 and 100 that, when added to his partial sum, results in his assigned last two digits.
That's much cleaner than I thought it would be. I was convinced that there was a solution that guaranteed success, since each arrangement of numbers could get mapped to a unique guessing strategy, so if you could make it so that exactly one correct guess per arrangement you're golden. I tried working with a N-wide N-dimensional cube, got it working for N=2, and failed at N=3.
This makes sense, though twhb didn't mention any restriction on the numbers you might guess. Thus the first prisoner could just guess on the entire sum they saw, and only two guesses would be needed.
A different solution to the Box in box problem, with less math:
Consider the square of (length + with + height). The sum of the diagonal terms is the square of the distance between opposite corners, the sum of the off diagonal terms equals half the area of the boxes. We can show that both these terms are smaller for the innermost box.
It’s obvious for the diagonal terms, as the opposite corners of a box are the two points of the box that are furthest apart. So the opposite corners of the inner box must be separated by less than the opposite corners of the outer one.
For the cross diagonal terms: take axes that are aligned with the inner box. Consider the parts of the outer box that would be projected on the inner box if you projected either on the x&y, x&z, or y&z planes (i.e. you project on the faces of the inner box). These six pieces of the outer box don’t intersect, and each of them is larger than the face of the inner box on which they project. So this part of the outer box has an area bigger than the total are of the inner box. QED
Consider the square of (length + with + height). The sum of the diagonal terms is the square of the distance between opposite corners, the sum of the off diagonal terms equals half the area of the boxes. We can show that both these terms are smaller for the innermost box.
It’s obvious for the diagonal terms, as the opposite corners of a box are the two points of the box that are furthest apart. So the opposite corners of the inner box must be separated by less than the opposite corners of the outer one.
For the cross diagonal terms: take axes that are aligned with the inner box. Consider the parts of the outer box that would be projected on the inner box if you projected either on the x&y, x&z, or y&z planes (i.e. you project on the faces of the inner box). These six pieces of the outer box don’t intersect, and each of them is larger than the face of the inner box on which they project. So this part of the outer box has an area bigger than the total are of the inner box. QED
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.
Yeah, it's an old chestnut:
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.
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.
I think the puzzle as phrased is slightly incomplete. The stranger must communicate something _new_ each day to make the induction work.
For instance, if the number of blues is 25, and the (merciful) stranger says that the number of blues is not prime every day, no one ever has enough information.
And in fact, even that doesn't seem to be enough. The non-trivial part must be that at least one person knows more than they did before the statement, otherwise a merciful stranger could say 'The number of blues is less than <big number>' each day, where the big number is more than the population.
Unfortunately that stringent of a definition for non-trivial sort of ruins the problem since in the formulation is the idea that at least one person in the village gets (at least) one number closer to knowing the exact number of blues everyday, and as soon as they know the exact number of blues they are eliminated.
For instance, if the number of blues is 25, and the (merciful) stranger says that the number of blues is not prime every day, no one ever has enough information.
And in fact, even that doesn't seem to be enough. The non-trivial part must be that at least one person knows more than they did before the statement, otherwise a merciful stranger could say 'The number of blues is less than <big number>' each day, where the big number is more than the population.
Unfortunately that stringent of a definition for non-trivial sort of ruins the problem since in the formulation is the idea that at least one person in the village gets (at least) one number closer to knowing the exact number of blues everyday, and as soon as they know the exact number of blues they are eliminated.
The clock is certainly necessary. But for information, I think its as easy as "somebody has blue eyes!" said once. If only one person has blue eyes, they see no one else with blue eyes so kill themselves. If two people have blue eyes, they see the other guy and think "maybe its only him". Next day, that guy is still alive; they now know the only remaining blue-eye is themselves; midnight comes and they both suicide. Then nobody else has to - the two guys died on day 2 so only 2 blue-eyes can exist.
And so on.
If two people have blue eyes, "Somebody has blue eyes" is not new information, because everyone has already seen that someone has blue eyes.
It's not new information to either person individually. But while both people already knew it, they didn't know that the other one knew it. That's the new information.
> If two people have blue eyes, "Somebody has blue eyes" is not new information, because everyone has already seen that someone has blue eyes.
The new information in that scenario is that the other guy with blue eyes knows that someone has blue eyes.
The new information in that scenario is that the other guy with blue eyes knows that someone has blue eyes.
If they have seen someone with blue eyes they would already know that.
They know that you know that. That's the new info.
> The non-trivial part must be that at least one person knows more than they did before the statement.
I think that's what they meant by non-trivial. If the stranger tells them something they already know, that doesn't count.
You can assume that an individual person can count the blue dots they see, but they can't count their own dot. If they count 9 dots, then the true number must be either 9 or 10, so they already know the number can't be prime.
I think that's what they meant by non-trivial. If the stranger tells them something they already know, that doesn't count.
You can assume that an individual person can count the blue dots they see, but they can't count their own dot. If they count 9 dots, then the true number must be either 9 or 10, so they already know the number can't be prime.
I agree. If the stranger says something along the lines of, "The number of blue dots is greater than 50." on one day, and on some subsequent day says, "The number of blue dots is not an odd number less than 45." or "The number if blue dots is not a number less than 40 which is divisible by 3.", then no new information will have been conveyed by these latter example statements. I imagine that the stranger could keep stringing them along like this for quite some time, and if multiple statements referring to the same subset were allowed (ex: "The number of blues is not a number which is divisible by 37 which is less than 45." and "The number of blues is not 37.") then the stranger could continue this indefinitely.
The puzzle doesn't involve the stranger saying multiple things. He just shows up, says one thing that everyone already knows to be true (e.g. "At least one of you has blue eyes"), and then leaves forever. And that's enough to cause everyone to (eventually) commit suicide.
The fact that this happens even though it doesn't sound like new information is what makes it an interesting puzzle!
The fact that this happens even though it doesn't sound like new information is what makes it an interesting puzzle!
You are overlooking that all the residents gather together each day. Once a visitor has said something nontrivial, after that the new information each day comes when the residents gather, and discover who did or didn't commit suicide the night before.
Also:
> For instance, if the number of blues is 25, and the (merciful) stranger says that the number of blues is not prime every day, no one ever has enough information.
This is not correct. Saying "the number of blues isn't prime" just once would be sufficient to start the process, as would "there is at least one blue", etc. It doesn't matter that it's not new information to any one villager.
Also:
> For instance, if the number of blues is 25, and the (merciful) stranger says that the number of blues is not prime every day, no one ever has enough information.
This is not correct. Saying "the number of blues isn't prime" just once would be sufficient to start the process, as would "there is at least one blue", etc. It doesn't matter that it's not new information to any one villager.
> This is not correct. Saying "the number of blues isn't prime" just once would be sufficient to start the process, as would "there is at least one blue", etc. It doesn't matter that it's not new information to any one villager.
Sorry, can you explain this part? If there were 10 blues and 10 reds, and the stranger said "there is at least one blue", why would that result in a suicide in any of the dot-town people?
Sorry, can you explain this part? If there were 10 blues and 10 reds, and the stranger said "there is at least one blue", why would that result in a suicide in any of the dot-town people?
That's exactly the puzzle!
If you'd like a hint, imagine that there are only two villagers - you're one of them, and the other one has a blue dot. A visitor tells you both "there is at least one blue". You already knew that, but did he? And what happens the following day, when you see him still alive (or don't)?
If you'd like a hint, imagine that there are only two villagers - you're one of them, and the other one has a blue dot. A visitor tells you both "there is at least one blue". You already knew that, but did he? And what happens the following day, when you see him still alive (or don't)?
[deleted]
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.
There are many things that the visitor can say, and the question is to prove that absolutely anything that the visitor says will result in complete suicide if it provides any information whatsoever about the dots.
That sounds about right. But the problem statement doesn't permit the information to be a lie? The info could be "somebody has blue eyes!"
The comment elaborated on the explanation of "non-trivial" and didn't explicitly say you can't lie. Right? Or am I not hearing this correctly?
Some of the questions incorporate a "new idea" or allow you to change elements. Triangle boxes, prisoners who can make requests, tired tennis players.... I introduced a yellow dot or am I supposed to change the variables to two?
Some of the questions incorporate a "new idea" or allow you to change elements. Triangle boxes, prisoners who can make requests, tired tennis players.... I introduced a yellow dot or am I supposed to change the variables to two?
There's a discrepancy between the number of visible blues and the number given. Say the person is a blue and doesn't know it. They can count b-1 blues on everyone else. Hearing "r reds, b blues, 1 yellow," he knows he must be either blue or yellow. He doesn't know which. Everyone survives.
Edit: had a paren instead of opening quote.
Edit: had a paren instead of opening quote.
I'm also thinking it would need to be at least a couple hundred people to be classified as a town. Which then the odds of someone subconsciously counting a number that high in their head is unlikely.
In a classroom with 30 people right now and I couldn't tell you how many of each gender there are unless I actively try. If that meant certain death, why would I count?
In a classroom with 30 people right now and I couldn't tell you how many of each gender there are unless I actively try. If that meant certain death, why would I count?
You're being downvoted, which is a bit harsh. However, you are thinking about this as a practical problem, when it is actually a mathematics exercise.
The distinction comes naturally to some people, it's a real struggle for others.
The distinction comes naturally to some people, it's a real struggle for others.
I am so bad at this. Also, apparently I don't know the first thing about tennis.
It's not in the same vein, but my favorite puzzle is the Monty Hall Problem. Although as is relentlessly pointed out, it's not actually how "Let's Make A Deal" works.
Monty Hall shows you three doors, two have goats behind them, one has a brand new car. While still closed, you pick a door. After you've picked, Monty opens one of the other two doors to show you a goat, and asks if you want to stay with your choice, or choose the other remaining door. What do you do? Stay? Switch? Or it doesn't matter?
For background and spoiler, https://en.wikipedia.org/wiki/Monty_Hall_problem
Edit: Spelling
Monty Hall shows you three doors, two have goats behind them, one has a brand new car. While still closed, you pick a door. After you've picked, Monty opens one of the other two doors to show you a goat, and asks if you want to stay with your choice, or choose the other remaining door. What do you do? Stay? Switch? Or it doesn't matter?
For background and spoiler, https://en.wikipedia.org/wiki/Monty_Hall_problem
Edit: Spelling
Monty Hall, not Haul.
SPOILER 1 Names in boxes
I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if chance has it that there are two cycles of length 50. Then it seems the chance would be very large that one of the 100 prisoners would en up in the "wrong" loop and thus not find their name?
I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if chance has it that there are two cycles of length 50. Then it seems the chance would be very large that one of the 100 prisoners would en up in the "wrong" loop and thus not find their name?
It's because you start with the box labeled (via the initial random labeling) with your name. If you cycle back to it then it means that you found your name on a piece of paper, since the next box you open is always the one matching the piece of paper in the last box. So it is impossible to start in a cycle that doesn't include your name.
It assumes, they can secretly assign and remember a 100 items random ordering and then execute it perfectly. Further, it assumes they can decide which orientation is the start vs end of the line. Thus, it's not actually possible, but 'in theory' it seems to work.
EX: If I know your going to order based on which side is closet to the entry door nob when the door is closed. Well nothing says they all enter from the same door if it's based on the wall, put the table in the middle of the room.
EX: If I know your going to order based on which side is closet to the entry door nob when the door is closed. Well nothing says they all enter from the same door if it's based on the wall, put the table in the middle of the room.
I agree that the puzzle sort of plays dirty pool here.
The strict requirement is that the boxes are distinguishable. The puzzle implies this by saying they're lined up on a table, but it would be more honest to the reader to say they're numbered 1-100, or somesuch.
The strict requirement is that the boxes are distinguishable. The puzzle implies this by saying they're lined up on a table, but it would be more honest to the reader to say they're numbered 1-100, or somesuch.
I must be missing something. Couldn't one instead assume that they have a private notebook and a pen? And that they can tell left from right? Seems more reasonable.
So you want to add a private notebook that the warden can't read. Further, left vs right does not help if the table is in the middle of a room and people are entering from random doors.
AKA, the solution assumes a lot of information not explicitly part of the original wording.
AKA, the solution assumes a lot of information not explicitly part of the original wording.
Couldn't I start in a "tail" leading to a cycle that doesn't include my name? Suppose my name is "A", and I proceed:
check box A - read name B; check box B - read name C; check box C - read name B
and now I'm in a B-C loop, and will never find my name.
check box A - read name B; check box B - read name C; check box C - read name B
and now I'm in a B-C loop, and will never find my name.
Re-read your scenario -- you have both box A and box C containing name B, but the problem statement says each name appears only once. So you can't get into cycles like this.
Ah, of course! That guarantees there are no "tails"; every name (& box) is part of exactly one cycle. And this is then a property of cycles of permutations generally. Thanks!
No, because in your example both boxes A and C have name B in them. That's against the rules.
No, then "B" would be in two boxes: A and C.
I don't understand: the solution text claims that some permutations are guaranteed to work every time[1]. But you still have to initially land in one of "your" cycles, right?
[1] "If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared."
[1] "If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared."
You always land in "your" cycle, because you start with the box with your name on it.
All sequences of box-opening that use the method described must eventually cycle, because both box-to-name mappings are 1-to-1. Because it's a cycle, the sequence must eventually lead back to the box you started with. Since you start with the box with your name on it, then whatever cycle you landed it, it definitely contains the box with your name on it, because that box is the one that completes the cycle. The only question is whether the cycle is length-50 or less.
All sequences of box-opening that use the method described must eventually cycle, because both box-to-name mappings are 1-to-1. Because it's a cycle, the sequence must eventually lead back to the box you started with. Since you start with the box with your name on it, then whatever cycle you landed it, it definitely contains the box with your name on it, because that box is the one that completes the cycle. The only question is whether the cycle is length-50 or less.
I guess that's what I'm confused about: when we start, the boxes we map our names to have nothing to do with the name in the box. Just because my cycle includes the box I got assigned to, doesn't mean that cycle includes the box with my name inside it. If my name maps to 89, then sure, I accept 89 is a LT-50 cycle, but why does it mean that that cycle actually contains my name (as opposed to the box we assigned me to)?
Think about how you will get back to the box you got assigned to. Like what do you have to see in order to return to box 89, where you started?
Ah, okay, that makes more sense. So the solution is to impose a random ordering on the (1-100 random numbers assigned to the) boxes that ensures you will return to the first one you picked, and that the one that points to your initial pick (or your initial pick itself) has your name in it.
This ordering then partitions the boxes into cycles where each prisoner is in their cycle, and has a low chance of having 50-sized cycles.
Still mesmerized at how the choice of query can improve your chances like that without accumulating information.
This ordering then partitions the boxes into cycles where each prisoner is in their cycle, and has a low chance of having 50-sized cycles.
Still mesmerized at how the choice of query can improve your chances like that without accumulating information.
But why would that matter? You don't know 89 has your name in it, because the numbers were randomly assigned to random people in the first place. You would just draw the name associated with box 89, which is not necessarily your name.
Whatever box you open, you take the name inside and go to the number you associated with that name. So when you end up at box 89, the last box you opened must have had your name inside. So you will have found your name, provided you got there in under 50 steps.
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 does is make it so each individual failure mode is much more likely to overlap with each other failure mode. Correlating the performance of individuals when you have a one fail all fail scenario is a common solution to this type of problem.
What this protocol does is make it so each individual failure mode is much more likely to overlap with each other failure mode. Correlating the performance of individuals when you have a one fail all fail scenario is a common solution to this type of problem.
You are right, but we can also agree on a common query sequence in advance that doesn't use the 'results' of the queries. What about using what we find makes this so much more efficient?
You need to use the result of the query to place yourself in the right cycle (in this case by starting with the box matching your name).
Ah right, that's clever. Thanks for the explanation!
I coded a simulation here if that helps: https://gist.github.com/bjornedstrom/971574557b6f3179db08350...
I also coded a simulation, mine is in js: https://jsfiddle.net/a3ch3s5h/
I only run once, you'll have to run it a few times to get a positive result.
The output is displayed in the js console (F12 on most browsers).
Edit: Something interesting I derived from the solution is that by allowing the first prisoner to reset the experiment if he fails or don't like the result, they get a 100% success rate. The first prisoner just need to wait for an arrangement which place him in a 50 length cycle (which means no other cycle can be of length > 50).
I only run once, you'll have to run it a few times to get a positive result.
The output is displayed in the js console (F12 on most browsers).
Edit: Something interesting I derived from the solution is that by allowing the first prisoner to reset the experiment if he fails or don't like the result, they get a 100% success rate. The first prisoner just need to wait for an arrangement which place him in a 50 length cycle (which means no other cycle can be of length > 50).
The first two times I ran it I got 0.298 and 0.286. Out of 20 attempts 5 were below 30%.
1000 is a pretty small number of trials. Also note the docs on random.shuffle:
Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.[1]
I don't know if we have any reason to believe that the small subset of all permutations that this library can generate is unbiased in terms of the size of the cycles.
https://docs.python.org/2/library/random.html#random.shuffle
Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.[1]
I don't know if we have any reason to believe that the small subset of all permutations that this library can generate is unbiased in terms of the size of the cycles.
https://docs.python.org/2/library/random.html#random.shuffle
Minute Physics [1] did a video on the puzzle [2] and the solution [3].
[1] https://www.youtube.com/user/minutephysics/videos
[2] https://www.youtube.com/watch?v=eivGlBKlK6M
[3] https://www.youtube.com/watch?v=C5-I0bAuEUE
[1] https://www.youtube.com/user/minutephysics/videos
[2] https://www.youtube.com/watch?v=eivGlBKlK6M
[3] https://www.youtube.com/watch?v=C5-I0bAuEUE
I don't understand the answer at all. Are they suggesting that the prisoners have somehow labeled the boxes? Or do they agree to assign names to the boxes via some other way - like make an alphabetic list of prisoners and assume that is the order of the "names on the boxes"? I suppose I just answered my own question, but I'm still not sure ;-)
One assumption not explicitly explained is that the prisoners can identify the boxes by their order, since they are arranged in a line. So, the prisoners first agree among themselves that box number x should correspond to which prisoner, and vice versa. So now, each box contains a name, which points to another box at a certain position, which contains another name, ad infinitum, until the prisoner finds his name. It is guaranteed that he will, because of the relationship between permutations and cycles.
It is interesting that this question is regarded as the most math intensive. I myself was spoiled the solution a few years ago, but I have the impression that the challenge is in observing the correct algorithm rather than calculating the probability. Maybe the author felt that one needs mathematical insights in order to see the solution out of the blue.
It is interesting that this question is regarded as the most math intensive. I myself was spoiled the solution a few years ago, but I have the impression that the challenge is in observing the correct algorithm rather than calculating the probability. Maybe the author felt that one needs mathematical insights in order to see the solution out of the blue.
>I have the impression that the challenge is in observing the correct algorithm rather than calculating the probability
I've got a stats PhD and I guessed the solution but couldn't calculate the probability of having a max cycle length of 50 or less. To be fair, the calculation isn't hard once you see it, but it's not trivial either.
The 30% figure threw me since I know the probability of a random permutation having a fixed point is 1/e (just over 30%), so I went looking for ways to link the cycle length to the Poisson distribution.
I've got a stats PhD and I guessed the solution but couldn't calculate the probability of having a max cycle length of 50 or less. To be fair, the calculation isn't hard once you see it, but it's not trivial either.
The 30% figure threw me since I know the probability of a random permutation having a fixed point is 1/e (just over 30%), so I went looking for ways to link the cycle length to the Poisson distribution.
Yes, not everyone knows that permutations decompose uniquely as products of disjoint cycles.
Every prisoner assigns every box a random name from the list. Boxes cannot be modified in any way, so every prisoner has to do it on their own. The (unexplained) assumption here is that each prisoner can do that somehow, either in their head or on a piece of paper. It doesn't matter that every prisoner has their own unique assignment of names to boxes.
The crucial part here is that it's not guaranteed to work - but it gives prisoners 30% chance to survive, as opposed to some infinitesimally small number if each picks 50 boxes on random.
The crucial part here is that it's not guaranteed to work - but it gives prisoners 30% chance to survive, as opposed to some infinitesimally small number if each picks 50 boxes on random.
If each prisoner randomly labels the boxes in their own (presumably independent) manner, then this strategy fails miserably. In fact, it's equivalent to each prisoner choosing 50 random (unique) boxes.
The solution specifies that "the prisoners must first agree on a random labeling of the boxes by their own names." This is necessary.
The solution specifies that "the prisoners must first agree on a random labeling of the boxes by their own names." This is necessary.
If each prisoner has their own ordering, it's exceedingly likely that one of those orderings will have a 51-cycle.
This strategy only works with one common dictionary. You have the same individual odds, but you've linked each person: each member of a cycle succeeds or fails together.
If it wasn't decided beforehand, you could just make up the ordering as you go. This gives exactly the same odds as random selection.
This strategy only works with one common dictionary. You have the same individual odds, but you've linked each person: each member of a cycle succeeds or fails together.
If it wasn't decided beforehand, you could just make up the ordering as you go. This gives exactly the same odds as random selection.
Yeah, they memorize their own random ordering. Alphabetic is risky because the warden might guess that strategy and purposefully set up the boxes so it doesn't work.
[deleted]
[deleted]
Peter Winkler's books of mathematical puzzles ("Mathematical Puzzles" and "Mathematical Mind-Benders") are top-notch and highly recommended. You will learn something there even if you've read dozens of puzzle books before.
Some of these are poorly worded:
* Kleptopia is ambiguous about what gets stolen, and what toplogy the boxes/padlocks must have for the solution.
* The "clever" solution to Unwanted Expansion isn't a complete proof, unless you add some complicated reasoning or use the non-clever proof, but if you do that, you don't need the "clever" proof at all.
* The Wimbledon puzzle doesn't explain the scoring rules of tennis :(
* Kleptopia is ambiguous about what gets stolen, and what toplogy the boxes/padlocks must have for the solution.
* The "clever" solution to Unwanted Expansion isn't a complete proof, unless you add some complicated reasoning or use the non-clever proof, but if you do that, you don't need the "clever" proof at all.
* The Wimbledon puzzle doesn't explain the scoring rules of tennis :(
the clever solution to "unwanted expansion" only uses the fact that addition and multiplication of two positive integers a, b > 1 always gives an answer that is greater than both a and b, therefore if the expansion never terminates and all your variables are 2, the overall result will be infinite. since expansion doesn't change a result, the pre-expansion evaluation should also be infinite; since it is not, the expansion terminates.
I think there's a simpler solution to boxes in boxes. Assume that the outer box is axis-aligned. Project both boxes onto the X axis, so they become one-dimensional. It's easy to check that the "projected perimeter" of the inner box is smaller. Repeat for axes Y and Z. From that and the triangle inequality, the result follows.
Can you expand on this last step? it's not obvious to me what you're applying the triangle inequality to and why it gives the desired result.
The length of a line segment can't be greater than the sum of its projections onto all three axes. Therefore the "perimeter" of the inner box can't be greater than the sum of its projections. But that sum is bounded from above by the "perimeter" of the outer box (which is equal to the sum of its own projections, because the outer box is axis-aligned).
I'm having trouble with your "therefore" conclusion. The projection of the perimeter of the inner box could easily be shorter than the sum of the lengths of the projections of each edge. It seems like you need a less obvious (to me, anyway) statement about the projection of a collection of lines.
By projected perimeter I mean the sum of lengths of projections of all edges. I'm not canceling them out or anything. Think of the box as a graph, its projection is another graph that happens to lie on a straight line, but we can measure the sum of its edges regardless.
It's not completely obvious why the projected perimeter of the inner box is bounded by the projected perimeter of the outer box, but it's a statement about one-dimensional segments that's easy enough to check.
It's not completely obvious why the projected perimeter of the inner box is bounded by the projected perimeter of the outer box, but it's a statement about one-dimensional segments that's easy enough to check.
> Therefore the "perimeter" of the inner box can't be greater than the sum of its projections.
What definition of "perimeter" are you using here?
What definition of "perimeter" are you using here?
See response to pfedak.
I'm still not quite following. Is the "perimeter" here the sum of the lengths of projections of the edges, then how is that different from "the sum of its projections"?
Anyway if you define "perimeter" that way then for the outer box the "perimeter" is in fact 4 * (a+b+c), where a, b, c are the dimensions of the box. I also agree that for the inner box the "perimeter" is at least 4 * (a'+b'+c'), by the triangle inequality.
What is not at all clear to me is why the "perimeter" of the inner box is no larger than the "perimeter" of the outer box in this setup. You say it's easy to check, but it doesn't seem very obvious to me.
Anyway if you define "perimeter" that way then for the outer box the "perimeter" is in fact 4 * (a+b+c), where a, b, c are the dimensions of the box. I also agree that for the inner box the "perimeter" is at least 4 * (a'+b'+c'), by the triangle inequality.
What is not at all clear to me is why the "perimeter" of the inner box is no larger than the "perimeter" of the outer box in this setup. You say it's easy to check, but it doesn't seem very obvious to me.
Let's say the projections of the inner box's edges onto the X axis have three distinct lengths a,b,c (all positive). Also let's say the distance between the leftmost and rightmost projected vertices is d. The nontrivial fact is that d=a+b+c, and not say a-b+c. That leads to the desired inequality, I think.
Ah, I see. Yes, I agree that given that fact you get the desired inequality.
But this fact is, as you say, nontrivial. It's certainly false for various non-box-like shapes afaict, so there's something special to boxes that needs proving here.
But this fact is, as you say, nontrivial. It's certainly false for various non-box-like shapes afaict, so there's something special to boxes that needs proving here.
Just note that all combinations ±a±b±c can be realized by paths on the box.
I'm sorry, I see now that my original comment glossed over tons of stuff that was clear only to me. Instead of saying "easy to check" I should've posted my napkin sketch with the easy check.
Anyway, my solution is still simpler and more natural than the one in that pdf :-)
I'm sorry, I see now that my original comment glossed over tons of stuff that was clear only to me. Instead of saying "easy to check" I should've posted my napkin sketch with the easy check.
Anyway, my solution is still simpler and more natural than the one in that pdf :-)
<spoiler>For #1, I didn't hear correctly because I didn't understand that the clearly insane and cruel warden would let the prisoners label the boxes before hand :-/
You don't actually need to label them you just need all the prisoners to be able to memorize which name is associated with which box, Alice's box is the first on the left, Bob's the second etc... Then when Zach. Z. Z. Vanderwall opens "his box" and finds the name Bob he follows procedure.
You need a minimal perfect hash function but it's a thing that can be done, especially because prisoners in these sort of conundrums always have fantastic memories and mental math facility.
https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_...
You need a minimal perfect hash function but it's a thing that can be done, especially because prisoners in these sort of conundrums always have fantastic memories and mental math facility.
https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_...
>fantastic memories and mental math facility.
If you assume the axiom of choice and allow them to memorize arbitrary uncountable elements, you can get more interesting puzzles (and also go insane).
https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-ch...
If you assume the axiom of choice and allow them to memorize arbitrary uncountable elements, you can get more interesting puzzles (and also go insane).
https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-ch...
Doh! Of course. But now the recommended solution is really overkill ...
Still, I didn't hear correctly either: I thought there would be 100 identical boxes lined up in a row by the warden's assistant.
The solution still works. The prisoners have agreed on a mapping between their names and the order of the 100 boxes. That mapping is what they rely on to inspect the boxes, the boxes don't need actual labels.
The problem statement makes it clear they can communicate prior to starting the game.
The problem statement makes it clear they can communicate prior to starting the game.
And they all do what you, The Nerd, say. Prisoners are known to be well-behaved and respect Nerds! /s
From my experience as a nerd playing werewolf with non-nerds I'm afraid you're right.
Me: "Here's a plan that will defeat the werewolf in any case, even if I am the werewolf"
Them: "That sounds complicated, therefore suspicious, let's hang him"
Me: "Here's a plan that will defeat the werewolf in any case, even if I am the werewolf"
Them: "That sounds complicated, therefore suspicious, let's hang him"
I'm have some trouble understanding the solution to the 3 natives puzzle. Is the objective to find the road guarded by the truth teller?
SPOILER BELOW
The solution suggests
Q1) --> A
Q1): Is B least likely to tell the truth out of B and C?
If yes ask Q2 --> B, If no, ask Q2 --> C
Q2): If I were to ask you does your road lead to the truth village, would you say yes?
If yes, you know where the truth village is. If no, you would know the person you are questioning in the liar, but both of the other two could be the truth teller or the random answerer?
For example, if A is the random answerer and randomly selects 'truth', or if A is the truth teller, they will both direct you to the liar for Q2.
Let me know where I've gone wrong.
SPOILER BELOW
The solution suggests
Q1) --> A
Q1): Is B least likely to tell the truth out of B and C?
If yes ask Q2 --> B, If no, ask Q2 --> C
Q2): If I were to ask you does your road lead to the truth village, would you say yes?
If yes, you know where the truth village is. If no, you would know the person you are questioning in the liar, but both of the other two could be the truth teller or the random answerer?
For example, if A is the random answerer and randomly selects 'truth', or if A is the truth teller, they will both direct you to the liar for Q2.
Let me know where I've gone wrong.
There are only two roads and one village, and the problem is to find out which of the roads lead to the village. Forget about "guarding" and the "truth village".
If you ignore the random answerer for a second, then you ask "if I were to ask you if this road leads to the village, what would you say?". Let's call this the original question. The answer will be trustable, because the truth teller will tell the truth, and the liar will lie about a lie, making the result the truth as well.
Now we introduce a new question, and a third answerer -- random. Since we know we can solve the problem with only the original question and original two natives, the goal of this question is just to eliminate the random answerer.
The solution given in the article uses this new question in two ways. One, by asking it of one native and not ever asking that native the original question, if the native we happen to ask is the random answerer, we know we won't ask the original question of that answerer, so what they answer doesn't matter -- either way, we'll end up with the liar or truth teller to ask the original question of.
So we only need to design the new question assuming the one we ask it of is not the random answerer. So now we're back to asking a "double question", resulting in a truth about a truth or a lie about a lie. You ask the question you stated, knowing that the native identified as "least likely to tell the truth" will never be the random one, due to truth-about-truth, lie-about-lie, or due to the random answerer being neither B nor C.
If you ignore the random answerer for a second, then you ask "if I were to ask you if this road leads to the village, what would you say?". Let's call this the original question. The answer will be trustable, because the truth teller will tell the truth, and the liar will lie about a lie, making the result the truth as well.
Now we introduce a new question, and a third answerer -- random. Since we know we can solve the problem with only the original question and original two natives, the goal of this question is just to eliminate the random answerer.
The solution given in the article uses this new question in two ways. One, by asking it of one native and not ever asking that native the original question, if the native we happen to ask is the random answerer, we know we won't ask the original question of that answerer, so what they answer doesn't matter -- either way, we'll end up with the liar or truth teller to ask the original question of.
So we only need to design the new question assuming the one we ask it of is not the random answerer. So now we're back to asking a "double question", resulting in a truth about a truth or a lie about a lie. You ask the question you stated, knowing that the native identified as "least likely to tell the truth" will never be the random one, due to truth-about-truth, lie-about-lie, or due to the random answerer being neither B nor C.
Ah ok, if there are 2 roads and 3 people then the question makes complete sense.
I have always been a fan of the Pirate game puzzle. https://omohundro.files.wordpress.com/2009/03/stewart99_a_pu...
[deleted]
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 square of interest the master chose by inspecting the state of the board. There is a strategy that is guaranteed to work for all possible configurations of the board.
I think you're referring to this puzzle: http://datagenetics.com/blog/december12014/index.html
The version you gave is missing information and so can't be solved as stated.
The version you gave is missing information and so can't be solved as stated.
Thank you for posting this. I read the parent several times trying to figure out if they were mistaken or I was dense.
I had to read that like 11 times before I started to get the underlying principle. That's amazing.
In a very similar vein, try this one: https://youtu.be/N5vJSNXPEwA
Either I'm somehow missing some critical piece of this puzzle or your description is. The master could pick a square at random, leaving you with a board (and likelihood of success) that is still completely random.
Are you supposed to be collaborating with the "master"?
Are you supposed to be collaborating with the "master"?
[deleted]
Of course a few of these mathematical puzzles assume that the human beings involved are all robotic, and capable of remembering a randomly ordered list 100 long. The blue dot red dot problem being the worst offender because the theorem doesn't hold up of you assume anyone in the village has the wrong internal state.
Ah. I hate these kind of puzzles!
A short collection of similar puzzles that have been shared with me over the years: https://quaxio.com/some_math_puzzles/
[deleted]
#2 is super interesting! I wonder if it generalizes to higher dimensions.
I don't quite follow the solution, can anyone explain a bit more? What's the motivation for considering large epsilon?
The rigorous version would be:
0 < (Vol(Bε) - Vol(Aε))/ε² = ((a+b+c) - (a'+b'+c'))π + 2((ab + ac + bc) - (a'b' + a'c' + b'c'))/ε + (abc - a'b'c')/ε²
The limit for ε to infinity must be >= 0 and is ((a+b+c) - (a'+b'+c'))π, therefore a+b+c >= a'+b'+c'.
"large epsilon" is a standard way to express "consider the asymptotic behavior for epsilon to infinity and you will see what I mean".
0 < (Vol(Bε) - Vol(Aε))/ε² = ((a+b+c) - (a'+b'+c'))π + 2((ab + ac + bc) - (a'b' + a'c' + b'c'))/ε + (abc - a'b'c')/ε²
The limit for ε to infinity must be >= 0 and is ((a+b+c) - (a'+b'+c'))π, therefore a+b+c >= a'+b'+c'.
"large epsilon" is a standard way to express "consider the asymptotic behavior for epsilon to infinity and you will see what I mean".
Thanks, I get that it means asymptotic behavior - that's the thing I don't get the motivation for.
I think the intuition is that we want to focus on the edges of the box (where the lengths sum together like the answer we're looking for), not the volume (where the lengths multiply together and cause problems). So we expand the edges until they completely dominate the equation.
[deleted]
The tennis was was so straightforward I was thinking it must be a trick, but it was that simple.
[deleted]
Title gore
Here's another one, similiar to the first one (Names in Boxes). Apologies for any incorrections in advance.
There are 100 prisoners. At random times one prisoner is chosen uniformly at random and led into a room with a single lamp. The prisoner can choose to switch it on or off or leave it as the last visiting prisoner left it. Apart from the state of the lamp he must leave the room unchanged.
After visiting the room, each prisoner is asked if every prisoner has visited the room by now. If he answers 'Yes' and indeed everyone has been to the room at least once, then everybody is freed immediately. Otherwise they are all executed ;) He can answer 'I don't know' without any consequences.
Apart from the lamp being on or off the prisoners have no way of communication at all, but of course as is customary in such puzzles they can plot a strategy in advance and everybody is a perfect logician.
So, to clarify: The goal is for one prisoner to be 100% sure that everybody has been to the room at least once. The "easiest" solution would simply be to wait a few billion years (it's an abstract puzzle, they are all immortal anyways ;). But of course there is a more elegant solution that terminates earlier.
Also, as the time for a visit is chosen at random a prisoner has no way of knowing who the previous person in the room was. It might just as well have been himself!
As there is some randomness involved, it is theoretically possible that the goal state never happens. Just assume that in the limit everybody will have visited the room infinitely often ;)
In other words: Implement synchronization between 100 threads with only one bit of shared memory and completely random scheduling.