Two secrets
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 155
 Joined: Mon May 18, 2009 6:11 pm UTC
 Location: Stockholm, Sweden
Two secrets
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?
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?

 Posts: 14
 Joined: Fri Mar 24, 2017 3:28 am UTC
Re: Two secrets
Edit of a solution post which misread the question and was therefore wrong. It wouldn't let me delete the post.
Last edited by Schrödinger's Wolves on Tue Mar 28, 2017 3:03 pm UTC, edited 1 time in total.
Re: Two secrets
Spoiler:
Last edited by Sabrar on Tue Mar 28, 2017 3:26 pm UTC, edited 1 time in total.

 Posts: 14
 Joined: Fri Mar 24, 2017 3:28 am UTC
Re: Two secrets
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.

 Posts: 14
 Joined: Fri Mar 24, 2017 3:28 am UTC
Re: Two secrets
Sabrar wrote:Spoiler:
Spoiler:
 Soupspoon
 You have done something you shouldn't. Or are about to.
 Posts: 2963
 Joined: Thu Jan 28, 2016 7:00 pm UTC
 Location: 531
Re: Two secrets
Far nonoptimal solution (not even sure it needs a spoiler, but here it is) might be to:
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:
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".
Spoiler:
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:
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".
Re: Two secrets
For N = 3, any twoelement subset will work. 0 questions.
For N = 4, ask about any twoelement 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 5element subsets is fruitless (since the secretholder can always answer "no", "no", "yes", and "yes", respectively), and asking about a 3element 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 2element subsets. Then, adversarially, the secretholder 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 secretholder 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 twoelement 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) twoelement subsets as being the pair of secrets no matter what the answers are. After that I ask about the other six twoelement 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 extrahard to pin down a twoelement 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 secretholder can force you to have to name the two secrets, but I suspect that that might be the case.
For N = 4, ask about any twoelement 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 5element subsets is fruitless (since the secretholder can always answer "no", "no", "yes", and "yes", respectively), and asking about a 3element 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 2element subsets. Then, adversarially, the secretholder 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 secretholder 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 twoelement 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) twoelement subsets as being the pair of secrets no matter what the answers are. After that I ask about the other six twoelement 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 extrahard to pin down a twoelement 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 secretholder can force you to have to name the two secrets, but I suspect that that might be the case.
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.

 Posts: 60
 Joined: Fri Jun 15, 2007 2:33 am UTC
 Location: Multiple Places (only one now that you read this...)
Re: Two secrets
Cauchy wrote:For N = 5, asking about 0, 1, 4, or 5element subsets is fruitless (since the secretholder can always answer "no", "no", "yes", and "yes", respectively), and asking about a 3element 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 2element subsets. Then, adversarially, the secretholder 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 secretholder 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 twoelement 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) twoelement subsets as being the pair of secrets no matter what the answers are. After that I ask about the other six twoelement 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 secretholder will always answer "no" to a 2element 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:
Re: Two secrets
This method gets the number of questions down to a constant multiple of log(N)^4:
Spoiler:
Re: Two secrets
sfwc wrote:Spoiler:
How can we process the cases where the four numbers all differ at the same digit and are otherwise identical?

 Posts: 60
 Joined: Fri Jun 15, 2007 2:33 am UTC
 Location: Multiple Places (only one now that you read this...)
Re: Two secrets
Yat wrote:sfwc wrote:Spoiler:
How can we process the cases where the four numbers all differ at the same digit and are otherwise identical?
Spoiler:
Re: Two secrets
Poker wrote:In truth, N = 5 should require only 3 questions. It's true that adversarially the secretholder will always answer "no" to a 2element 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? Secretholder can still say "no" to all three of {1, 2}, {1, 3}, and {2, 3}, but 4 and 5 are not true either.

 Posts: 60
 Joined: Fri Jun 15, 2007 2:33 am UTC
 Location: Multiple Places (only one now that you read this...)
Re: Two secrets
Xias wrote:Poker wrote:In truth, N = 5 should require only 3 questions. It's true that adversarially the secretholder will always answer "no" to a 2element 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? Secretholder 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?
Re: Two secrets
Oh, that was silly of me.
Re: Two secrets
Poker wrote:Yat wrote:sfwc wrote:Spoiler:
How can we process the cases where the four numbers all differ at the same digit and are otherwise identical?Spoiler:
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.

 Posts: 60
 Joined: Fri Jun 15, 2007 2:33 am UTC
 Location: Multiple Places (only one now that you read this...)
Re: Two secrets
I just realized we can improve sfwc's method to only require O(log(N)^3) questions:
Spoiler:
Re: Two secrets
I think I have an O(log(N)) solution.
Spoiler:
Re: Two secrets
Nitrodon wrote:I think I have an O(log(N)) solution.Spoiler:
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:
Re: Two secrets
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:
Re: Two secrets
Yat wrote:Nitrodon wrote:I think I have an O(log(N)) solution.Spoiler:
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:
I don't see what the problem is.
Spoiler:
Re: Two secrets
jaap wrote:Yat wrote:Nitrodon wrote:I think I have an O(log(N)) solution.Spoiler:
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:
I don't see what the problem is.Spoiler:
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.
Who is online
Users browsing this forum: Google Feedfetcher and 53 guests