Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
math.dartmouth.edu
math.dartmouth.edu
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.
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.
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).
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.
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.
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?
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.
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.
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.
Who is they???
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.
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?
> 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".
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.
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.
Nice talking to you, thanks for the link.
> 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.
In contrast, F was really singular.
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.
(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.
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
https://jeremykun.com/2014/11/18/learning-a-single-variable-...
I guess i made more assumptions about the limitations than there were in the description of the problem.
I feel like there is some sort of lesson, here.
This accounts for some high percentage of the failures in figuring out brain teasers :)
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.
I think the idea is that that padlock would get stolen unless it would be sent 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.
If someone stole the padlocked box then they would necessarily also steal whatever's inside. Therefore (non-empty) padlocked boxes are 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.
What you really need is a trusted "padlock authority" that can verify the authenticity of your padlocks...
https://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_pu...
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.
Jan will get the bus.
This, aside from the fact that the key on the hasp is not "inside a padlocked box" ...
Another alternate solution was a bummer..
> Win at Wimbleton > 9999-9997 : Roger was wearing himself out
I mean, seriously?
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).
"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?"
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.
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 box cannot be opened by Maria, breaking the rear end of chain wouldn't help at all.
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
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.
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?
EDIT: Happy now? ;P
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: true, but you can do better than 75%-ish.
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.
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.
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
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?
Edit: had a paren instead of opening quote.
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?
The distinction comes naturally to some people, it's a real struggle for others.
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.
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 new information in that scenario is that the other guy with blue eyes knows that someone has blue eyes.
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.
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.
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)?
The fact that this happens even though it doesn't sound like new information is what makes it an interesting puzzle!
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
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?
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.
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.
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.
AKA, the solution assumes a lot of information not explicitly part of the original wording.
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.
[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."
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.
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.
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 solution specifies that "the prisoners must first agree on a random labeling of the boxes by their own names." This is necessary.
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.
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'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.
[1] https://www.youtube.com/user/minutephysics/videos
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
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).
* 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 :(
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.
What definition of "perimeter" are you using here?
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.
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.
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 :-)
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_...
The problem statement makes it clear they can communicate prior to starting the game.
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"
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...
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.
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.
Are you supposed to be collaborating with the "master"?
The version you gave is missing information and so can't be solved as stated.
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".