Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

Post by function_seven » Sun, May 06, 2018, 2:02 AM UTC

CamperBob2 wrote: post #118

fydorm wrote: post #115

Earlier quoted context omitted.

If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them). Incidentally, the "first prisoner" might as well be every prisoner, because they aren't allowed to observe each other, communicate, or modify the room.

If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them) But there are 100 boxes, assigned at random. The prisoners can come up with a mapping function that predetermines which boxes they will open based on their names, but that function will have no relationship to the one (if any) that was used…

Post by CamperBob2 » Sun, May 06, 2018, 2:48 AM UTC

bsdetector wrote: post #121

CamperBob2 wrote: post #119

Earlier quoted context omitted.

No it's still 50%, because first person opens box 1 and second person opens box 2. They both either live or die together. As the problem is stated, the boxes remain where they are and must be reclosed after being opened. There are no other choices to be made, there's no way to retain or communicate any information about a particular prisoner's actions, and there are no order-dependent aspects to the problem. Everybod…

> there's no way to retain or communicate any information about a particular prisoner's actions The communication happens before the people go in to open the boxes. In the 2-person 2-box 1-choice example, person 1 says to person 2 "I'll open box 1 and you open box 2". With person 1 always opening box 1 and person 2 always opening box 2, what do you feel their chances are? List out the permutations and see.

Post by tomp » Sun, May 06, 2018, 4:08 AM UTC

Avshalom wrote: post #120

OscarCunningham wrote: post #100

Earlier quoted context omitted.

I think the "orthodox" answer is that your method wouldn't work, because if Alice picks 10 and 20 and opens 10 first then you have a 0% chance of winning. Instead (they say) you should pick your number at random, so that it has at least some probability of being any given integer. For example you could pick the number n with probability 2^|n|/3. That way no matter which two numbers Alice picks there's always some pro…

It's important to remember that Alice is a perfect random number generator. She certainly isn't going limit her numbers to what can be comfortably written on the paper for instance. Which is fun because while there are hundreds of puzzles that require people to be able memorize perfect hash functions on the fly or remember the state of a FSM 1000 states ago or be capable of implementing the necessary function require…

Post by fao_ » Sun, May 06, 2018, 4:33 AM UTC

theoh wrote: post #93

ryanx435 wrote: post #17

Earlier quoted context omitted.

Or just attach a lock that needs a combo (ex: 3,7,15) instead of a key to open it, then tell her the combination after she gets it and the risk of theft is zero. The problem specifically says they are communicating using the internet, so why not? "Hey, I sent you a box. It's locked with a combo lock. Call me when you get it: I want to be talking to you when you see the surprise! I'll tell you the combo on the phone!"

The situation is actually a bit tricky. If they met over the internet, there's no way to guarantee the absence of a Man-in-the-Middle who has been allowing the romance to proceed without interference, but who tampers with the messages which give the address to which the ring must be sent (and who fakes the message which says the box has been received.) The only way to avoid this possibility (of a man in the middle at…

Post by function_seven » Sun, May 06, 2018, 5:11 AM UTC

CamperBob2 wrote: post #123

function_seven wrote: post #122

Earlier quoted context omitted.

If no cycle is longer than 50 boxes (~30% chance of that being true), then by starting with the box that matches your number, you have a 100% chance of navigating to the box containing your number before your 50-box limit is reached. It’s impossible to start in the wrong cycle, because that cycle contains neither the pointer or the value. You have to find your pointer in a circular linked list. But it’s only singly-l…

But what if your name is in box #51, which you aren't allowed to open?