Two secrets

[operator[]]

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.

Now, finding both of my numbers may be difficult -- for instance, I could choose to always answer for x, making it impossible to find y. So I will give you a slightly easier task: can you find a set of size 2 that contains at least one of them?

How many questions do you need? If I just had one secret you could halve the candidate set in each step, getting roughly log N questions. Is it possible to do similarly well with two secrets?

[Schrödinger's Wolves]

Edit of a solution post which misread the question and was therefore wrong. It wouldn't let me delete the post.

[Sabrar]

Thinking out loud, not full or best solution Not even correct solution as was pointed out below

Spoiler:

Divide {1..N} into p equal (or close to equal) subsets of size N/p each. Asking for each subset individually at most 2 will get 'yes' as answer. Therefore with p questions we can reduce the number of possibilities by a factor of at least 2/p. Progress per question seems best in case of p in {5;6}. This gives us a rough estimate of 6*log₃N or 5*log_2.5N

[Schrödinger's Wolves]

I don't know yet what the optimal solution is, but one comment I have is that if you are only trying to prevent me from having a subset of 2 with at least one being a solution, then I can find both secrets, because you will never reply 'yes' to any subset of 2 unless it has both secrets in it.

[Schrödinger's Wolves]

Spoiler:

Therefore with p questions we can reduce the number of possibilities by a factor of at least 2/p.

Spoiler:

It is possible for one of your subsets to contain just one of his secrets and for him to still reply "false". He can choose which secret to reply with. It is therefore possible that all of your subsets will be answered with "False" and being answered "false does not make it impossible that an interval contains one of the secrets.

[Soupspoon]

Far non-optimal solution (not even sure it needs a spoiler, but here it is) might be to:

Spoiler:

Ask about set {a,b} and then {1..N}\{a,b} for every distinct a,b pairing (loop-within-loop as: a=1..N-1; b=a+1..N), until you get the answer to the first question to be identical to the answer to the second question. Then you can declare {a,b} as your "answer".

A more complicated (and not yet tied down to precise method, but should scale better) derivative of this, with better explanation of the logic than above, is perhaps:

Spoiler:

Run through paired questions for subset S₁ and subset S₂, where at each stage S₂ is the complement of S₁ of roughly half of all "interesting" numbers, which is itself permuted accordingly for every new stage in a more refined (e.g. binary splitting) method of demarcation.

Getting answer pairs, for the question pairs, of:
false+false: means that x must be in the "y answered" half and vice versa, as there was never a compulsion to answer "true". Use this to alter your k-dimensional tree for the future (bisect each S and mix-and-match halves in subsequent rounds, looking for more false+false answers, at the expense of many useless questions).
true+true: exactly as much (and as little) information false+false, only 'reversed'. The adversarial respondent will doubtless avoid this trap, at first (first question of the first complementary pair, they won't want you to discard the non-included 'y' on the way to hunting the included 'x'), but once they see your tactic there's no reason to favour false (to be followed be the complimentary false) rather than true (to be followed by the other true), so again you can use this to prove two halves (or the two quarters that have been rematched) still retain one number each. You can stop before finding all the information, if at least one number is now in a 'quarter'/'eighth'/'sixteenth'/whatever of at most two digits in size, and declare that.
false+true/true+false: the split returning the truth means less than it should, as it will take more work to extricate "one or both are in this set" by future questions, than I feel is worth it.

But there's more work needed to perfect all this, certainly. Just that if you can't trick the adversary into providing a premature "true", your next bet seems to be into making them as susceptible to the forced "false".

[Cauchy]

For N = 3, any two-element subset will work. 0 questions.
For N = 4, ask about any two-element subset. If the answer is "yes", you have it; if the answer is "no", then its complement works. 1 question.
For N = 5, asking about 0, 1, 4, or 5-element subsets is fruitless (since the secret-holder can always answer "no", "no", "yes", and "yes", respectively), and asking about a 3-element subset is the same as asking about its complement (since whatever the answer is for a set, the answer would be the opposite for the complement). So you should only ask about 2-element subsets. Then, adversarially, the secret-holder will answer "no" unless you stumble across the exact two secrets. In the worst case, this is 10 questions.
For N = 6, it necessarily requires at least 10 questions since the secret-holder could just pick the secret from among {1, 2, 3, 4, 5} and employ the same strategy as in N = 5. On the other hand, it can't require a full 15 questions, since by asking about {1, 2, 3} you weed out three two-element subsets (either {1, 2}, {1, 3} and {2, 3}; or {4, 5}, {4, 6}, and {5, 6} are eliminated as being the two secrets depending on what answer is given for {1, 2, 3}). If WLOG {1, 2, 3} returns a "no", then I can ask about {1, 2, 4}, {1, 2, 5} and {1, 2, 6} which I believe eliminates another six (at least) two-element subsets as being the pair of secrets no matter what the answers are. After that I ask about the other six two-element subsets, again needing 10 questions in total. It feels weird to me that the answers for N = 5 and N = 6 would be the same, though, so I probably messed something up.

As an aside, if my secrets are {a, b} then I can pretend my secrets are {a, c} by answering for (a in S) whenever (b in S) and (c in S) are different. This makes it extra-hard to pin down a two-element subset that contains one of the elements, as any answer without a, other than {b, c}, could be wrong. This doesn't show that the secret-holder can force you to have to name the two secrets, but I suspect that that might be the case.

[Poker]

For N = 5, asking about 0, 1, 4, or 5-element subsets is fruitless (since the secret-holder can always answer "no", "no", "yes", and "yes", respectively), and asking about a 3-element subset is the same as asking about its complement (since whatever the answer is for a set, the answer would be the opposite for the complement). So you should only ask about 2-element subsets. Then, adversarially, the secret-holder will answer "no" unless you stumble across the exact two secrets. In the worst case, this is 10 questions.
For N = 6, it necessarily requires at least 10 questions since the secret-holder could just pick the secret from among {1, 2, 3, 4, 5} and employ the same strategy as in N = 5. On the other hand, it can't require a full 15 questions, since by asking about {1, 2, 3} you weed out three two-element subsets (either {1, 2}, {1, 3} and {2, 3}; or {4, 5}, {4, 6}, and {5, 6} are eliminated as being the two secrets depending on what answer is given for {1, 2, 3}). If WLOG {1, 2, 3} returns a "no", then I can ask about {1, 2, 4}, {1, 2, 5} and {1, 2, 6} which I believe eliminates another six (at least) two-element subsets as being the pair of secrets no matter what the answers are. After that I ask about the other six two-element subsets, again needing 10 questions in total. It feels weird to me that the answers for N = 5 and N = 6 would be the same, though, so I probably messed something up.

I think what you forgot in your analysis of these is that you don't need to get both numbers - you only need to be sure you have at least one. I'm a little surprised it slipped out of your grasp - you were aware of that fact for N = 3 and N = 4...

In truth, N = 5 should require only 3 questions. It's true that adversarially the secret-holder will always answer "no" to a 2-element question if possible (otherwise, guessing those 2 elements will guarantee at least one is in the set), but if you strategically ask about, let's say, {1, 2}, {1, 3}, and {2, 3}, and get a "no" answer every time, then my guess {4, 5} will always contain at least one of the two.

As for N = 6, assume WLOG {1, 2, 3} returns a "yes" ("no" also works; this is just how my mind naturally drifts). If I then ask {1, 2, 4} and get a "yes", either 1 is in it, 2 is in it, or it is {3, 4}, so I then ask {3, 4} - if "yes" that's my guess, if "no then {1, 2} is my guess. Either way, that's only three questions. But if I ask {1, 2, 4} and get a "no", then either 3 is in it with any number, or one number is either 1 or 2 and the other is either 5 or 6. In that case, my third question is {1, 2, 5}. If it's a "no" then {1, 5} and {2, 5} are both out, so {3, 6} is my guess. If it's a "yes" then {3, 4} and {3, 6} are out, so I ask {3, 5} for my fourth and final question. A "yes" lets me guess {3, 5} while a "no" lets me guess {1, 2} (which, even though I know is not the correct pair, must contain at least one number of the true pair). All in all, I need 4 questions for the N = 6 case.

In any case, it's relatively easy to prove that it is always possible to eventually find a pair that gets at least one number right, though my proof is nonconstructive:

Spoiler:

Suppose after a number of questions you reach a point where no further questions can eliminate any more pairs. Guessing aside, this is guaranteed to happen, as there are a finite number of pairs. Let P be the set of all pairs that cannot be eliminated. P is not empty, since at least one pair is the true answer and cannot be eliminated. WLOG let (1, 2) be in P. P cannot contain any pairs that contain neither 1 nor 2, for if P did have such a pair, the question {1, 2} would either eliminate (1, 2) or it would eliminate the pair that contains neither 1 nor 2 - but that would mean P must contain a pair that will be eliminated, which is a contradiction. Therefore, every pair in P contains either 1 or 2 (or both), and so the guess {1, 2} is a winning guess.

[sfwc]

This method gets the number of questions down to a constant multiple of log(N)^4:

Spoiler:

The plan is to find a collection of subsets such that, for any 4 distinct numbers (a,b,c,d) in 1…N at least one of the sets contains both a and b but neither c nor d. After asking about each of these sets we’ll be able to find a suitable pair. This is because, letting P be the set of pairs which have not yet been eliminated, P does not contain 2 disjoint pairs (it cannot contain both {a,b} and {c,d} with all of a, b, c and d distinct since the question about the set containing a and b but neither c nor d eliminates either {a,b} or {c,d}). So any element of P will contain at least one of x or y.

To obtain a suitable collection of subsets, we sort the numbers according to the values of particular collections of digits. More precisely, let k be the number of digits of N. We view each number in 1…N as a sequence of k digits, padding on the left with zeroes if necessary. For any numbers g,h,i,j in 1..k and any set T of sequences of 4 digits, we let S(g,h,i,j,T) be the set of all those numbers in 1…N such that the sequence given by the gth, hth, ith and jth digits of that number is in T. The sets we ask about are the ones which can be built in this way. It is clear that there are only constant*log(N)^4 many of them.

So we just have to show that for any distinct a, b, c and d we can find g, h, i, j and T with a and b but neither c nor d in S(g,h,i,j,T). Let g be the position of any digit where a and c differ, h the position of a digit where a and d differ, i the position of a digit where b and c differ and j the position of a digit where b and d differ. Let T be the set containing just 2 sequences, the first consisting of the gth, hth, ith and jth digits of a and the second of the gth, hth, ith and jth digits of b. It is clear that these values for g,h,i,j and T work.

[Yat]

Spoiler:

So we just have to show that for any distinct a, b, c and d we can find g, h, i, j and T with a and b but neither c nor d in S(g,h,i,j,T). Let g be the position of any digit where a and c differ, h the position of a digit where a and d differ, i the position of a digit where b and c differ and j the position of a digit where b and d differ. Let T be the set containing just 2 sequences, the first consisting of the gth, hth, ith and jth digits of a and the second of the gth, hth, ith and jth digits of b. It is clear that these values for g,h,i,j and T work.

How can we process the cases where the four numbers all differ at the same digit and are otherwise identical?

[Poker]

Spoiler:

So we just have to show that for any distinct a, b, c and d we can find g, h, i, j and T with a and b but neither c nor d in S(g,h,i,j,T). Let g be the position of any digit where a and c differ, h the position of a digit where a and d differ, i the position of a digit where b and c differ and j the position of a digit where b and d differ. Let T be the set containing just 2 sequences, the first consisting of the gth, hth, ith and jth digits of a and the second of the gth, hth, ith and jth digits of b. It is clear that these values for g,h,i,j and T work.

How can we process the cases where the four numbers all differ at the same digit and are otherwise identical?

Spoiler:

I don't see why that's a problem - g, h, i, and j would all be the same, and the members of T would all have four repeated digits.

[Xias]

In truth, N = 5 should require only 3 questions. It's true that adversarially the secret-holder will always answer "no" to a 2-element question if possible (otherwise, guessing those 2 elements will guarantee at least one is in the set), but if you strategically ask about, let's say, {1, 2}, {1, 3}, and {2, 3}, and get a "no" answer every time, then my guess {4, 5} will always contain at least one of the two.

Am I mistaken, or does (2, 6) lead to a failure here? Secret-holder can still say "no" to all three of {1, 2}, {1, 3}, and {2, 3}, but 4 and 5 are not true either.

[Poker]

In truth, N = 5 should require only 3 questions. It's true that adversarially the secret-holder will always answer "no" to a 2-element question if possible (otherwise, guessing those 2 elements will guarantee at least one is in the set), but if you strategically ask about, let's say, {1, 2}, {1, 3}, and {2, 3}, and get a "no" answer every time, then my guess {4, 5} will always contain at least one of the two.

Am I mistaken, or does (2, 6) lead to a failure here? Secret-holder can still say "no" to all three of {1, 2}, {1, 3}, and {2, 3}, but 4 and 5 are not true either.

We're in the N = 5 case. What is this "6" you refer to?

[Xias]

Oh, that was silly of me.

[Yat]

Spoiler:

So we just have to show that for any distinct a, b, c and d we can find g, h, i, j and T with a and b but neither c nor d in S(g,h,i,j,T). Let g be the position of any digit where a and c differ, h the position of a digit where a and d differ, i the position of a digit where b and c differ and j the position of a digit where b and d differ. Let T be the set containing just 2 sequences, the first consisting of the gth, hth, ith and jth digits of a and the second of the gth, hth, ith and jth digits of b. It is clear that these values for g,h,i,j and T work.

How can we process the cases where the four numbers all differ at the same digit and are otherwise identical?

Spoiler:

I don't see why that's a problem - g, h, i, and j would all be the same, and the members of T would all have four repeated digits.

But then how do you build the set, and how would it allow you to separate a and b form c and d? Would you care to give an example of the different steps of the process? I thought I had a vague understanding of this method, but now I apparently don't.

EDIT: I finally figured it out. I did not understand the second paragraph correctly. Sorry.

[Poker]

I just realized we can improve sfwc's method to only require O(log(N)^3) questions:

Spoiler:

If any of g, h, i, and j are the same, we can get rid of a duplicate, and reduce the lengths of the sequences in T accordingly, with no change. For example, if i and j are the same, we can get rid of j, remove the last digit from each member of T, and still wind up with the same set. So as long as we can, given any a, b, c, and d, choose g, h, i, and j such that at least two of them are the same, we can get rid of a duplicate, and thus get rid of a variable. All we have to do is prove this is always possible for any a, b, c, and d, and we will have reduced the number of needed place variables from 4 to 3, and thus reduced the power to which log(N) is raised from 4 to 3.

Now, given any a, b, c, and d, and any digit place g, it is impossible for a and c to differ in place g, while simultaneously a and d are the same, b and c are the same, and b and d are the same (since being same is transitive). Therefore, whatever g we pick for where a and c differ, we will be able to pick one of the other places (either h, i, or j) to be equal to g. Therefore, given any a, b, c, and d, we can always choose g, h, i, and j such that at least two of them are the same.

Incidentally, we cannot reduce it further using this method - for example, let a=001, b=100, c=101, d=011. The only place where a and c differ, the only place where a and d differ, and the only place where b and c differ are all different places, so 3 place variables are required. If we want to reduce the number of questions to fewer than O(log(N)^3), we would need to use a more in-depth modification than this one.

[Nitrodon]

I think I have an O(log(N)) solution.

Spoiler:

Let A initially be {1, 2, 3, ..., N-1}. At all times, we know that at least one of the numbers is in A.

Divide A into three roughly equal sets A₁, A₂, and A₃, and ask about A₁ ∪ A₂, A₁ ∪ A₃, and A₂ ∪ A₃. If we get a "yes" response to one of these questions, take that set as the new value of A. Repeat until either |A| = 2 or all three sets get a "no" response. If |A| = 2, we are done. Otherwise, we know that A cannot contain both numbers. Let B initially be the complement of A.

At this point, we know that one of the numbers is in A, and the other number is in B. Divide A into two halves A₁ and A₂, and B into two halves B₁ and B₂. Ask about A₁ ∪ B₁ and A₁ ∪ B₂. There are four possible responses:

(yes, yes) -> One of the numbers is in A₁ (and the other is in B).
(yes, no) -> One of the numbers is in B₁ (and the other is in A).
(no, yes) -> One of the numbers is in B₂ (and the other is in A).
(no, no) -> One of the numbers is in A₂ (and the other is in B).

In all cases, we have halved the size of either A or B. Repeat until one of them has size 1 or 2.

Both parts of this procedure take O(log N) steps, so the entire procedure is O(log N).

[Yat]

I think I have an O(log(N)) solution.

Spoiler:

Let A initially be {1, 2, 3, ..., N-1}. At all times, we know that at least one of the numbers is in A.

Divide A into three roughly equal sets A₁, A₂, and A₃, and ask about A₁ ∪ A₂, A₁ ∪ A₃, and A₂ ∪ A₃. If we get a "yes" response to one of these questions, take that set as the new value of A. Repeat until either |A| = 2 or all three sets get a "no" response. If |A| = 2, we are done. Otherwise, we know that A cannot contain both numbers. Let B initially be the complement of A.

At this point, we know that one of the numbers is in A, and the other number is in B. Divide A into two halves A₁ and A₂, and B into two halves B₁ and B₂. Ask about A₁ ∪ B₁ and A₁ ∪ B₂. There are four possible responses:

(yes, yes) -> One of the numbers is in A₁ (and the other is in B).
(yes, no) -> One of the numbers is in B₁ (and the other is in A).
(no, yes) -> One of the numbers is in B₂ (and the other is in A).
(no, no) -> One of the numbers is in A₂ (and the other is in B).

In all cases, we have halved the size of either A or B. Repeat until one of them has size 1 or 2.

Both parts of this procedure take O(log N) steps, so the entire procedure is O(log N).

I don't think it can work like this. I've tried this type of approach and came to a solution that is much more complex (it needs to be clarified a lot before posting). I get the exact same thing for the second part, but...

Spoiler:

The problem is with the first part. In your explanation, you handle the simple cases when there is no more than one yes, but what do you do if you have two or three?

[Yat]

Ok, I took a chance to work on my solution again, even if now it is just a correction of Nitrodon's solution, but here is where I landed:

Spoiler:

Let the initial state be state I, where we have one set containing both numbers.
We cut the set in n parts and test every pair of parts.
If there is only one yes, each part of the pair contains one secret, we can skip to state III.
If there is more, you need to take a look at the results, it either allows us to skip to state III, or at least allow us to isolate one group of parts that contains at least one secret, and go to state II.
Chosing n will depend on N and the expected behaviour of the other guy, but for this specific solution to work, it needs to be at least 4. So if the set we have here contains 4 elements or less, just test all the pairs until you get a yes and win.

State II is when you have one set A that contains at least one secret and one set B that contains at most one secret (and the implicit set C that does not contain any secret). If A has only two elements, you won. If B has only one element, well... I think the best option is to get back to state I with AUB.
If it hasn't been done yet, you can ask about A alone for a chance to get a skipping-to-state-III no. Then cut each set in half (A1, A2, B1 and B2), and test every A,B pair. Now there are a few possible outcomes:
-zero yes. A1 and A2 both contain one secret, skip to III.
-one yes. The subset of B that is not implied is empty. Put it in C and start a new state II.
-two yes with the same subset of A. The other subset of A is moved into B, state II again.
-two yes with the same subset of B. The other subset of B is empty. Put it in C and start a new state II.
-three yes. The subset of B that is not implied is empty. Put it in C and start a new state II.
-four yes. A1 and A2 both contain one secret, skip to III.

State III is when you have two sets, each one containing a secret. I got the same as in Nitrodon's original solution.

[jaap]

I think I have an O(log(N)) solution.

Spoiler:

Let A initially be {1, 2, 3, ..., N-1}. At all times, we know that at least one of the numbers is in A.

Divide A into three roughly equal sets A₁, A₂, and A₃, and ask about A₁ ∪ A₂, A₁ ∪ A₃, and A₂ ∪ A₃. If we get a "yes" response to one of these questions, take that set as the new value of A. Repeat until either |A| = 2 or all three sets get a "no" response. If |A| = 2, we are done. Otherwise, we know that A cannot contain both numbers. Let B initially be the complement of A.

At this point, we know that one of the numbers is in A, and the other number is in B. Divide A into two halves A₁ and A₂, and B into two halves B₁ and B₂. Ask about A₁ ∪ B₁ and A₁ ∪ B₂. There are four possible responses:

(yes, yes) -> One of the numbers is in A₁ (and the other is in B).
(yes, no) -> One of the numbers is in B₁ (and the other is in A).
(no, yes) -> One of the numbers is in B₂ (and the other is in A).
(no, no) -> One of the numbers is in A₂ (and the other is in B).

In all cases, we have halved the size of either A or B. Repeat until one of them has size 1 or 2.

Both parts of this procedure take O(log N) steps, so the entire procedure is O(log N).

I don't think it can work like this. I've tried this type of approach and came to a solution that is much more complex (it needs to be clarified a lot before posting). I get the exact same thing for the second part, but...

Spoiler:

The problem is with the first part. In your explanation, you handle the simple cases when there is no more than one yes, but what do you do if you have two or three?

I don't see what the problem is.

Spoiler:

During the first stage of Nitro's solution there is the set A, which contains at least one of the numbers, and its complement B that contains at most one.
At the very start A is the full set (with both numbers) and B is empty (with neither).
So you trisect A, and ask about A₁ ∪ A₂, A₁ ∪ A₃, and A₂ ∪ A₃.
If any one of those answers is yes, you know that at least one of the numbers is in that union you asked about.
So you can take any of those unions for which the answer was yes as the new definition of A.
As long as there is at least one yes answer, you can reduce the size of A by a third and still be sure it has at least one of the numbers in it.
When there are three no answers, then you know that you cannot have both numbers in A. You know (the untrisected) A still contains one of them however.
So now you are in the situation that A and B both have exactly one of the numbers, and you can go into stage two of Nitro's solution.

[Yat]

I think I have an O(log(N)) solution.

Spoiler:

Let A initially be {1, 2, 3, ..., N-1}. At all times, we know that at least one of the numbers is in A.

Divide A into three roughly equal sets A₁, A₂, and A₃, and ask about A₁ ∪ A₂, A₁ ∪ A₃, and A₂ ∪ A₃. If we get a "yes" response to one of these questions, take that set as the new value of A. Repeat until either |A| = 2 or all three sets get a "no" response. If |A| = 2, we are done. Otherwise, we know that A cannot contain both numbers. Let B initially be the complement of A.

At this point, we know that one of the numbers is in A, and the other number is in B. Divide A into two halves A₁ and A₂, and B into two halves B₁ and B₂. Ask about A₁ ∪ B₁ and A₁ ∪ B₂. There are four possible responses:

(yes, yes) -> One of the numbers is in A₁ (and the other is in B).
(yes, no) -> One of the numbers is in B₁ (and the other is in A).
(no, yes) -> One of the numbers is in B₂ (and the other is in A).
(no, no) -> One of the numbers is in A₂ (and the other is in B).

In all cases, we have halved the size of either A or B. Repeat until one of them has size 1 or 2.

Both parts of this procedure take O(log N) steps, so the entire procedure is O(log N).

I don't think it can work like this. I've tried this type of approach and came to a solution that is much more complex (it needs to be clarified a lot before posting). I get the exact same thing for the second part, but...

Spoiler:

The problem is with the first part. In your explanation, you handle the simple cases when there is no more than one yes, but what do you do if you have two or three?

I don't see what the problem is.

Spoiler:

During the first stage of Nitro's solution there is the set A, which contains at least one of the numbers, and its complement B that contains at most one.
At the very start A is the full set (with both numbers) and B is empty (with neither).
So you trisect A, and ask about A₁ ∪ A₂, A₁ ∪ A₃, and A₂ ∪ A₃.
If any one of those answers is yes, you know that at least one of the numbers is in that union you asked about.
So you can take any of those unions for which the answer was yes as the new definition of A.
As long as there is at least one yes answer, you can reduce the size of A by a third and still be sure it has at least one of the numbers in it.
When there are three no answers, then you know that you cannot have both numbers in A. You know (the untrisected) A still contains one of them however.
So now you are in the situation that A and B both have exactly one of the numbers, and you can go into stage two of Nitro's solution.

thanks for the clarification. I was stuck on reducing the sets as quickly as possible, but removing one third with three questions not only works, it is also probably faster than multiplying questions to improve the ratio.