Two more secrets

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6141
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Two more secrets

Postby skeptical scientist » Mon Apr 24, 2017 8:29 pm UTC

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:

operator[] wrote: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?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Poker
Posts: 40
Joined: Fri Jun 15, 2007 2:33 am UTC
Location: Multiple Places (only one now that you read this...)

Re: Two more secrets

Postby Poker » Tue Apr 25, 2017 12:03 am UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6141
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Two more secrets

Postby skeptical scientist » Tue Apr 25, 2017 12:40 am UTC

Nice! That's my answer as well.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

SteelCamel
Posts: 6
Joined: Sun Jul 12, 2015 5:54 pm UTC

Re: Two more secrets

Postby SteelCamel » Tue Apr 25, 2017 8:22 pm UTC

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.

User avatar
Sabrar
Posts: 37
Joined: Tue Nov 03, 2015 6:29 pm UTC

Re: Two more secrets

Postby Sabrar » Tue Apr 25, 2017 8:37 pm UTC

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
Posts: 6
Joined: Sun Jul 12, 2015 5:54 pm UTC

Re: Two more secrets

Postby SteelCamel » Thu Apr 27, 2017 9:13 pm UTC

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!).


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 4 guests