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: 3877
- Joined: Thu Jan 28, 2016 7:00 pm UTC
- Location: 53-1
Re: Two secrets
Far non-optimal 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 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.
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.
(∫|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 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:
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 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.
-
- 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 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?
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:

Who is online
Users browsing this forum: No registered users and 7 guests