Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[silverspawn]

So there are 100!, that is, 100*99*98...*2*1 ways the numbers could be arranged. All of them are equally probable. Given any strategy, some subset of those 100! are going to yield a win under that strategy. So the task can be alternatively phrased as maximizing the size of that subset.

[silverspawn]

Let H = {1, ..., 100}. We can formalize the possible arrangements as bijective functions f : H -> H. Then F is the set of all such functions and |F| = 100!.

Given any subset S of H, exactly half of all elements f in F are going to have the property that f(1) in S. Ditto for a subset T and f(2) in T. But the two are not independent, so the set of all f for which f(1) in S and f(2) in T could be greater than a quarter. But I still don't even see how you can choose S,T such that it goes above 0.3. I guess the answer has to come from studying the subset {f in F | f(1) in S}. We can even assume WLoG that S = {1, ..., 50}.

[scott_pilgrim]

If you're stuck, I recommend thinking about the case with n=2 prisoners opening 1 box each. It should be obvious how to do better than the naive 25%. Then think about n=4. You might have to do some case analysis, but hopefully you can find a solid solution there. Then you want to think about how that generalizes to larger n. If you're still stuck, think about what it means for prisoner #1 to succeed with the strategy you used for n=4. What properties do you want the permutation on 4 elements to have? How many permutations have the requisite properties?

I really like this problem because (major spoiler) it teaches you about cycle structure in permutations. The answer is totally non-obvious and counterintuitive at first, but it points to something really beautiful.

[silverspawn]

Hm I haven't looked at the spoilers yet, but I was about to give up because I seem to have upper-bounded the probability of success for the first two by (50*50)/(100*99). Thought maybe the puzzle is wrong in some way. But if it really is real there must be something wrong with the proof...

[silverspawn]

To confirm, is it correct that the assumed probability distribution for how numbers are put into boxes is uniform over the set of 100! possible distributions?

[scott_pilgrim]

To confirm, is it correct that the assumed probability distribution for how numbers are put into boxes is uniform over the set of 100! possible distributions?

Yes.

[scott_pilgrim]

By the way, I'm not actually sure how [super ultra major spoiler] the proof that the permutations with cycle length at most n/2 appear with probability ~1/e goes; but I think it's a result I've heard cited in other contexts, so I assume it's correct.

[silverspawn]

My brain doesn't allow me to keep thinking about this problem without first realizing what's wrong with this proof:



And (50^2*98!)/100! = (50^2)/(100*99) < 0.3.

[scott_pilgrim]

Your proof would work if S and T were independent, randomly drawn sets of size 50, but that's not the case here. For example, it would be easy to modify your proof to show that the probability that f(1) \in S and f(1) \in T is also 50^2/(100*99), but if S and T are chosen to be complements of each other, the actual probability is 0.

[scott_pilgrim]

Your proof would work if S and T were independent, randomly drawn sets of size 50, but that's not the case here. For example, it would be easy to modify your proof to show that the probability that f(1) \in S and f(1) \in T is also 50^2/(100*99), but if S and T are chosen to be complements of each other, the actual probability is 0.

Sorry, this would actually be 50^2/100^2, but you get the idea.

[silverspawn]

I don't get it where am I using independence?

The proof upper-bounds at the step where it sets the size of a set with f(1) = s and f(2) = t to 98!. If s=t, the real size is 0. Similarly for f(1) only, it would give only an upper bound.

[scott_pilgrim]

Similarly for f(1) only, it would give only an upper bound.

It's still clear that the bound is incorrect, because if S and T were chosen to be the same, the probability would be 0.5, not 0.25.

I don't get it where am I using independence?

I've thought about it more carefully and I think the answer is that in the line where you count the number of "good" f's, you assume that s \neq t. If s=t, then there are 99! "good" functions, not 98!. The sets S and T could potentially be chosen such that s=t more often than expected it random.

[scott_pilgrim]

I've thought about it more carefully and I think the answer is that in the line where you count the number of "good" f's, you assume that s \neq t. If s=t, then there are 99! "good" functions, not 98!. The sets S and T could potentially be chosen such that s=t more often than expected it random.

Wait, I think I've confused myself about what s and t are doing. 1 and 2 are always different, so I think that line is actually correct...

[silverspawn]

Yeah if s=t, the set is empty. One of my first thoughts was that it's optimal to choose the second set to have no overlap with the first... in which case they're never the same and we get equality in that step.

[scott_pilgrim]

Okay, this is a lot more subtle than I thought. I believe your proof now. I *think* the problem is that it doesn't actually apply to the original problem.

In your proof, you imagine choosing S and T to be whatever you want, and then drawing a random function, and asking about the probability that that random function is consistent with S and T. In the actual problem, you draw a random function first, and then set S and T based on the random function. Since there's no communication allowed after the game starts, this sounds like the same thing, but I think it's not. For example, if you could set S and T such that S contains f(1) and T contains f(2), the probability would be 1. Obviously you can't do that, but the solution could potentially exploit some structure in f after it's been drawn. That is to say, you set some algorithm, then draw a random function f, and then run the algorithm on f to somehow generate S and T. I'm convinced this is different from what you do in your proof, but it's hard to say more without giving away the answer.

[scott_pilgrim]

Thinking a little more, I think it actually does come back to independence. In your proof, S and T are chosen independently of f, but in reality they don't need to be.

[MiX]

But you don't know f, right? There's no information you can gain about f before you decide what S and T are. In fact, you're going to pick the same S and T for all f, in the optimal solution.

[scott_pilgrim]

But each individual learns information about f as they go; S and T can be generated adaptively as you see what each box outputs.

[MiX]

Can individuals talk after they go check boxes? If yes, then this is super easy: the first 2 prisoners know all boxes. If not, then I'm not sure how you get information that way.

[scott_pilgrim]

I guess what I'm trying to say is that I, prisoner #1, can open a box, then decide which box to open next, then open that box and decide which box to open next, etc. I can't go talk to prisoner #2, but my point is that I don't have to decide my set independently of f.

[MiX]

I guess what I'm trying to say is that I, prisoner #1, can open a box, then decide which box to open next, then open that box and decide which box to open next, etc. I can't go talk to prisoner #2, but my point is that I don't have to decide my set independently of f.

But...oh...! Huh. That does change things...

[silverspawn]

Mhh... so technically, my argument doesn't assume anything about S and T at all; they are arbitrary sets. But it only shows that the subspace of functions for which this is a solution is about a quarter of F, and that may not mean the probability is about a quarter. So I think the mistake you're pointing at is to assume that the distribution over F is uniform.

(This is mb just a different way of phrasing it.)

[silverspawn]

Since with both it comes down to independence

[silverspawn]

Will think about it more before looking at spoilers!

[silverspawn]

Unrelated, extremely interesting but also hard to follow video. Among other things, there's an argument here that observing the computational properties of vision is itself enough to show that the brain uses holistic computations of some kind because otherwise the tasks are too algorithmically complex. I foresee a future in which I spend a lot of time dealing with this.