These two are both via my nephew. They were part of what was essentially a "Puzzler's Christmas" in our family.
In the first one, do you want the number of drops or the number of eggs? (Given that an egg could survive multiple drops).
I think that you only get the two eggs; if you break the second one without coming up with an answer you're out of luck. (The number to beat here would be n drops, where n is the highest safe height - that's what it would take to drop it from the second story, then the third, etc. until the egg breaks. - this is assuming US style numbering where story 1 is the ground floor.)
The number of drops. The number of eggs is fixed at two. You can only have two unsuccessful drops and you're done.
For the second one, once an econobot finds his number, does he take it away with him, leaving 99 remaining briefcases? Or is the scenario more like:
Empty room with 100 briefcases. An econobot enters, looks in one of the cases, then leaves. Another (or the same) econobot enters, looks in one of the cases, then leaves. Iterate until all the econobots have run out of goes, or have found their numbers.
Yes, use 1 as the ground floor (but you actually get the same answer for the other system).
First pass at an egg-drop procedure: Take the first egg to the third floor, drop it - if it breaks, drop the second egg from the second floor (if that also breaks, then you know your egg is safe only to the first floor, that is, not at all); if not, move to the fifth floor and repeat. This gets you the answer in (n/2) + 1 drops.
5: Papers stay in the suitcase*. And each econobot looks in 50 (actually if he finds his own he does not need to look in more since the question is only "did he find his own number?").
*If the papers were removed the strategy being looked for would not work (which is a hint). Gonna think about if that might work as well via some different strategy.
I feel like that asterisk is pointing at me.
Warmup: I think it's fairly easy to bring n down to a maximum of 19. You drop egg 1 from the tenth floor. If it survives, drop it from the 20th. If it survives, the 30th and so on until it breaks or you reach the 90th floor. When it breaks, go back to the last safe drop height and drop the second egg from the floor above that one. The most you'll ever have to do is 19 drops - if the max height is 100 floors, egg 1 will drop from (10, 20, 30, 40, 50, 60, 70, 80, 90) and be retired safe, and egg 2 will drop from (91, 92, 93, 94, 95, 96, 97, 98, 99) safely, and then drop from 100 and break.
10: More teo*, but probably a bit.
*And I'm pointing with him, not at him.
For the egg one, are you optimizing for the worst case? That is, figure out the scheme under which the maximum number of drops is lowest, even if other methods might be faster in most cases?
11: Yep. That is usually the first waystation to the answer that folks get to in my small experience of the problem. However, 7.parenthetical would not be true in that case.
11 can be improved slightly, I think, in the degenerate case of "the egg can survived being dropped from a 100 story building" -- you drop from the 95th floor after the 90th, and it reduces the maximum number of required drops to 16, right?
10, 12: Actually, I found it interesting to examine at the broad range of "logic puzzle assumptions" it requires to distill it, and even then...
And if someone brings a lateral-thinking problem mindset to a logic puzzle, sparks tend to fly.
16: What if, say, 93 was the actual answer?
I don't think that generalizes if it breaks on, e.g., the 56th floor, though.
18: Then you've wasted a drop and are done at 14 drops, thus my question about whether you were attempting to reduce the worst case.
So instead we can go to (for example) 17, then 33, then 48, then 62, 75, 87, 98 and drop from there for egg 1. That will make for a maximum of 17 or maybe 16 drops. This can probably be better optimized.
17.2: I was surprised by the bifurcation in the commentariat the last time we did one of these. Clearly there are those of us who were raised on silly logic puzzles (or, alternatively, have math degrees) and those who weren't.
Actually 18 in that case if 89th floor). Bu tit is an improvement over 19.
19: no, it doesn't. But in that case my original method gets you there in 12 drops anyway. (10, 20, 30, 40, 50, 60B) (51, 52, 53, 54, 55, 56B). Only if the first egg survives 90 do you get to halve the search space from 10 to 5 by dropping at 95, because you effectively have one egg in hand. Any other decile, you've found the target decile at the cost of one egg.
24-> 16
And I think Tom is right on 17 drops in 22. But you can do better.
You also get the same answer for the Empire State Building.
15, 29, 42, 53, 63, 72, 80, 87, 93, 96, 98, 100. Max 14 drops.
14, 27, 39, 50, 59, 67, 74, 80, 85, 89, 92... nope. At least without further cleverness.
"You" in 27 is a referent to the imaginary egg dropper, not "you" as in Tom or other solvers.
29: I think that takes 15 drops, but it is essentially the right answer. (You can ge tit to 14.)
ESB is 103 stories for those not feeling like looking it up.
Young Gauss would have gotten it.
31: 15 smash. (1)
2-13, no smash. (2-13)
14 - smash (or no smash) (14)
14 drops gets you up to 104 stories (I thought ESB was 102).
25: Ah. Eggs dropped from waist height, so you need to test 1....
37 -> 35. Constraint added belatedly. But you have the scheme.
35: And I think 28th, 41st floors etc. would require 15 drops in the scheme in 29 even without the "waist height" dodge.
For the main event: what about the very simple case of 2 economists, 2 briefcases, one look each? There's no strategy to guarantee success here, and no strategy that has an expected payoff better than 50%. Either you both look in the same one (in which case exactly one of you wins) or you each look in different ones (in 50% of cases you both win, in 50% neither win).
Thing is I remember that LB and I were dead certain that the answer to the dwarfs-and-hats puzzle was the same, and we were both wrong. So I will assume that the answer to the briefcases one is "modular arithmetic" too.
40: Yes, not a very illuminating boundary case. However, it does fit the general pattern of a bet at odds of n-to-1 at least breaking even.
Nope. No modulo was harmed in the making of the briefcase problem.
Seems like looking at the case of 4 economists (or even 3, although the "50%" thing probably makes a difference) might be more useful. I don't have any immediate suggestions on strategy, though.
I feel like ajay must have the right asymptotics (~ sqrt(n_floors)), even if the precise number can be optimized a little bit. Is that right?
45 was my thinking as well (k'th root for the general case of k eggs).
45, 46: That gives a good result, but actually Tom's scheme gets a better one. Basically find the smallest n for which the sum of 1 to n is greater than the number of floors. And then drop pattern is n, 2n-1, 3n-2 ...
Basically find the smallest n for which the sum of 1 to n is greater than the number of floors.
That's ~ sqrt(number of floors).
46: Had not thought about generalizing for n eggs. I assume there is some generalization of the decreasing interval pattern that would apply.
40 - Having E1 and E2 both look in B1 is a guaranteed loser, right? All of E1...En need to find their number, so E1 needs to look in the briefcase E2 doesn't look in. Solving this so that each econobot has a chance of success is simple (En starts with Bn and checks the next 49... using modulo arithmetic), but that doesn't seem to get you to a better place than each econobot having a 1/2 chance of success, which is a sucker bet.
49: "~" doing a lot of work. For 100 floors it is 14. (14*15)/2 = 105.
51: Ah yeah, it's only a 1/4th chance of them winning for the n=2 case isn't it ...
I actually found it easier to work with the full 100 and 50 briefcases in this problem.
Thinking about the briefcases.
First thing I'm sure of: Econobot 1 is guessing at random, and can't do better than 50/50 odds.
Second thing I'm pretty sure of: Even without any communication, for purposes of strategy, all econobots can assume that every prior econobot guessed right. As soon as an econobot guesses wrong, the game effectively ends and no subsequent choices have consequences, so all meaningful choices are informed by the knowledge that every prior guess was correct.
That gets me through the first two guesses with marginally better odds than the 1/4 you'd get for two random picks: Econobot 1 opens 1-50; Econobot 2 assumes Econobot 1 was successful, which means that Econobot 2s odds are slightly better if she picks 51-100. There are only 99 briefcases her number could be in, and 50 of them are between 51 and 100 -- instead of 50/100, her odds are 50/99. (This is sort of related to the Monty Hall problem, isn't it?)
I can't figure out how the next econobot can build on this, but at least the next pair (and each subsequent pair) can do the same thing -- one takes a random draw, and the other gets the same slightly improved odds by drawing from the other half.
54: Yes. You lose half right off the bat.
51: Ah yeah, it's only a 1/4th chance of them winning for the n=2 case isn't it ...
1/2, in that they choose either E1->B1 or E1->B2. If we expand to 4, there are 24 possible cases. Given the case of E1->{B1,B2}, E2->{B2,B3}, E3->{B3, B4}, E4->{B4,B1}, you end up with the following possible success states:
1234
4123
Which 1/12 odds (even worse than having them just choose randomly), suggesting that my naive mechanism isn't very good.
54 - 54 is helpful. Okay, the toy case with 4 econobots is instructive here. E1->{B1, B2}, which (assuming success) gets you to a world in which there are only 10 choices, so E2->{B3, B4) (which has a 6/10 chance of success), which reduces the search space to 6.
Yeah, as I work it out with N=4, you can get 1/9 odds of success: 1/2 * 2/3 * 1/2 * 2/3.
I got 1/8, I think:
E1->{B1, B2} (1/2)
E2->{B3, B4} (7/10)
E3->{B1, B3} (4/7)
E4->{B2, B4} (3/4)
Successful outcomes are:
3124
3142
2134
That 100-to-1 payoff for the N=100 case doesn't look great.
Nope, I did something wrong there, because 2134 is a failure condition. Back to work with me!
Yeah, I'm not understanding your odds in 59.
49: Basically find the smallest n for which the sum of 1 to n is greater than the number of floors.
That's ~ sqrt(number of floors).
I think it's more ~sqrt(2*number of floors). and then apply then apply the reduce gap by one scheme.
So, begging for hints here, but this is bothering me:
(and the order in which they look need not be predetermined before they start).
As far as I can tell, no econobot gets any new information during the process: everything any one of them knows when they have their turn to look, they knew before the first bot looked. At which point, there's no basis for changing any strategy at all after they start. Which makes the quoted parenthetical superfluous.
Am I right about that, or am I missing something that would allow changing the order in which econobots look to be a functional part of the strategy?
63: Yes, the strategy does not change, but they do get to see the number in the briefcase, even if it is incorrect.
"~" means "proportional to" and I was talking about asymptotics. Sqrt(2) is 1-ish anyway.
I do not think there is a strategy with a predetermined order that works. But the bots can "react" to the numbers they uncover.
64: Oh, wait. Each econobot doesn't have to name a list of 50 briefcases she wants opened, she can open them one by one, look at them, and then choose the next one? That's useful, although I don't quite have something to do with it yet.
70: it would ruin the experiment, but have at it.
Arg something about partitions and permutations and pigeonhole. I'm not quite putting the pieces together.
The problem I'm having with doing anything simple with it, is that the more variable each bot's strategy is, the less subsequent bots know about what's already happened (that is, my strategy in 54, where in each pair of bots, the second makes their guess on the assumption that the first was successful and knowing what the first's guesses were, breaks down if the second doesn't know what the first's guesses were.)
Anyway, the correct answer is to have a regulatory board certify the egg protection device to a certain number of floors and then start from there. If the eggs break below that floor, sue.
So one possible strategy would be to number all the briefcases from left to right 1 to 100, open 1, look at the number on the bit of paper inside (say it's "37"), go to briefcase 37, open it, look at the number on the paper inside, go to that briefcase and so on.
That seems like it should be important but I can't see why.
I'm trying to work through the n=4 in my head now--not a problem where I found the smaller n cases that useful to getting to the solution (which may be a very indirect hint).
Also, FWIW, in the n=100 case the strategy absolutely crushes the 100-to-1 odds. It leads to a much better chance of success. In fact you know you have it after the first bot completes--one specific result for him guarantees you are at break even.
Yes. A single scenario for the first bot that occurs 1% of the time guarantees that every one gets theirs right.
Working through the n=4 problem with the winning strategy, I think get 9/24 chance of success (higher than the 1/4).
It does seem like fucking magic.
Ajay should be feeling a bit of warmth right now.
For the n=100 case I find a strategy that wins about 31.2% of the time, if I have my arithmetic correct. I think I heard the problem a long time ago because I don't think I would have thought of this strategy on my own.
Wait, but then I find that you can win 5/12 of the time with n=4, which isn't what you said. Am I still mucking something up? Now I see that ajay's 75 is the strategy I was thinking of.
Haven't read the thread - should I post hints or is Stormcrow doling them out in good measure?
Drop your device from the first floor where the egg won't break (or if it does, problem very quickly solved) and time it. This will let you determine wind resistance and, as a result, terminal velocity. Then hard boil the egg and start half way between the floor where it reaches that velocity and the second floor. If it cracks the shell rotate the shell and drop it from the floor half way between that and the second floor, and if it doesn't from the floor half way between it and the terminal velocity floor. Proceed until you get within one floor or so from the point where it changes from cracking the shell to not cracking the shell. You probably won't need the other egg, which is nice because, hey, free egg. This probably violates the ignore-physical-constraints condition, but if you really do that then you're just doing math problems for fun and good god no one is that hard up for something to do are they?
To be more precise, for the n=100 case if I have it right the number is 21740752665556690246055199895649405434183/\
69720375229712477164533808935312303556800.
82: Essear wins beaucoup fucktons of extra credit.
That is the right probability for the "hard" problem! So, almost certainly the same strategy.
You could email me or rot it .. or just post it.
Ajay should be feeling a bit of warmth right now.
Nope, sorry.
(ESSEAR: fiddlesticks! It's not even slowing him down! Bring the perigee down to 120 km and try it again on the next orbit.)
84: No need for the hints.
83: I could have gotten it wrong and missed a scenario that works. Let me recheck.
83.2: wait, that works? Why does it work?
83.last: Ajay's 75 is pretty much the strategy, but with one more specification needed. I actually lucked into guessing it early on but had no idea how/if it worked which took a lot more work.
I found that finding the break-even scenario was a lot easier than finding the overall result because math (or more precisely lack thereof).
On the eggs, there must be a limit past which adding more eggs won't help you to reduce the number of drops. Something like 7?
91.last: Right, figurng that out is the hard part.
Ah, and using the "strategy" such as it is for n=2, does give a 1/2 chance of success.
The large n limit approaches log(2)-1.
83, 90: Yes. 5/12 is the right answer for n=4. I did miss a scenario. I see now that there is a relatively straightforward formula for figuring out the probability for any even n.
I would encourage folks who fit MHPH's criteria in 85.last might continue to work on finding the single scenario for bot 1 that gets you to 1/100 chance. It actually works as sub-problem on its own.
Same setup, but find out how you can know that you've at least broken even after the first bot chooses.
Speaking of problems, how's that KitchenAid coming?
Hint for the mathematics: you can think of the briefcases as a permutation of the numbers from 1 to 100. Permutations factor into products of cycles. What's the condition on how the permutation factors that allow's ajay's strategy (supplemented with a suitable starting point) to win?
I have doused the pin in Liquid Wrench, and have acquired a punch. Tomorrow, I try whacking it again. If that doesn't work, I'm shooting it in the head and burying it in the backyard.
99, 101: Specifically for the sub-problem on 99: What would it mean in those terms if the first bot does not find its number using the Supplemented Ajay Strategy? What does it mean if it finds it at the very end of its guesses?
LB wished the blender into the cornfield garden. It was a good day.
It's a good life. It's only a good day if LB doesn't use her AK, which assumes facts not in evidence.
The real magic is when she makes it dig its own grave.
I'm genuinely surprised by 12. I feel like I usually don't comment at all in the puzzle threads, but I guess at some point in the past I probably have asked some of those sorts of questions. The threads generally read as gibberish to me until someone gets the right answer and explains it in simple terms.
I think my brain is just not wired to be good at this sort of logical/mathematical thinking, which may explain my relative success with the laydeez. (Take that, Scott Aaronson!)
107: Oh that was an unfair knock form me based on some comments in the prior Puzzler thread (the one on the card trick).
61: JP Stormcrow: I am all about being elliptical and maddeningly vague.
135: essear: <issues with problem setup>
136: teo: 61-> 135
185: JP Stormcrow: And actually I like seeing the different interpretations and approaches although I know the vagueness can annoy some folks (hi teo!).
So you actually only made the one comment but it was well-placed. (I recall you have voiced your disapproval of allusive discourse on prior occasions.)
Ah, okay, that makes more sense. Yes, I do get annoyed by allusive discourse in general, but there's no particular connection between that and puzzle threads specifically.
102. Best result from a slow and steady solvent drip-- spray a little on in the morning and at night. You're wetting the ancient lubricant remnants that have fused, the wetting compound seeps in from the edges of the dried spots.
I haven't found it in TFA yet, but didn't we do essentially this problem in a previous puzzler thread? The solution sounds very familiar to me. I don't recall who suggested the problem, but I don't think it was JP.
Bizarre. Now I'm wondering in what other context I could have possibly been exposed to this sort of problem...hrm...
Hmm, you didn't get a nerdish major at a nerdish school by any chance did you?
Enh, that was a while ago. I'm pretty sure this was sometime in the last year, which is odd since the stupid puzzles I've been doing have mostly been trivia and crosswords (to bond with my father, mainly). I was thinking of this thread, anyway.
I'm not getting any traction at all on figuring out why 75 might work. One rabbit-hole I got distracted by is that 75 doesn't describe a procedure that can necessarily be followed to completion; if you're chasing numbers, opening each briefcase that's labeled with the number on the paper that the last briefcase contained, sometimes you're going to get a loop and have to pick a new starting point (that is B1 contains P37, B37/P15, B15/P95, B95/P1, and now you have to start fresh (B2?) because you already opened B1.) But I'm not coming up with anything to do with that.
No, wait, liveblogging thoughtprocess here, that does explain it. If you get a loop, and you started with your own number, that means you won. And if the longest loop is 50 or shorter, that's the guaranteed win case, because that means everyone wins by starting with their own number. But I don't know how you'd calculate the odds of that happening, and would have to think about it a lot longer to figure that out. (I am guessing that all this rambling is what essear meant by "Permutations factor into products of cycles," but I didn't understand it when he said it.)
117.2: right. So the only way to lose is if there is a cycle of length 51, or 52, or ... or 100. If you remember how to count the number of ways of selecting k objects out of a set of n then it isn't too hard to figure out how many such loops there can be.
You say it isn't too hard -- I say I haven't thought seriously about anything like this for ages, and while I could look up the formula for selecting objects out of a set, figuring out how to apply it to identifying the longest cycle is not immediately obvious.
The 1-100 chance that tells the first bot that they've won must be his finding a set of cycles that come out to an even 50 (one cycle of 50, or any set of shorter cycles that all close without any unclosed leftovers) but confirming the odds of that is again non-obvious to me.
It's becoming increasingly clear to me that I have no facility with this kind of puzzle, despite some facility at working with numbers in other ways.
My sole contribution is that the rational-actor participants should be called HE, homo economicus, plural HHEE.
119.last: Consider the case where the first boot gets their number on the 50th briefcase (which will occur 1/100th of the time, same as the odds for getting on any of their briefcases).
They are in a cycle that is exactly 50 long, so every one is in a cycle that is 50 or less and they will win. So just that one scenario is enough to show that they break even since it occurs 1% of the time. If they don;t get there number, they are on a cycle greater than 50 in length and of course they lose, and if they get their number in briefcase before 50 there still might be a longer than 50 cycle than at least one of their compatriots must be on so they will lose. (Of course there are a fair number of cases where they still win, say cycles of 30-30-40, or 49-1-50, whatever. These add up with the "find on the 50th" scenario to the overall 31% chance of winning. Which to me is astoundingly high given the size of the solution space.)
There is a decent write-up in Wikipedia of it as the 100 prisoners problem. I particularly like the chart of the probability distribution of the longest cycle.
But wait, just because it's made up of cycles shorter than 50 doesn't mean everyone will win. They might get on to the wrong cycle. What happens then?
A thing that I noodled over a bit was that the probability of 50 being the longest cycle is 2%. So, for exactly half of those instances, the first bot finds it's number on the 50th briefcase. Took me a bit to intuitively grasp that as being correct. (Although it now seems to follow quite naturally--if the longest is 50 there is precisely a 50% chance that the first bot is on that cycle.)
122: No, in that case there is no *wrong* cycle. They will all come to their own number before they have reached 50 briefcases. They always start in their own cycle (due to the supplemental part of the Supplemented Ajay Strategy).
... because everyone starts with the briefcase with their own number on it. Sorry.
Okay, but then the odds of the first player knowing that they're going to win are better than 1/100.
1/100 are the odds that the first player is in a cycle of length 50 (which would lead him to finding his number in the 50th briefcase), plus the odds that he sees any number of shorter cycles and also finds his number in the 50th briefcase. But if what he sees is a set of shorter cycles, all of which are closed, and he finds his number in one of the earlier cycles (so, not in briefcase 50) he also knows they're going to win -- any time the first player sees only closed cycles and finds his number is a guaranteed win, because you need him to see at least one unclosed cycle to fit a 51 or greater length cycle in the problem.
In the sequence you are following, the next briefcase if you find your own would be back to the first one you opened. The only way to lose is if you get to the 50th briefcase before you get to your number. Another way of stating it is that every finds their number in briefcase n where n is the length of the cycle that they are on.
126.last: He will never get into any other cycles.
You only explore your own cycle.
plus the odds that he sees any number of shorter cycles and also finds his number in the 50th briefcase.
Which are 0 per 128 & 129.
128: I'm not following you.
Say Bot 1 starts on what turns out to be a cycle of length 10, meaning that he hits his number on the tenth briefcase. But he's supposed to open 50 briefcases, so he picks another starting point and starts cycling again. If his second cycle turns out to be of length exactly 40, then he knows they have a guaranteed win (because there's no room for a long cycle left), but his number wasn't in briefcase 50.
128, 129: I don't see this (or anything that rules out my 131) in the rules as stated.
131.last: Ah yes, another place I could have sharpened up the problem; should probably have them stop after they find their own number. So yes there is the case where the max is 50 but they were not on it, and by staying with the program they explore all of the shorter cycles.
So, good catch. In a case where they ended a cycle exactly at 50 they would also know.
So yes there is the case where the max is 50 but they were not on it, and by staying with the program they explore all of the shorter cycles.
And also any number of cases where the longest cycle is shorter than fifty, but the first player sees enough to rule out a long cycle (like, first player sees cycles of 10 and 40 -- they know they've won, but the remainder could be one cycle of 50, or any number of shorter cycles).
135: Right.
The clean way to do it is to have them stop when they find their number.
A thing that I noodled over a bit was that the probability of 50 being the longest cycle is 2%. So, for exactly half of those instances, the first bot finds it's number on the 50th briefcase.
I'm nitpicking you to death here, but the 2% number can't be right, can it? 1% is the odds that player 1 finds his number in the 50th briefcase, but as we've been discussing, that doesn't necessarily mean that player 1 is in a cycle of length 50.
137: Nope, withdrawn, I'm wrong. If you start with your own number, then you always find your own number in the first loop you encounter.
137: No, I think that statement is correct. It is the probability of finding his number on the 50th briefcase. But I realize you need the caveat "if you don;t allow repeat briefcases." So yeah if he finds on 25, but then gets back in the same cycle form the same start he "finds" it again in the 50th briefcase. (Or could just say "first finds it.")
This is in fact why there are legal reviews of contracts and the like before they are issued.
And probably why LB is a lawyer (and presumably a good one).
Yeah, my error was that I was thinking "What if he finds a closed loop without his number in it, but then finds his number in briefcase 50 in a subsequent loop?" But under the strategy where you start with your own number, that's never going to happen.
Actually thinking about things is hard.
Okay, I'll give the details of the solution in case anyone cares about the combinatorics: the total number of ways arranging the numbers in the briefcases is 100!. How many ways are there to make a cycle of length 51? Well, first we choose the 51 numbers that will be part of the cycle: there are 100!/(49! 51!) ways to do that. We don't care how the remaining 49 numbers are arranged, so any of the 49! possibilities are fine. But for the 51 we have to make sure that they are a cycle, not just a random permutation of 51 numbers. If we start somewhere, we have 50 choices for the next, 49 for the next, etc., so there are 50! cycles we can make from the 51 selected briefcases.
Altogether, then, the number of ways to get a cycle of length 51 is 100!/(49! 51!) times 49! times 50!, that is, 100! / 51. So the fraction of all the arrangements that have a cycle of length 51 is 1/51.
Similarly, the fraction that have a cycle of length 52 is 1/52, etc.
So the probability of failing is 1/51 + 1/52 + ... + 1/100. In general, with 2n briefcases it's 1/(n+1) + 1/(n+2) + ... + 1/(2n), which sort of looks like integrating 1/x dx from x = 1 to x = 2 and thus tends toward log(2) as n becomes large. log(2) is about 0.7 and so the chance of winning is 1-0.7, or about 0.3.
Right, so the n=4 case is 1-1/3+1/4= 5/12 as you said. I got 9/24 because I looked the permutations and counted 9 with only cycles of 2 or less because I missed one. Not a problem that the shorter cases made it easier for me to understand, in fact sort of the reverse.
It's becoming increasingly clear to me that I have no facility with this kind of puzzle, despite some facility at working with numbers in other ways.
Yeah, I find these threads fascinating, but I do feel sort of like a chimpanzee trying to rewire a toaster oven reading them.
You really are suffering from a lack of appliance repair people.
Part of it is just that they're genuinely difficult and so everyone's going to have some of that feeling of struggle. If you enjoy that feeling, then you keep doing it and get better at it.
I just got to thinking "but really, how are you sure that this is the BEST way to do it?" I mean it's clever, but couldn't someone be more clever? Of course, this is exactly what mathoverflow was invented for, and someone asked exactly that question several years ago. The answer apparently is yes it really is the best strategy.
Thanks for the link UPETGI. As i was trying to be more careful in describing the problems/solutions, I did think from time to time about whether or not it was the best strategy. I enjoy how that thought process can lead you to "sharpen up" puzzles or even lead to different ones. (Here's James and I doing that with a 12/13-ball weighing problemHere's James and I doing that with a 12/13-ball weighing problem.)
146: I'm too lazy to read the link too carefully, but am I correct in surmising that this is due to all the uncertainty being in the first person's trajectory, which is pretty clearly irreducible?
The argument is pretty clever. You change the rules of the game, but do so only in ways that make it *easier*, and then you show that in the easier game it doesn't matter what strategy you use you'll always win with exactly the odds calculated above. The key rule change is that you allow the players to leave the boxes that they checked open for later players.
I mean, the argument has to be clever, because there are just too many strategies out there for a direct argument to be possible.
What would be the best strategy such that after opening the 50 briefcases nobody finds their number? That has to be random right?
From that Math Overflow thread, I got to this, which includes a version of the briefcase puzzle as the first problem, and a proof of the solution. I was intrigued by the third problem there, "The Dot-town Suicides," because it looked like there was a major flaw in the induction proof he gives of the result. And in fact, both the statement of the problem and the solution are flawed, but a corrected statement does lead to the result claimed, following the architecture of the proof. Here is the problem as stated:
Each resident of Dot-town carries a red or blue dot on his (or her) forehead, but if he ever figures out what color it is he kills himself. Each day the residents gather; one day a stranger comes and tells them something -- anything -- non-trivial about the number of blue dots. Prove that eventually every resident kills himself.
Comment:
"Non-trivial" means here that there is some number of blue dots for which the statement would not have been true. Thus we have a frighteningly general version of classical problems involving knowledge about knowledge.
In order to get the proof to go through, I think you need the following additional facts not stated in the original:
1) Every resident knows that the stranger is a complete truth-teller.
2) If a resident figures out the color of his or her dot, he/she says nothing to anyone else about this that day, but commits suicide when alone in his or her house that night.
3) Every resident knows that every other resident is completely logical and capable of working through all the implications of what he or she knows, and will definitely commit suicide as above if he or she ever deduces the color of his or her dot.
The apparently paradoxical nature of this problem is that the stranger can make a statement that every resident not only already knows is true, but knows that every other resident already knows it to be true, so that there is no apparent reason for anyone to expect anyone else's behavior to change as a result of the statement. And yet several days later the statement leads to several residents realizing the color of their own dots and committing suicide.
For example, in a village with 10 blue dots and 10 red dots, the stranger can say: "There are at least 3 blue dots in this town." Well sure - everyone can see at least 9 blue dots, and knows that everyone else is seeing at least 8 blue dots, so it doesn't seem that the stranger is adding any new information. But a few days later (given my additional conditions) a bunch of residents do kill themselves.
152: I think we also need to add:
4) The residents know that no one will commit suicide for any other reason, and can determine if any particular death is a suicide.
So here's my explanation of the apparent paradox in 152, which is to recognize that knowledge isn't just a set of facts about the world, but also about how we justify our beliefs (getting into a kind of epistemology here...). Even though the stranger's comment doesn't add to any villager's knowledge of the world itself, it does give each of them a way to justify certain facts about that world that is independent of their own visual observations of the dots, and therefore known to be shared by all the other villagers. It also gives them a common reference point of when this justification was introduced to allow them to synchronize their expectations of when various consequences would ensue.
So in my example (10 red dots, 10 blue dots, stranger says "there are at least 3 blue dots"), on day 1, every villager can say "I now know, independent of my own observation of the dots, that there are at least 3 blue dots in the village." On day 2, they can say, "I now know, based just on the stranger's statement and the absence of suicides last night, that there are at least 4 blue dots in the village, because if there were 3, every blue dotter would have realized yesterday that his/her own dot must be blue, and would have suicided last night." (This is why it is so important that the villagers all know that the stranger is a truth-teller: without that, the stranger's statement can't be used to independently justify anything, even though they can all see it to be true.) And so on, until on day seven, they can say "I now know, based just on the stranger's statement and the absence of suicides to date, that there are at least 9 blue dots in the village, because if there were 8, every blue dotter would have realized yesterday that his/her own dot must be blue, and would have suicided last night."
So far, every statement has been compatible with what each villager already knew from their own observation of the dots. But since each of these deductions is independent of that personal observation, each villager knows that every other villager has been able to make that same deduction. Now, though, each villager with a blue dot can combine this deduction with his or her own observation of 9 other people with blue dots, and think "If my own dot is red, all these other people must have just realized that their own dot must be blue, and so they will all kill themselves tonight." When the next day dawns and all their neighbors are still there, they all realize "OMG, my own dot must be blue." So they kill themselves that night, followed by the red-dot villagers the following day.
