2 puzzles for you

[Schmide]

After this post, I'll look it up. I just wanted to think about it before I spoiled.

So you come up with a strategy for elimination.

Spoiler

Each inmate chooses a separate locker and correct choices are eliminated.

The first round the chance of any single success is (1 in 100) * 50. or 50% chance of elimination of a locker. So on average for the first 2 choices 1 locker gets eliminated and one inmate is removed. The 3rd chance of success is now 1 in 98 * 49 which has a 50% chance of success equal to the 4th chance. On the 5th round you have a (1 in 96) * 48 which has a 50% chance of elimination success. You get the pattern.

This becomes a 100c50 problem. I.e 100/1 * 99/2 * 98/3...

Which equals 1 in 100,891,344,545,564,193,334,812,497,256 chance

 

[Mr. Pedantic]

After this post, I'll look it up. I just wanted to think about it before I spoiled.

So you come up with a strategy for elimination.

Spoiler

Each inmate chooses a separate locker and correct choices are eliminated.

The first round the chance of any single success is (1 in 100) * 50. or 50% chance of elimination of a locker. So on average for the first 2 choices 1 locker gets eliminated and one inmate is removed. The 3rd chance of success is now 1 in 98 * 49 which has a 50% chance of success equal to the 4th chance. On the 5th round you have a (1 in 96) * 48 which has a 50% chance of elimination success. You get the pattern.

This becomes a 100c50 problem. I.e 100/1 * 99/2 * 98/3...

Which equals 1 in 100,891,344,545,564,193,334,812,497,256 chance

No.

Spoiler

Inmate 1 goes to the lockers, and opens 50 lockers. If he does not open a locker with his number, they all die. If he opens a locker with his number, he does not die...yet.

After inmate 1 has opened his 50 lockers, inmate 2 goes and opens 50 lockers. Then inmate 3, then inmate 4. Each inmate only goes after the inmate before has opened all 50 lockers.

 

[eLiu]

I would never think of XOR here, nor a way similar to puzzle 1, but I can think of a different and very simple approach: The sum of all numbers 1 to N-1 is T = N*(N-1)/2. Now, do a single pass through the list to get their sum S. The duplicate is S-T

Damnit, I knew I was missing an obvious technique (i wanted to disallow all the strategies except the one that uses cycles) but for the life of me I couldn't remember what, haha. It does seem silly to post the XOR strategy but miss the summation! ><

But here's a hint for using something similar to the prisoners:

Spoiler

Suppose the N numbers are held in an array indexed 1 to N. What if we treated each array index as a locker? Then this problem has the same underlying graph structure as the prisoners problem.

That said, to do this, you need to know how to determine whether a linked list has a cycle (if backpointers are allowed). You can do this in linear time and constant space. Here, you already know a cycle must exist, but you still have to find it.

I didn't refer to Shannon exclusively, but generally some sort of information theory background. Like Hamming distance

Spoiler

I actually tried to see how to send 2 bits with length 4 (one would think that 31 instead of 32 from problem statement would give me a clue to go with 3, but, eh...), but I still don't see a way. I can create 4 messages, but I don't see a way to put them in some classes so Bob can know what we sent without knowing Alice's message, it becomes messy, I feel like I could do it with a PC and some sort of backtracking algorithm, but I didn't see some nice pattern.

If it makes you feel any better, this is not a problem I'd give in an interview. This one is really balls. Working with a friend who's much smarter than I am, we took about an hour to figure it out. And it's definitely an "aha!" moment at the end. As an interview problem this could be interesting just to see what people come up with... like there are some probabilistic things you might try (which suck in the worst case but still randomized strategies are usually good in practice), there's the hamming thing (which is hard to generalize but if the problem is small enough, brute force works), etc. So it'd be less about finding the right answer & more about correctly analyzing your own ideas. Still debating whether I'd ever pull this on an interview candidate once they let me start interviewing.

Spoiler

Let's go through how you could always send 2 bits with a message of length THREE. (Yeah your intuition was right there; it's length 3. It might be possible to apply this technique to a length 4 message but it will be a lot harder.)

With a length 4 message, you can flip 4 bits which allows you to get to 4 different messages. But you can also flip ZERO bits which leaves you at the current message, meaning that you can in principle transmit 5 things to Bob. (Or a non-whole number of bits, ouch)

So let's look at messages of length 3 instead. You can flip 3 bits or nothing; hence for any given input from Alice, you can generate 4 unique outputs. Now the question is can I find an mapping of 3 bit messages to 2 bit messages where any 2 bit message is always a hamming distance of 1 away (looking at distances in the 3-bit messages) from any other 2 bit message?
000 -> 00
001 -> 01
010 -> 10
100 -> 11
011 -> 11
101 -> 10
110 -> 01
111 -> 00
Is one such mapping. Regardless of what Alice sends (left column), by flipping one of 3 bits or not flipping a bit, Bob can always access 00, 01, 10, or 11 (right column).

I'm guessing this can be generalized to larger numbers of bits, but it becomes very hard to find the right mapping (without coding an exhaustive search). It might be useful to play with a 7 bit message and see what's there, but it seems to me that mapping assigning a N bit meaning to each 2^N-1 bit message is perhaps not the way to go.

And you have the added advantage of (this references an earlier spoiler so don't read if you don't want this hint yet)

Spoiler

knowing that XOR is useful.

 

[eLiu]

After this post, I'll look it up. I just wanted to think about it before I spoiled.

So you come up with a strategy for elimination.

Eliminating lockers in the manner you suggest would be akin to transferring information between inmates. But interestingly, even with this little bit of information transfer, the performance is still way worse than the optimal strategy.

Additionally, the problem requires that each inmate make all 50 of his choices before the next inmate goes as indicated by Mr. Pedantic. However, this requirement is actually not necessary. The 0 information rule means that events can happen in any arbitrary order and it won't matter, b/c every action is completely independent.

 

[Cerb]

For #2, I was going for pop count and then +/- value(s) from the message with and or xor for elimination (and was working better), but was stuck at 1 bit. A personal thing came up, though, so I'm well out of the mood now, and just read the spoiler.

 

[Schmide]

I get it.

 

[iCyborg]

Spoiler

I think you stated that backwards. The calculation ONLY considers cycles of length>N/2. You count how many there are and divide by the total number of arrangements, n! to get the probability that an arrangement has a cycle of length > N/2. 1 - thatnumber is the answer. At the start of my last post, I explain how to compute the number of arrangements having exactly one cycle of length > N/2 and also why computing the number of cycles of length < N/2 is hard & why you cannot use the same approach.

Spoiler

Perhaps I could have phrased it better: it's easier to compute probability P for those that have cycles > N/2, but the final answer 1-P really only considers those with no cycles >N/2. And takes all of them, because all of them are OK. But imagine that having a cycle >N/2 didn't mean the certainty of death for all prisoners, i.e. the chance wasn't 0 but some non-zero probability S - you'd need to find this S and add it to 1-P. It's because the chance of survival is exactly 0 if there's a cycle>N/2 that you only need to consider those with no such cycles. Word 'consider' is unfortunately confusing here given how we actually compute the answer.

 

[iCyborg]

Let's go through how you could always send 2 bits with a message of length THREE. (Yeah your intuition was right there; it's length 3. It might be possible to apply this technique to a length 4 message but it will be a lot harder.)

I see. I was looking at 4 bits to find such a mapping to 2 bits, and was a bit overwhelmed with the number of cases/mappings, so it looked like I'd need a computer program for this. Hamming or not...

And you have the added advantage of (this references an earlier spoiler so don't read if you don't want this hint yet)

Spoiler

knowing that XOR is useful.

I'm not putting much effort into this, I think about it for a little and give up quickly. What this means is: you can safely assume that I've read all the hints

 

[eLiu]

I see. I was looking at 4 bits to find such a mapping to 2 bits, and was a bit overwhelmed with the number of cases/mappings, so it looked like I'd need a computer program for this. Hamming or not...

I'm not putting much effort into this, I think about it for a little and give up quickly. What this means is: you can safely assume that I've read all the hints

Spoiler

Ok, so I think we've well established that strategies revolving around doing arithmetic or branching operations on individual bits (like adding them together or some binary op with a preset message) will not work.

That's akin to doing basic parity checking. You can at most detect 1 bit changes with these kinds of techniques.

We also saw one way of mapping 2^N-1 bit messages to N bit messages. The most natural approach seems cumbersome... maybe there are others but I don't know them.

What else is left? What kinds of things do you typically do with bit-strings in real life?

Answer to the last question...

Spoiler

There are lots of things you can do w/bit strings, but one very common one is using 1 to indicate 'include me' and 0 to indicate 'ignore me' for a set of 2^N-1 things.

 

[beginner99]

Spoiler

LoL. Omg. Wanted to write I still don't get it and then it just clicked. Now I feel a bit stupid. For other stupids in my words:

- You are always in a cycle (unless every number is in its locker but then you win)
- If you open your locker first, your locker (or better said your number you are looking for!) will logically be part of that cycle
- This means at some point you will get back to it
- if you get back to it, that means you completed the cycle
- But you can only achieve this if the cycle has at max 50 lockers in it. (eg n/2)
- Then calculate probability for that

 

[Schmide]

Spoiler

LoL. Omg. Wanted to write I still don't get it and then it just clicked. Now I feel a bit stupid. For other stupids in my words:

- You are always in a cycle (unless every number is in its locker but then you win)
- If you open your locker first, your locker (or better said your number you are looking for!) will logically be part of that cycle
- This means at some point you will get back to it
- if you get back to it, that means you completed the cycle
- But you can only achieve this if the cycle has at max 50 lockers in it. (eg n/2)
- Then calculate probability for that

I got it till you wrote that.

Spoiler

Kidding

.

 

[Fayd]

with regard to the first problem:

I might try a monte-carlo approach to this tomorrow.

 

[eLiu]

Spoiler

LoL. Omg. Wanted to write I still don't get it and then it just clicked. Now I feel a bit stupid. For other stupids in my words:

- You are always in a cycle (unless every number is in its locker but then you win)
- If you open your locker first, your locker (or better said your number you are looking for!) will logically be part of that cycle
- This means at some point you will get back to it
- if you get back to it, that means you completed the cycle
- But you can only achieve this if the cycle has at max 50 lockers in it. (eg n/2)
- Then calculate probability for that

Minor:

Spoiler

If every number is in its locker, you're still in a cycle. Imagine each locker only has an edge connecting itself to itself. So there's 100 cycles of length 1. It's nice to be able to treat every case the same way.

 

[uclabachelor]

Question for puzzle #1: Can the inmates use time as a variable in their strategy? Ie, open 1 locker every minute? If they can, then it will improve their odds quite a bit and that I have a "decent" strategy for them if that's the case.

If they can't use time as a factor then one easy strategy is to alternate between 1-50 and 51-100 for each prisoner. That way the first prisoner has a 1/2 chance of success and every prisoner after has a 50/99 chance of success - if the the next prisoner gets to go, then you can assume that the previous prisoner found his #. This strategy is only about 10x better than randomly picking a locker for each prisoner. This is assuming that the locker containing the right number is still included in the set for the next prisoner.

I will have to think about this problem some more!

Edit some more thoughts on this: If the lockers are mapped out, then the structure presents a linked list in which each element's next pointer is the contents of the locker. There could be more than one linked list as the locker # could also contain the same number as its contents. The problem then becomes how to plan a strategy among the prisoners so that every successful prior selection improves the odds of the current inmate.

 

[IHateMyJob2004]

Inmate 1 has a 50/100 chance of getting his number
Inmate 2 has a 49/99 chance assuming that inmate 1 found his locker.

Repeat.
So, 50!/100*99* ... *52*51 are the odds, AKA astronomical.

There is no obvious strategy if information passing is not allowed.

 

[mv2devnull]

Inmate 2 has a 49/99 chance assuming that inmate 1 found his locker.

That assumption is transfer of information. The way you think it, each inmate has a 50/100 chance. You are right though, the optimal strategy is not obvious to most of us.


I had no brain, so searched the web (and later spoilers). All I can say: math is beautiful. Absolutely, mind-bogglingly beautiful.

 

[eLiu]

Question for puzzle #1: Can the inmates use time as a variable in their strategy? Ie, open 1 locker every minute? If they can, then it will improve their odds quite a bit and that I have a "decent" strategy for them if that's the case.

If they can't use time as a factor then one easy strategy is to alternate between 1-50 and 51-100 for each prisoner. That way the first prisoner has a 1/2 chance of success and every prisoner after has a 50/99 chance of success - if the the next prisoner gets to go, then you can assume that the previous prisoner found his #. This strategy is only about 10x better than randomly picking a locker for each prisoner. This is assuming that the locker containing the right number is still included in the set for the next prisoner.

I will have to think about this problem some more!

Edit some more thoughts on this: If the lockers are mapped out, then the structure presents a linked list in which each element's next pointer is the contents of the locker. There could be more than one linked list as the locker # could also contain the same number as its contents. The problem then becomes how to plan a strategy among the prisoners so that every successful prior selection improves the odds of the current inmate.

They cannot use time as a factor.

Your linked list idea is very promising; I'm impressed you got to that point so quickly. But I don't know how you could arrange so that each successful selection improves the odds of future inmates. Remember, there can be no information transferred between inmates. So regardless of whether prisoner 1 opens 1 or 50 lockers, prisoner 2 has to take the same actions, always.

Inmate 1 has a 50/100 chance of getting his number
Inmate 2 has a 49/99 chance assuming that inmate 1 found his locker.

Repeat.
So, 50!/100*99* ... *52*51 are the odds, AKA astronomical.

There is no obvious strategy if information passing is not allowed.

Not quite. As mentioned above, if inmate 1 finds his locker within 50 tries, none of the other inmates can possibly know which locker was his (unless they themselves open the locker containing #1).

What's interesting is that even if this solution were permissible, the optimal strategy is still exponentially better: you can get double digit percentage of success... almost as good as if every prisoner could report about all the lockers they opened.

 

[IHateMyJob2004]

They cannot use time as a factor.

Your linked list idea is very promising; I'm impressed you got to that point so quickly. But I don't know how you could arrange so that each successful selection improves the odds of future inmates. Remember, there can be no information transferred between inmates. So regardless of whether prisoner 1 opens 1 or 50 lockers, prisoner 2 has to take the same actions, always.



Not quite. As mentioned above, if inmate 1 finds his locker within 50 tries, none of the other inmates can possibly know which locker was his (unless they themselves open the locker containing #1).

What's interesting is that even if this solution were permissible, the optimal strategy is still exponentially better: you can get double digit percentage of success... almost as good as if every prisoner could report about all the lockers they opened.

Oh, so 1 in 2 to the power of 50. I was assuming that once a locker was found that it was left open or something.

Anyway, this is a tupid question to ask unless you have to write software on statistics. I'm 12 years into software dev. I never needed statistics and i have forgetten everything about it. Seems liek the interviewer is risking finding someone good at math and hrorrible at software dev.

 

[uclabachelor]

They cannot use time as a factor.

Your linked list idea is very promising; I'm impressed you got to that point so quickly. But I don't know how you could arrange so that each successful selection improves the odds of future inmates. Remember, there can be no information transferred between inmates. So regardless of whether prisoner 1 opens 1 or 50 lockers, prisoner 2 has to take the same actions, always.

Would it be safe to assume that the only information being "passed" would be that the next prisoner to go would know his position in line? If so, then he can say that everyone who went before him has found their number otherwise he would not be alive.

 

[mv2devnull]

Not safe. It has been stated that each of them should assume that he is the first one entering the room.


@IHateMyJob2004: Lies, damned lies, and statistics. Assumptions can be misleading. Not answering to "stupid" question may actually be a clever thing to do in this case.

 

[IHateMyJob2004]

Would it be safe to assume that the only information being "passed" would be that the next prisoner to go would know his position in line? If so, then he can say that everyone who went before him has found their number otherwise he would not be alive.

That would mean that people with even numbers in line should take even numbers. Or oddly numbered people should take odd numbers. Or even numbers take the first half of lockers and odd numbered people take the last 50.

This way, the odds for the first person are 50 in 100. But the second person and beyond would be 49/99. Slightly improving the odds.

I wonder if this concept can be improved by overlapping. (line position)mod 4 = 0 takes 1-50. =1 takes 26-75, =2 takes 51-100, =3 takes 76-100 and 1-25. I don't even want to get into the math. But if this is better odds than the basic strategy, it probably means that each person starting with their place in line as their starting point and doing the first 50 from their would be optimal. But i don't see that as as good solution intuitively.

NEW IDEA
What about time?
If people take exactly 1 minute to check each locker, they could use indirect information passing assuming the next person starts immediately after the prior finds their locker. This means that if person 1 takes 22 minutes, the next person would start at position 23. This strategy is then repeated for each person. And using such a strategy, they could even figure out which lockers have already had their number found so you would know to skip certain lockers. Thus making the odds still astronomical, but in line with my previous math of 50!/(100*99...52*51)

And one could even improve upon this by using non linear stepping when choosing lockers. Time could be used as a method of information passing. Using time, one could pass information on about what the content of locker 1,2,3 are when person 1 finds his number in 4. he could wait an extra 26 ms to pass information via time that locker 1 had id=26 in it and that locker 4 had his number in it. Thus solving two lockers for everyone else. using some sort of hashcode, the contents of 1,2 and 3 could also be passed on via time based messaging.

In an interview, they don't want to see a solution. But they want to see a thought process. Of course, this says little about team work ability though since we collectively are figuring this one out and my ideas are not all from my own intellectual musings.

 

[uclabachelor]

That would mean that people with even numbers in line should take even numbers. Or oddly numbered people should take odd numbers. Or even numbers take the first half of lockers and odd numbered people take the last 50.

This way, the odds for the first person are 50 in 100. But the second person and beyond would be 49/99. Slightly improving the odds.

I wonder if this concept can be improved by overlapping. (line position)mod 4 = 0 takes 1-50. =1 takes 26-75, =2 takes 51-100, =3 takes 76-100 and 1-25. I don't even want to get into the math. But if this is better odds than the basic strategy, it probably means that each person starting with their place in line as their starting point and doing the first 50 from their would be optimal. But i don't see that as as good solution intuitively.

NEW IDEA
What about time?
If people take exactly 1 minute to check each locker, they could use indirect information passing assuming the next person starts immediately after the prior finds their locker. This means that if person 1 takes 22 minutes, the next person would start at position 23. This strategy is then repeated for each person. And using such a strategy, they could even figure out which lockers have already had their number found so you would know to skip certain lockers. Thus making the odds still astronomical, but in line with my previous math of 50!/(100*99...52*51)

And one could even improve upon this by using non linear stepping when choosing lockers. Time could be used as a method of information passing. Using time, one could pass information on about what the content of locker 1,2,3 are when person 1 finds his number in 4. he could wait an extra 26 ms to pass information via time that locker 1 had id=26 in it and that locker 4 had his number in it. Thus solving two lockers for everyone else. using some sort of hashcode, the contents of 1,2 and 3 could also be passed on via time based messaging.

In an interview, they don't want to see a solution. But they want to see a thought process. Of course, this says little about team work ability though since we collectively are figuring this one out and my ideas are not all from my own intellectual musings.

The time idea would make the problem simple but since that's not allowed, the linked list idea is the best I can relate this problem to. If you map the lockers out, it will essentially become a big linked list. However, the # of possible locker combinations results in a big number (think search space). I think I have a pretty good solution but I have not worked out the math as I will have to simplify the problem down to a 4-locker problem lol.

Spoiler

Because each locker's content points to the next locker, you can build a one way imaginary chain whose link points to the next. If you're the prisoner, you won't know the contents of the chain but the only thing you know is your prisoner number. If every prisoner started out by opening a locker corresponding with their prisoner #, then they can greatly increase the chances and here's why.

If prisoner #1 starts at locker 1 and succeeds, prisoner #2's search space is now half of all possible combinations, otherwise prisoner #2 would not be alive.

Continuing onward, prisoner #3 opens locker #3 and so forth...

If you think of the search space as a binary tree, prisoner #1 visits the first left node. Prisoner #2's search space starts at the first left node for reasons described above (the whole right branch of the tree is irrelevant for prisoner #2).

 

[serpretetsky]

Oh, so 1 in 2 to the power of 50. I was assuming that once a locker was found that it was left open or something.

Anyway, this is a tupid question to ask unless you have to write software on statistics. I'm 12 years into software dev. I never needed statistics and i have forgetten everything about it. Seems liek the interviewer is risking finding someone good at math and hrorrible at software dev.

i dont know if you read the solutions, but the solution is NOT purely probability based, and it is MUCH better than (1/2)^(100).

I tested this out using a stack of cards. I used 2 through king (12 unique numbers), and used 1 set of red cards (signifying the peace of paper with a number written on it) and 1 set black (signifying the locker which hides the paper). I then shuffled them and randomly tossed them onto a desk in pairs.

I was only able to try it 4 times but i won once. 3 of the times i created a single giant loop and failed. The 4th time i created 1 loop of 6 cards, 2 loops of 2 cards, and 2 loops of 1 cards (the locker held its own number), which guaranteed success.

 

[iCyborg]

i dont know if you read the solutions, but the solution is NOT purely probability based, and it is MUCH better than (1/2)^(100).

I'm not sure what you mean by "NOT purely probability based". You calculate probability, it's no more or less probability based than getting the 0.5^100 answer...

 

[iCyborg]

I wonder if this concept can be improved by overlapping. (line position)mod 4 = 0 takes 1-50. =1 takes 26-75, =2 takes 51-100, =3 takes 76-100 and 1-25. I don't even want to get into the math. But if this is better odds than the basic strategy, it probably means that each person starting with their place in line as their starting point and doing the first 50 from their would be optimal. But i don't see that as as good solution intuitively.

You can get better odds than 0.5^100 with ideas like this, but not that much better compared to the answer which is not of the "astronomically small" kind.