Two more secrets

[skeptical scientist]

This is a modified version of operator[]'s puzzle two secrets, which I thought of when reading the original. The setup is the same, but the task is slightly different:

I'm thinking of two numbers (x, y) from a large set {1..N}, and you want to find them. At your disposal is the ability to ask questions about subsets S ⊆ {1..N}. For each such question I will (adversarially) pick one of my two numbers, and answer with either (x in S) or (y in S), without telling you which number I answered for. So for instance, if N = 5 and I'm thinking of the numbers 2 and 3, I'm required to answer true for the query {1,2,3}, but for {1,2,4} I can give any answer I like.

After asking as many questions as you like, you may name a number, and you win if your number is one of (x, y), and lose if it's not.

Do you have a winning strategy?



There's also a followup question, but it gives away the answer to the original question.

Spoiler:

With perfect play, what are the winning probabilities for each player (in terms of N)? What are the strategies?

[Poker]

If by a "winning strategy" you mean one that is guaranteed to win:

Spoiler:

For N>=3, which are the only values of N for which this game makes sense anyway, no. Your response is as follows: letting your two numbers be x and y, you can select a single "fake" number z, distinct from these two. For any set I give, if at least 2 of x, y, and z are in the set, you respond "yes," otherwise you respond "no." Since the only way to eliminate a pair (a,b) from consideration is to guess a set that includes both a and b and get a no, or to guess a set that excludes both a and b and get a yes, using your strategy I will never be able to eliminate from consideration any of the pairs (x,y), (x,z), or (y,z). Thus, even if I eliminate every pair but those three, I only have a 2/3 probability of winning - good, but far from guaranteed.

I typed all of the above before opening the spoiler. Now for the follow-up:

Spoiler:

Well, I pretty much answered the follow-up already, except for any details of my strategy. Efficiency considerations aside, I can basically ask whatever questions I want, as long as I adhere to this rule: every question, for any completely different pairs (a,b) and (c,d) that have not been eliminated yet, pick a set that includes a and b, but excludes c and d. One of those distinct pairs will be eliminated no matter what your response is. Consider what happens when there are no such completely different pairs left. There must exist the correct pair, (x,y). If this is not the only pair, then the second pair must share an element with the first pair, so it must be of the form (x,z). What if there are more pairs beyond those two? Well, if such a pair contains y, then it must contain z, otherwise it would be completely different from (x,z). The reverse is also true. Furthermore, if a pair contains some new element w, it must be of the form (w,x) and the (y,z) pair must have been eliminated. So in the end we either have every pair containing element x, or else we have the triangle of pairs (x,y), (x,z), and (y,z). As long as I follow this basic strategy, even when you use your best strategy and leave me in the triangle of pairs, I have a 2/3 probability of winning.

[skeptical scientist]

Nice! That's my answer as well.

[SteelCamel]

I don't see anything in the instructions about the size of subsets I'm allowed to ask about. So having found x, y, and z I can ask about the subset {x} - if you say "yes", x is a winning answer, if you say "no" then both y and z are winning answers.

[Sabrar]

If the numbers are {x,y} and you ask about S={x} then he may answer 'no' for (y in S). Or he may answer 'no' for (z in S) if the actual numbers are {x,z}. Of course {y,z} could be the solution as well. Long story short every S with 1 element only will always get 'no' as an answer and you won't learn anything.

[SteelCamel]

Yes, I realised that after I posted! If I ask about a subset containing only one number, you can just say "no" constantly because at least one of your numbers isn't in my subset. For subsets of two and above, you can follow the previously-described strategy to stop me getting down to the right numbers (and I could ask about the empty set, but I already know you'd say "no" so there's no point!).

[MartianInvader]

Cool puzzle! How about the following generalization: Instead of thinking of 2 numbers, you think of 3? Or m for some arbitrary m < N? And the adversary still chooses any of them to answer with when given a subset, but the guesser wins if the final guess is any of the secret numbers.

I think I've worked out the answers to the main question and the follow-up for arbitrary m.

[Poker]

I think I've got it:

Spoiler:

Let the players be called the Picker, who chooses the numbers, and the Guesser, who makes the guesses.

Let the Picker's strategy be as follows: Select an arbitrary finite projective plane (of order m-1) over m^2-m+1 points (assume N is sufficiently large for the Picker to do this), and never let any of the lines of this projective plane be eliminated (For example, for m=3, if the Picker's numbers are {1,2,3} the Picker may choose the Fano plane with lines {1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}). Since any two lines of the projective plane intersect, at most one of a guess and its inverse will contain as a subset one or more of these lines. Therefore, it is always possible for the Picker to prevent all lines of the selected projective plane from being eliminated.

As for the Guesser, it will always be possible for the Guesser to limit the possibilities to only the projective plane, for it is always possible for the Guesser to eliminate one of two mutually-exclusive sets, and any set of m points that it outside the projective plane cannot share points with all of its lines. After all, each point is only incident on m lines, but every pair of points share a line, so the absolute maximum number of lines a set can share points with is m^2-m+1, and while that is exactly the number of lines in the projective plane, it would require the m selected points to all be on the same line (if points a, b, and c aren't, then c would only add m-2 lines, which would not be enough to cover all of the lines), but then the set must be in the projective plane. So the Guesser can limit the possibilities to the projective plane, but can go no further. At that point, the guesser only has a m/(m^2-m+1) probability of victory.

Intuitively this feels like the optimal strategy, but I can't figure out a proof that it is.

[MartianInvader]

Still reading through the second half of your solution, but had a question on this:

Spoiler:

...for it is always possible for the Guesser to eliminate one of two mutually-exclusive sets...

I don't see why this needs to be true (and if true it seems like it solves the whole problem on its own). Did you mean

Spoiler:

if one of the two mutually-exclusive sets contains the projective plane? But then I think you need to figure out how to identify what the chosen projective plane is.

[Poker]

Still reading through the second half of your solution, but had a question on this:

Spoiler:

...for it is always possible for the Guesser to eliminate one of two mutually-exclusive sets...

I don't see why this needs to be true (and if true it seems like it solves the whole problem on its own). Did you mean

Spoiler:

if one of the two mutually-exclusive sets contains the projective plane? But then I think you need to figure out how to identify what the chosen projective plane is.

What I mean is:

Spoiler:

The Guesser begins with every subset of size m of the set of numbers as a possibility. If there are two such subsets {a₁, a₂, ..., a_m} and {b₁, b₂, ..., b_m} of which their elements are mutually exclusive, the guesser may eliminate one set or the other from the list of possibilities, with a guess that includes every a_i but excludes every b_i.

[MartianInvader]

Spoiler:

The Guesser begins with every subset of size m of the set of numbers as a possibility. If there are two such subsets {a₁, a₂, ..., a_m} and {b₁, b₂, ..., b_m} of which their elements are mutually exclusive, the guesser may eliminate one set or the other from the list of possibilities, with a guess that includes every a_i but excludes every b_i.

Spoiler:

I guess I'm still confused. Maybe an example would help me understand?

Say N = 10, m = 3, and the secret numbers are 1,2 and 3. Then the sets {1, 5, 6} and {2, 7, 8} are mutually exclusive, so you say we should make a guess that contains the entire first set but none of the second, let's say {1, 4, 5, 6}. The picker then answers "no" (which is allowed since two of the secret numbers are outside the set).

What set can the guesser then eliminate, and why?

[Poker]

Spoiler:

The Guesser begins with every subset of size m of the set of numbers as a possibility. If there are two such subsets {a₁, a₂, ..., a_m} and {b₁, b₂, ..., b_m} of which their elements are mutually exclusive, the guesser may eliminate one set or the other from the list of possibilities, with a guess that includes every a_i but excludes every b_i.

Spoiler:

I guess I'm still confused. Maybe an example would help me understand?

Say N = 10, m = 3, and the secret numbers are 1,2 and 3. Then the sets {1, 5, 6} and {2, 7, 8} are mutually exclusive, so you say we should make a guess that contains the entire first set but none of the second, let's say {1, 4, 5, 6}. The picker then answers "no" (which is allowed since two of the secret numbers are outside the set).

What set can the guesser then eliminate, and why?

Spoiler:

The Guesser can eliminate {1,5,6}. If the Picker had {1,5,6} as their set, a "no" answer would be impossible, since all of {1,5,6} were in the guess.

I think my wording earlier regarding elimination might have been confusing. We do not eliminate the numbers themselves - what we are eliminating is specific sets of numbers from a list of sets. So for your example, we would start with a list of sets {1,2,3}, {1,2,4}, {1,2,5}, ... {8,9,10}, and the guess and response would remove the sets {1,4,5}, {1,4,6}, {1,5,6}, and {4,5,6} from that list, while leaving alone sets such as {1,2,3}, {1,4,9}, and so on.

[MartianInvader]

Ah, I was confused by how you were using the word "eliminate". I understand your argument now, and realize that when I though I had solved the general case, I had gotten it wrong, and you are indeed correct! You get a smarter-than-MartianInvader badge. I'm going to try to rephrase your solution in a slightly simpler way, tell me if I'm misrepresenting it:

Spoiler:

Rename the numbers so the secret numbers are 1, 2, and 3. The Picker then says "yes" to any set that contains one of the triples {1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}. For any two numbers, you can find a permutation of {1,2,3,4,5,6,7} that swaps those numbers and preserves that set of 7 sets, so there's no way to distinguish between the real secret numbers and the others. The Guesser CAN reduce the possibilities down to those 7 points, since they are the only triples with "yes" answers. So the Guesser has a 3/7 chance of victory.

For the case of m, you choose your points to be the lines in a finite projective plane, which gives an m / (m^2 - m + 1) chance of victory to the guesser.

My approach was basically the same as yours, but

Spoiler:

I didn't realize we were dealing with a finite projective plane. I figured out the right sets for m=3 and proved they worked with a symmetry argument, but I tried to generalize it in a purely combinatorial way and got the wrong answer.

I *think* I can prove that this is optimal, but I'm going to think it through very carefully this time before claiming so

[Poker]

Yeah, that's my solution.

Spoiler:

I realized that since the Picker could not preserve two m-tuples of points that are mutually-exclusive, every pair of m-tuples in the set of m-tuples the Picker preserves have to share at least one point. My intuition was that in order to spread out the m-tuples as much as possible, any two should share exactly one point, which led me to finite projective planes.

Let's see if I can prove it is optimal for m=3... I think I have it.

Spoiler:

In order for every number to have probability <3/7, there must be at least 8 numbers.

Consider the set of triples that the Picker preserves. (Each triple will be selected by the Picker to be the secret numbers with some probability, not necessarily equal.) Assume that the probability of every number being among the secret numbers is less than 3/7, and the set contains the triple {1,2,3}. Let p₁₂₃ be the probability that the Picker's secret numbers are 1, 2, and 3, and for other combinations of 1, 2, and 3, replace the corresponding missing numbers with X's (so, for example, the probability that 1 is among the secret numbers but not 2 or 3 is p_1XX). Now, we have (A) p_XXX=0, since {1,2,3} has nonzero probability. We also have (B) p_1XX+p_12X+p_1X3+p₁₂₃<3/7, and (C) p_X2X+p_12X+p_X23+p₁₂₃<3/7, and (D) p_XX3+p_1X3+p_X23+p₁₂₃<3/7. Since (E) the sum of all 8 probabilities is 1, we can add A, B, C, and D, and subtract E, to get (F) p_12X+p_1X3+p_X23+2*p₁₂₃<2/7. Since all probabilities are nonnegative, this means (G) p₁₂₃<1/7. This is true for any possibility, so every triple occurs with probability less than 1/7. Keep this in mind.

If we take equation E and subtract A and B, we get (H) p_X2X+p_XX3+p_X23>4/7. Doing the same but replacing B with C or D gives us (I) p_1XX+p_XX3+p_1X3>4/7 and (J) p_1XX+p_X2X+p_12X>4/7. From these equations, and the fact that all probabilities are non(edit: what's wrong with me for forgetting the non here?)negative, we can deduce (K) p_1XX>1/7, (L) p_X2X>1/7, and (M) p_XX3>1/7. Since every triple occurs with probability less than 1/7, we can deduce that for any element of any triple, there are at least two triples that share only that element with the original triple. Now keep this in mind.

Now, suppose that along with {1,2,3} we have some triple that shares two numberswith it, letting it be {1,2,4}. Then there are at least two triples that contain 3 but not 1 or 2, and since they do not contain 1 or 2 they must contain 4 as well. Let these two triples be {3,4,5} and {3,4,6}. Then there are at least two triples that contain 5 but not 3 or 4, and since they do not contain 3 or 4 they must contain 6 as well. Furthermore, each must contain at least one of 1 or 2, so they must be {1,5,6} and {2,5,6}. Now consider a triple including 7. If it lacks 1 and 2 then it contains 3 and 4, but then it is mutually exclusive with {1,5,6}. Therefore it contains 1 or 2, and it also contains 3 or 4, but then it lacks 5 and 6, and then whichever of 1 or 2 it lacks, it is mutually exclusive with {1,5,6} or {2,5,6}. Therefore, there cannot be any triples involving any numbers except these six, but there must be at least 8 numbers. Therefore, no two triples share any numbers. This gives us (N) p_12X=p_1X3=p_X23=0.

Taking N into account with B, C, D, and G, we get (O) p_1XX>2/7, (P) p_X2X>2/7, and (Q) p_XX3>2/7. Therefore, there must be at least three triples that contain 1 but not 2 or 3, and furthermore none of them share any elements other than 1. Let these triples be {1,4,5}, {1,6,7}, and {1,8,9}. But there must also be a triple that contains 2 but not 1 or 3 (in fact there are at least three of them), so it must contain either 4 or 5, and either 6 or 7, and either 8 or 9, but that is impossible since it's only a triple. Therefore, this entire situation, where every number has probability <3/7, is impossible.

I'm sure there's a more elegant proof somewhere.

Edited a typo.

[MartianInvader]

So it turns out I don't have a proof of optimality; I was making an assumption about the form of the solution that it turns out I can't easily prove.

I'm not (yet) convinced your argument works, though - I'm stuck here:

Spoiler:

From these equations, and the fact that all probabilities are negative, we can deduce (K) p1XX>1/7, (L) pX2X>1/7, and (M) pXX3>1/7

Can you explain how you make this assumption and deduction?

[Poker]

I'm not (yet) convinced your argument works, though - I'm stuck here:

Spoiler:

From these equations, and the fact that all probabilities are negative, we can deduce (K) p1XX>1/7, (L) pX2X>1/7, and (M) pXX3>1/7

Can you explain how you make this assumption and deduction?

Sure, no problem.

Spoiler:

Adding together equations I and J gives us 2*p_1XX+p_X2X+p_XX3+p_12X+p_1X3>8/7. Subtracting E from this gives us p_1XX-p_X23-p₁₂₃>1/7, or p_1XX>1/7+p_X23+p₁₂₃. Since every p is nonnegative, this leads to p_1XX>1/7. The same argument follows for the other two numbers.

As for the assumption... I'm not really sure what assumption you're referring to. The one that all the numbers are nonnegative? Remember, I defined all these p variables to be probabilities.

Edit: To avoid a double-post, I will post a partial conversion of my reasoning for the m=3 case in an attempt to apply it to the general case. As you can see I don't get very far, but maybe it will inspire somebody else.

Spoiler:

Assume that every number occurs with probability <m/(m²-m+1). Assume there is some preserved m-tuple {1,2,...,m}. Then adding together the probabilities as I did in my previous argument, the sum of every probability that exactly one number is in the m-tuple, plus twice the sum of every probability that exactly two numbers are in the m-tuple, plus ... plus m times the probability that every number is in the m-tuple, is less than m²/(m²-m+1). Subtracting 1 from each side gives us this: m-1 times the probability that every number is in the m-tuple, plus some other terms, is less than (m-1)/(m²-m+1). In other words, for any given m-tuple, the probability that m-tuple is selected is less than 1/(m²-m+1).

Now, the probability that 1 is not in the m-tuple is >(m²-2m+1)/(m²-m+1). Same for the probability that 2 is not in the m-tuple, and so on for every number in the preserved m-tuple. Summing together the amounts for m-1 of those numbers gives us (m-1)³/(m²-m+1). Comparing the numerator and the denominator, we find that when we take (m-1)³ and subtract (m-2)(m²-m+1), we get m³-3*m²+3*m-1-m³+m²-m+2*m²-2*m+2 which simplifies to 1, meaning the fraction is greater than (m-2). Now, any m-tuple that shares 2 or more numbers with the preserved m-tuple would contribute only m-2 times its probability, at most. Therefore, the probability of the actual m-tuple sharing only a single particular number with the preserved m-tuple is >1/(m²-m+1). In other words, given any number in any preserved m-tuple, there are at least two m-tuples that share only that number with it.

That's as far as I got.

[MartianInvader]

Actually, I was referring to the claim that

Spoiler:

all probabilities are negative. I though I was misunderstanding how you were using "probability" like I misunderstood how you were using "eliminate"
earlier.

But after reading your response, I'm assuming that was a typo.

[Poker]

Yeah, it was. Fixed it.