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.
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.
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.
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.
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.
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.
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.
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.
"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.
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?
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".
>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.
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.
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.
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 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.
>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.
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).
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.
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.
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.
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.
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
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.
Jan can open his padlock, releasing hers, and transform this to:
Box - J - M - J - Lid
Which Maria can open. An optimization could be:
Box - M - J - Lid
This is available if Maria could fit her padlock through the port in the box simultaneously with Jan's there, and send that back so Jan could remove his initial box padlock.
And the arrangement
Box - M - J - Lid
| |
J M
Would let either start a new box, using the J - M - J or M - J - M chaining as needed.
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.
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?"
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.
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.
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.
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.
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.
:). 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).
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" ...
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.
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.
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?
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)
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%.
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.
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.
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
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.
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.
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.
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.
> 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 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!
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.
> 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?
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)?
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.
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?
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.
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?
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?
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.
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.
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.
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!
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."
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.
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)?
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.
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.
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?
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).
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.
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.
>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.
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.
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.
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.
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.
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.
* 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.
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.
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.
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.
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 :-)
<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.
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).
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.
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.
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.
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.
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"?
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.
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.
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.