2 puzzles for you

[eLiu]

Ran into the first one in an interview, second one from a friend. As always, don't say anything if you've seen the answers before. So here we go:

1) There are 100 inmates (numbered 1..100) each with his own locker. Each locker has a number, 1 to 100 inclusive, inside. The warden poses the following challenge. Each inmate is allowed to open 50 lockers. If he finds his own number, he passes. If EVERY inmate passes, then they all live. If ANY inmate fails, then they all die.

The numbers in the lockers are randomized before the first inmate opens a door; after that, no further changes. The inmates can discuss a strategy beforehand, but they cannot communicate with each other once the process begins. Once the games starts, each inmate can use NO INFORMATION about other inmates--no communication, no deduction, etc. In particular, the strategy must work if each inmate does not know who goes before/after him. (So if you want to assume a particular order, you cannot have the inmates deduce things about locker contents based on who has already gone. For example, it would be ok to say have every inmate agree to only look in lockers 1-99. If the inmates know their line-up order, then if the last inmate in the line gets to go, he will die. He "knows" that his number is in the 100th locker, but he cannot act on this information by the rules of the game.)

What is the probability that they live? What is their strategy?

Also, if it helps, feel free to relax the constraints, develop a solution, and then try to fix it to conform to the constraints (but of course post what extra assumptions you're making). I'm not saying that this will help though.

2) Alice is sending Bob a 31-bit message. You want to send Bob a message via the following process:
a) intercept Alice's message
b) flip at most *one* bit
c) send the modified message on to Bob

Bob has no idea what Alice's original message is; he only received your (possibly) edited version. You and Bob can communicate beforehand to work out a strategy.

How many bits of information* can you transmit to Bob with this method? How do you do it? Note: I want a worst-case result, but feel free to explore "expected" results.

*To clarify: If you claim to be able to send 2 bits of information (00, 10, 01, 11), then Bob must be able to understand these 2 bits regardless of what Alice's original message is. For example, it is always possible to send 1 bit of information. Pre-arrange with Bob to have him only look at the first bit of Alice's message. After interception, you can ensure that bit is either 0 or 1 with only 1 bit flip, always.

 

[Daverino]

Regarding question 1. Do we assume that if any prisoner doesn't find his or her number that the challenge ends?

 

[Cerb]

1) 0.5^100? If the numbers are randomized, they have to get their own number, and can't know if anyone else already got their number, I really don't see how strategy would play into it. Probably wrong, but I don't see any way around it.

2)

*To clarify: If you claim to be able to send 2 bits of information (00, 10, 01, 11), then Bob must be able to understand these 2 bits regardless of what Alice's original message is. For example, it is always possible to send 1 bit of information. Pre-arrange with Bob to have him only look at the first bit of Alice's message. After interception, you can ensure that bit is either 0 or 1 with only 1 bit flip, always.

If Alice's message uses all 31 bits, wouldn't the Alice or Bob services be likely to have unexpected behaviors, after the 5th developer starts taking over the system, and this little trick, that saves only 4 bytes/message, is not sufficiently documented?

Spoiler

But anyway, I'm pretty sure a xor against a predetermined value is the way to do it.

 

[dighn]

1) can the prisoners rotate e.g. prisoner 1 opens 1 door, prisoner 2 opens another door, then prisoner 100, then 1 again, repeat 50 times?

 

[Maximilian]

1. 50% change of living, all they need is the first inmate to find his own number and then they are set because half of the lockers will be open by then and the other prisoners will definitely find their own number after that.

Nobody said the lockers get closed afterwards or that the numbers are re-randomized

 

[postmortemIA]

1. 50% change of living, all they need is the first inmate to find his own number and then they are set because half of the lockers will be open by then and the other prisoners will definitely find their own number after that.

Nobody said the lockers get closed afterwards or that the numbers are re-randomized

Yes he did

Each inmate has NO KNOWLEDGE of the lockers opened by the other inmates.

sounds like game theory sample to me. obviously there has to be way to increase chance beyond 50% per prisoner, as when that is multiplied for all, is very small chance.

 

[PhatoseAlpha]

Do the inmates go in order?

 

[eLiu]

Responses...

also, I'll add that problem 2 is a lot harder than problem 1 (at least in my experience)

Regarding question 1. Do we assume that if any prisoner doesn't find his or her number that the challenge ends?

Yes. If any prisoner fails to find his number after opening 50 lockers, they all die.

1) can the prisoners rotate e.g. prisoner 1 opens 1 door, prisoner 2 opens another door, then prisoner 100, then 1 again, repeat 50 times?

Since there is no information transferred between prisoners, I don't think this actually matters. But let's say that each prisoner has to open all 50 lockers (he can stop if he finds his number of course) before the next prisoner gets his turn.

1) 0.5^100? If the numbers are randomized, they have to get their own number, and can't know if anyone else already got their number, I really don't see how strategy would play into it. Probably wrong, but I don't see any way around it.

If every prisoner chooses 50 doors at random and opens them, then yes, this is what happens. But you can do A LOT better. I can give hints later if people want them.

2)
If Alice's message uses all 31 bits, wouldn't the Alice or Bob services be likely to have unexpected behaviors, after the 5th developer starts taking over the system, and this little trick, that saves only 4 bytes/message, is not sufficiently documented?

Practicality is never a concern with these kinds of puzzles... c'mon man
Also, this trick isn't saving any space per message. It's allowing a 3rd party to send a message independently of the contents of the original message.

As for the blacked out part of your msg, that doesn't do any better than telling Bob to always look at the 1st bit or something. I mean, what if Alice's message is all 0s? Remember, the solution has to be able to work regardless of what the original message is.

1. 50% change of living, all they need is the first inmate to find his own number and then they are set because half of the lockers will be open by then and the other prisoners will definitely find their own number after that.

Nobody said the lockers get closed afterwards or that the numbers are re-randomized

Yeah I think we covered this one already. No prisoner knows what the other prisoners do. Doors are all closed, etc etc. 50% is of course not correct, but it is vastly closer to the right answer than 1/2^100

BUT the numbers *are not* re-randomized or changed in any way after each prisoner. The numbers in lockers are fixed at the start of the process and untouched thereafter.

sounds like game theory sample to me. obviously there has to be way to increase chance beyond 50% per prisoner, as when that is multiplied for all, is very small chance.

I'm not sure what you're getting at here. Why does going above 50% per prisoner matter at all? And I'd be reluctant to apply game theory since there is no information transfer between prisoners (but then again, my game theory is pretty weak so maybe there's a solution in there too).

Do the inmates go in order?

I don't think it matters. But if it helps, assume they go in order.

 

[dighn]

well then, can a prisoner move the numbers in the lockers they open?

 

[eLiu]

well then, can a prisoner move the numbers in the lockers they open?

Not in the problem I'm thinking of.

That would be an interesting twist though. I think it actually makes the analysis harder but I believe at least the first prisoner's strategy would be the same as in the problem I posed.

 

[dighn]

Not in the problem I'm thinking of.

That would be an interesting twist though. I think it actually makes the analysis harder but I believe at least the first prisoner's strategy would be the same as in the problem I posed.

i'm thinking the first guy would open 1-50, sort them. the second guy 51-100, and sort those. assuming the first two guys got lucky (1/4), then every other person can check 1 and 50 and figure out which half their number is in, and then do a binary search in that half with 100% certainty.

but, as you said, can't move the numbers.

 

[Cerb]

If every prisoner chooses 50 doors at random and opens them, then yes, this is what happens. But you can do A LOT better. I can give hints later if people want them.

Each inmate has NO KNOWLEDGE of the lockers opened by the other inmates.

Without an planned order, or feedback, I don't get how it would work, and the above precludes them being allowed to plan an opening order.

Can the inmates make use of paper and pencils, and a bag, prior to starting?

2) Indeed, 0 breaks it, requiring additional message information .

 

[iCyborg]

Without an planned order, or feedback, I don't get how it would work, and the above precludes them being allowed to plan an opening order.

Can the inmates make use of paper and pencils, and a bag, prior to starting?

I happen to know this puzzle, and this is a hard problem for an interview even for someone good at math; just a warning to you guys. At least the full solution and optimality proof - I don't think one can just sit down and "think for a bit". Maybe if they would be looking for an approach and reasoning, and not expecting a proper solution. I know the strategy and roughly what % I'm supposed to get, and it would still take me some time to work out the solution, and I don't remember how to prove that's the best we can do.

That said, OP asked not to give any solutions, so I will give you a very light hint, it's not really a hint how to solve it, but a hint that they can do better than 0.5^100:
Think about this: Inmate 2 knows which boxes inmate 1 opened, and he assumes he passed(*). Can you see how inmate 2 could use this information to have a better chance than 50% for himself?

(*) He has to assume this, and in general, the "extra knowledge" for inmate K is which boxes the previous K-1 inmates opened, and that they passed. If one of them didn't, they're all fu**ed anyway. They're just trying to increase their odds, so they assume everyone before them is correct.

Or think about 2 inmates opening one box each, it would appear that each has 50% chance, so the two of them are at 0.5*0.5 = 25%. But it's trivial to find a strategy that gives them 50% chance.


Since I think this is a hard puzzle, and OP said 2 is a lot harder, I'm not going to put much effort into 2). I can see some simple ways to raise expected num of bits, but I can't move from 1 as the worst case.

 

[beginner99]

Since there is no information transferred between prisoners, I don't think this actually matters. But let's say that each prisoner has to open all 50 lockers (he can stop if he finds his number of course) before the next prisoner gets his turn.

I think that matters a lot.

My strategy before I read this would have been the following which could be defined before starting the procedure:

Prisoners line up from 1-100. first one goes and opens locker 1. If he finds his number he will sit out or not return (eg "signal" the other he found his number) if not he will stand back to the end of the queue. As soon as a prisoner found his number, the next one will open locker 2. And so on.

I did not go through with the math but on average for each locker only half the prisoners will have to open a locker and since you have 50 tries on 100 lockers on average it should work out.

 

[beginner99]

Think about this: Inmate 2 knows which boxes inmate 1 opened, and he assumes he passed(*). Can you see how inmate 2 could use this information to have a better chance than 50% for himself?

The information given is confusing. Either they can communicate or else inmate 2 has no idea which boxes inmate 1 opened unless they defined for the first one open 1-50.

Also what happens if an inmate finds his number? Do the other inmates get this information?

IMHO if the first inmate instantly opens all his 50 lockers, his change is always exactly 50% and hence total chance can't be higher than that. What I'm trying to say is they should be able to take turns as outlined in my previous post else chance can't be higher than 50%.

 

[Cerb]

Think about this: Inmate 2 knows which boxes inmate 1 opened, and he assumes he passed(*). Can you see how inmate 2 could use this information to have a better chance than 50% for himself?

Not really, no:

Each inmate has NO KNOWLEDGE of the lockers opened by the other inmates.

The problem requires that they specifically do not know what lockers any other inmate has opened, or will open, else the challenge is void (probably failed). Based on the problem as posted, one inmate might know if the prior inmate passed or not, but that doesn't help, without knowing at least some of the boxes that the prior inmate(s) may have opened.

With no communication, all I can think of would be writing ranges (such as 1-30, 11-40, etc., allowing some flexibility, but ensuring a high chance of several full passes) on paper, folded closed, then each one takes a piece out of a box they can't see into. Then, they would sort the lockers they open, which would lead the lockers ever closer to being 1-100, increasing the chances of the next one being able to find his number near a locker of his number.

Proving it might be another problem, but that's why programmers have optimized fast pseudo-random number generators . In fact, it might actually feasible to do a complete enumeration, since the lockers shouldn't need to be re-shuffled for each trial run.

I can see some simple ways to raise expected num of bits, but I can't move from 1 as the worst case.

I have a couple more ideas, but this time I'm actually going to test them, first .

 

[iCyborg]

The information given is confusing. Either they can communicate or else inmate 2 has no idea which boxes inmate 1 opened unless they defined for the first one open 1-50.

They had time to discuss strategy - obviously this would include some discussion about how will each of them would be opening the lockers. E.g. inmate 1 might say: I'll be opening 1-50. Inmate 2 would then know this. he doesn't know what did inmate 1 see in them nor where did he find his number, if he did at all, because that happens once all communication is cut off.

Also what happens if an inmate finds his number? Do the other inmates get this information?

IMHO if the first inmate instantly opens all his 50 lockers, his change is always exactly 50% and hence total chance can't be higher than that. What I'm trying to say is they should be able to take turns as outlined in my previous post else chance can't be higher than 50%.

The other inmates do not get info, but it's irrelevant: you're calculating odds and it will be a product of probabilities that each one is correct, the key is that they are not independent, but conditional probabilites. each one of them assumes all the previous inmates passed.

 

[iCyborg]

Not really, no:

For 2 inmates: they both decide that inmate A will open box 1, and inmate B will open box 2. That is their strategy:
A has 50% chance of missing, if he misses, that's it. If he passes, then B will pass too, so they now have a 50% chance of success.

For 100: say 1 goes 1-50. 2 can take 51-100. He has a 50/99 chance, because number 1 can't be there, so 50 boxes and 99 possibilites.

The problem requires that they specifically do not know what lockers any other inmate has opened, or will open, else the challenge is void (probably failed). Based on the problem as posted, one inmate might know if the prior inmate passed or not, but that doesn't help, without knowing at least some of the boxes that the prior inmate(s) may have opened.

With no communication, all I can think of would be writing ranges (such as 1-30, 11-40, etc., allowing some flexibility, but ensuring a high chance of several full passes) on paper, folded closed, then each one takes a piece out of a box they can't see into. Then, they would sort the lockers they open, which would lead the lockers ever closer to being 1-100, increasing the chances of the next one being able to find his number near a locker of his number.

Proving it might be another problem, but that's why programmers have optimized fast pseudo-random number generators . In fact, it might actually feasible to do a complete enumeration, since the lockers shouldn't need to be re-shuffled for each trial run.

They do not know what other inmates saw in the lockers they opened, nor where they found their numbers if at all. Perhaps that's a bit unclear, but it's quite reasonable as "discussing strategy" would be completely meaningless if they're not allowed to talk about lockers: they can discuss anything before proceeeding to opening them, after that, no more communication, that's stated in the problem.

 

[Cerb]

For 2 inmates: they both decide that inmate A will open box 1, and inmate B will open box 2. That is their strategy:
A has 50% chance of missing, if he misses, that's it. If he passes, then B will pass too, so they now have a 50% chance of success.

For 100: say 1 goes 1-50. 2 can take 51-100. He has a 50/99 chance, because number 1 can't be there, so 50 boxes and 99 possibilites.

That's knowledge of lockers opened by other inmates.

They do not know what other inmates saw in the lockers they opened, nor where they found their numbers if at all. Perhaps that's a bit unclear, but it's quite reasonable as "discussing strategy" would be completely meaningless if they're not allowed to talk about lockers: they can discuss anything before proceeeding to opening them, after that, no more communication, that's stated in the problem.

But, if they make any decisions about what lockers others will open, then the stated restriction is broken. If #1 and #2, FI, negotiate which lockers to open, then as soon as #2 goes, regardless of whether #1 passed, the no knowledge rule has been broken twice over.

The problem states that each one has no knowledge of the lockers others opened. So, if #2 knows that #1 will open locker 1-50, the only way to not void the challenge is for #1 to open a set of lockers that is not exactly 1-50, but not tell anyone that, which brings it all back to being effectively random.

 

[eLiu]

Anyone want hints yet?

Replies...

i'm thinking the first guy would open 1-50, sort them. the second guy 51-100, and sort those. assuming the first two guys got lucky (1/4), then every other person can check 1 and 50 and figure out which half their number is in, and then do a binary search in that half with 100% certainty.

but, as you said, can't move the numbers.

With the optimal solution, I can do *better* than 1/4. Without having to move any numbers.

Without an planned order, or feedback, I don't get how it would work, and the above precludes them being allowed to plan an opening order.

Can the inmates make use of paper and pencils, and a bag, prior to starting?

2) Indeed, 0 breaks it, requiring additional message information .

I'm not sure what you're getting at w/the paper+pencil+bag, but as long as what they're doing only happens pre-game, then sure.

As for #2, yeah it's a toughie.

Spoiler

XOR is a powerful tool though; most people I've talked to don't go there first.

Prisoners line up from 1-100. first one goes and opens locker 1. If he finds his number he will sit out or not return (eg "signal" the other he found his number) if not he will stand back to the end of the queue. As soon as a prisoner found his number, the next one will open locker 2. And so on.

Well the problem there is that you're transferring information. My point was that since you cannot transfer information, the actual order that the prisoners open doors is irrelevant. They can pick any order since the actions of the other prisoners can never influence each prisoner's choices.

1) can the prisoners rotate e.g. prisoner 1 opens 1 door, prisoner 2 opens another door, then prisoner 100, then 1 again, repeat 50 times?

Yes they can. But read my replies with beginner99; the actual order doesn't matter because no information can be transferred. It's easier to think about if you assume that each prisoners opens his 50 lockers before the next guy gets his turn.

With no communication, all I can think of would be writing ranges (such as 1-30, 11-40, etc., allowing some flexibility, but ensuring a high chance of several full passes) on paper, folded closed, then each one takes a piece out of a box they can't see into. Then, they would sort the lockers they open, which would lead the lockers ever closer to being 1-100, increasing the chances of the next one being able to find his number near a locker of his number.

I'm not entirely sure what you're trying to suggest here. How do they sort the lockers? Each prisoner cannot move the lockers he opens. Equivalently he also cannot move the numbers in the lockers he opens. This would be a way to pass information between prisoners, which is not allowed.

I have a couple more ideas, but this time I'm actually going to test them, first .

Looking forward to seeing what you come up with


Lastly, let's address the mini-debate btwn iCyborg and Cerb. I don't want to quote everything that has been said, but iCyborg is correct.

It would be valid for the prisoners to arrange beforehand to have prisoner 1 open doors 1-50 and prisoner 2 hit doors 51-100. There is actually no information transferred. Why? Because regardless of what 1 finds, 2 will always do the same thing. Similarly, if 2 went first, prisoner 1 does the same thing regardless of what happened to 2. So the prisoners can validly arrange to each open specific lockers beforehand without violating any rules.

But they cannot CHANGE their arrangement once the game has started. For example, say the prisoners decided to only sample from the first 99 lockers. Also suppose that prisoners 1-99 succeeded so that it's prisoner 100's turn. Prisoner 100 now knows the right locker is the last one. But it doesn't matter: due to the no information rule, he has to open his original set of 50 lockers and die.

Earlier someone asked if the prisoners go in order. I said it doesn't matter, but assume that if you want. This is exactly why. Since no information can be transferred, the optimal solution should work regardless of what order the prisoners line up in. I guess I could've avoided this confusion if I forced it so that the prisoners go in random order.

The general version of this problem is having N prisoners and N lockers (N even) with prisoners allowed to open N/2 lockers. With N=2, iCyborg's post gives the best possible solution (50%).

I happen to know this puzzle, and this is a hard problem for an interview even for someone good at math; just a warning to you guys. At least the full solution and optimality proof - I don't think one can just sit down and "think for a bit". Maybe if they would be looking for an approach and reasoning, and not expecting a proper solution. I know the strategy and roughly what % I'm supposed to get, and it would still take me some time to work out the solution, and I don't remember how to prove that's the best we can do.

Yeah in an interview, I don't think anyone expects you to get as far as proving the strategy is optimal. But for the level that these interviews are testing for, being able to find the solution (typically at least with a couple hints) and analyze the result (i.e., show what the probability of success is--which just requires some discrete math/probability) is reasonable to expect. I saw this problem in a software dev (new grad) interview in SF/south bay area (like Google, Dropbox, FB, etc. but not actually one of those 3). I mean if companies are offering 120k+ salary to new grads, the interviewees better be smart and so there will usually be some tougher questions to gauge that.

Personally I'm not sure if I like this problem as an interview problem. Most people I've shown this problem to end up having more of an "aha!" moment. There are definitely reasonable mathematical/algorithmic approaches to apply & reach the solution, but I find it difficult to give hints that aren't too strong while still being helpful.

 

[Cerb]

That greatly changes it.

Spoiler

In that case, they can know one or more lockers that another picks. If better than 25% can be had, I doubt I'll reach that, but >0.5^100 should be more than doable, without whatever special trick there is.

 

[eLiu]

That greatly changes it.

Spoiler

In that case, they can know one or more lockers that another picks. If better than 25% can be had, I doubt I'll reach that, but >0.5^100 should be more than doable, without whatever special trick there is.

Not 100% sure what "That" refers to in the first sentence. If you mean prisoners being able to pre-arrange a fixed strategy, then yes, depending on your solution, that information can be useful.

I guess that wasn't noted clearly in the OP? I updated it so that it's hopefully more clear.

Also, your remarks in the spoiler are correct, although not really surprising since 0.5^100 is the naive algorithm.

 

[Mr. Pedantic]

I'm confused by this first puzzle. As you say, it's a specific form of a general puzzle, with N lockers and N prisoners, each allowed to open N/2 lockers.

So say we simplify it right down. The solution for N = 2 is 50%, since if each of the prisoners opens one locker if the first person succeeds (50%) the other person is guaranteed to succeed.

So let's go to N = 4. The reason I'm confused is that because there is no information transfer between prisoners, there is no way of prisoner 2 knowing which of the lockers that prisoner 1 picked contained his number, and so there is no way to narrow the field. Therefore, the best that can be done (that I can think of) is 1/6 - prisoners 1 and 2 open lockers 1 and 2 each, giving probabilities of success of 1/2 and 1/3, respectively. Then 3 and 4 open the other 2, and each of these has a 100% success rate given the success of 1 and 2.

The best that I believe could possibly be done is 1/4, if the first 2 each have probabilities of 1/2 and the last two each have probabilities of 1. So when you say that you can do better than 1/4 with N = 100, it just seems to me that there's some way we're (I'm) misunderstanding the question.

 

[beginner99]

I happen to know this puzzle, and this is a hard problem for an interview even for someone good at math.

Yeah i was lazy and googled. I sure need to know a lot more than basic math and of course "advanced" (at least for me) stuff towards probability calculations. Anyway chance is probably 99.999% you will never encounter such a problem in real world application development.

Even with the strategy given for me it was not intuitive to understand at all (typical for such problems regarding probabilities) why it should be better than just randomly opening lockers, in fact it still isn't.

 

[Cerb]

Not 100% sure what "That" refers to in the first sentence. If you mean prisoners being able to pre-arrange a fixed strategy, then yes, depending on your solution, that information can be useful.

I guess that wasn't noted clearly in the OP? I updated it so that it's hopefully more clear.

Also, your remarks in the spoiler are correct, although not really surprising since 0.5^100 is the naive algorithm.

It would be valid for the prisoners to arrange beforehand to have prisoner 1 open doors 1-50 and prisoner 2 hit doors 51-100. There is actually no information transferred. Why? Because regardless of what 1 finds, 2 will always do the same thing. Similarly, if 2 went first, prisoner 1 does the same thing regardless of what happened to 2.

That is the 'that': allowed knowledge of others' opened lockers. My first try got almost 2x random, at N=10, but that's not even enough to measure at N=100. I may end up having to Google it, but I'd like to see if I can find some way to get it at least measurable within 10M trials at N=100, first.