Hidden Cards

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Cradarc
Posts: 448
Joined: Fri Nov 28, 2014 11:30 pm UTC

Hidden Cards

Postby Cradarc » Sat Nov 19, 2016 3:17 am UTC

A group of 10 logicians have been challenged by a puzzlemaster to play a game.

"I have here two sets of 10 cards, each with cards numbered 1 through 10. As you can see, one set is colored blue and the other is colored red. I will deal a blue card and a red card to each one of you. The red card can be made available for everyone to see, but the blue card should be kept private to you. Make sure you do not communicate with your associates regarding the value of your blue card."

One they complied, he continued:
"Your goal is to guess the value of the blue card possessed by the person who has a red card with value identical to that of your own blue card. Your guess is made by raising your hand and saying a single number out loud when I call on you. Be warned! You may only speak if you are making a guess. Everyone is disqualified if anyone attempts to communicate in a subversive way. I know who has what card, so I can check the validity of your guesses. I will award 5 points for every correct guess and subtract 1 point for every incorrect guess. It goes without saying that someone who has already guessed correctly can no longer make guesses. You will see your points change in real time on the scoreboard. Good luck!"

What is the minimum possible final score if every logician plays optimally to maximize the final score?
Is it possible to generalize to N people? (Correct guess would be worth N/2 points)
Last edited by Cradarc on Mon Nov 21, 2016 12:40 am UTC, edited 1 time in total.
This is a block of text that can be added to posts you make. There is a 300 character limit.

Sandor
Posts: 172
Joined: Sat Feb 13, 2010 8:25 am UTC

Re: Hidden Cards

Postby Sandor » Sun Nov 20, 2016 8:30 pm UTC

Cradarc wrote:Your goal is to guess the value of the blue card possessed by the person who has a red card with value identical to that of your own blue card.

Just running thought the numbers 1 to 10 will reach this goal. The logicians must have some other goal as well. I suspect they should be trying to maximise the score (by making as few incorrect guesses as possible), but you don't actually state this.

If I were playing, I would start by making a "guess" of my own blue number. I would then stay silent until I heard someone else say my red number, and if that turned out to be an incorrect guess, I would then "guess" their red number. If everyone else did the same, then the minimum score would be 40 or thereabouts (one wrong guess and one correct guess for everyone).

Cradarc also wrote:Make sure you do not communicate with your associates regarding the value of your blue card. [...] Everyone is disqualified if anyone attempts to communicate in a subversive way.

Does my strategy violate these rules? I'm communicating the value of my blue card, but it's not by a back-channel, it's blatant and in the clear.

Cradarc
Posts: 448
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Hidden Cards

Postby Cradarc » Mon Nov 21, 2016 12:39 am UTC

Sandor wrote:I suspect they should be trying to maximise the score (by making as few incorrect guesses as possible), but you don't actually state this.

Oops, yeah. It was implied, but I should have stated that.

Sandor wrote:If I were playing, I would start by making a "guess" of my own blue number. I would then stay silent until I heard someone else say my red number, and if that turned out to be an incorrect guess, I would then "guess" their red number. If everyone else did the same, then the minimum score would be 40 or thereabouts (one wrong guess and one correct guess for everyone).

1. They didn't have time to converse after hearing the rules, but I guess you can argue they can each individually deduce the optimal strategy. This is a loophole to the game though (see point 3).

2. Your method doesn't guarantee 40 points
Let P(N) denote the person with red card = N. and B(N) denote the blue card value of P(N).
Consider the scenario where:
B(2j) = B(2j+1)
B(2j+1) = B(2j)
With your strategy, a person guesses correctly every 2 turns. But what happens after 5 turns?
Everyone who has yet to guess correctly needs to guess the blue card of one of the people who has already guessed correctly (and can no longer speak).
At this point, the first guess has to be a random choice from the 5. The next person guess a random choice from 4, etc.

3. A better strategy (if we're assuming they are allowed to make fake guesses to communicate and all choose this strategy) is to simply wait until all but one person has said their blue number, then win back all the points. That would actually get you 41.
This is a block of text that can be added to posts you make. There is a 300 character limit.

sfwc
Posts: 224
Joined: Tue Mar 29, 2011 1:41 pm UTC

Re: Hidden Cards

Postby sfwc » Mon Nov 21, 2016 11:01 am UTC

It makes sense for the logicians to at least follow this rule: if you know that you can guess correctly, then raise your hand immediately. Otherwise, wait a little to give those who can guess correctly a chance, and then raise your hand a little later if nobody else does (the time you wait should be slightly randomised, so that the uncertain logicians don't all guess at once). I hope that this doesn't count as sneaky communication: for me, sneaky communication would be more like waiting a number of seconds corresponding to the number on your blue card before raising your hand.

This means that anyone whose two cards match will guess right at the start, since they know that they can guess correctly just by naming the number on both their cards. To explain my strategy from this point on, I need a little notation. First, note that B is a permutation of the numbers from 1 to 10. Let's call the inverse permutation C. Let's say some uncertain logician P(i0) is called on to make a guess. Then she should guess the number on her blue card. This guess will be wrong, of course, but now the other logicians know the value of B(i0). Let i1 = C(i0). Then P(i1) can make a correct guess, namely B(i0). This is all as in the previously described strategies. But we can go further. Now it is public knowledge that B(i1) = i0, and so, letting i2 be C(i1), the logician P(i_2) can now make the correct guess i_1. This makes it public knowledge that B(i_2) = i_1, and allows P(i_3) to make a correct guess, where i_3 = C(i_2). And so on. In this way, the logicians corresponding to a whole cycle of the permutation B will all guess correctly (in reverse order around the cycle). Eventually the whole cycle will have been eliminated, and only uncertain logicians will remain.

We can add an extra trick to slightly improve this: if the logicians reach a point where some cycles have been eliminated and at most 3 logicians remain, then they can all guess correctly. First, they know that there are no 1-cycles remaining (since logicians in 1-cycles guess correctly right at the start). So they either form a 2-cycle, if there are 2 of them, or a 3-cycle, if there are 3. They know who comes after them in the cycle, and so they can work out who has which blue card and all guess correctly.

If the logicians follow this strategy, then there can only be at most 4 incorrect guesses. So in the worst case, the logicians get 46 points with this strategy.

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

Re: Hidden Cards

Postby Poker » Mon Nov 21, 2016 1:34 pm UTC

I see your 46 and raise you 47 with the following strategy:

Spoiler:
Rather than having a random uncertain logician guess the number on their blue card, the logician with the lowest remaining blue card should guess the number on their red card. This still makes it public knowledge what B(i0) is, and the strategy can proceed as sfwc stated, only now some of those "wrong" guesses will be correct - namely, every guess that is part of a 2-cycle. That means that any incorrect guesses must be part of a 3-or-greater-cycle (and as before, will be the only incorrect guess in its cycle), and as there can be at most 3 of these, there can be at most 3 incorrect guesses. (The at-most-3-logicians trick is still useful but doesn't decrease this number any - there are still instances where the cycles are 3-3-4 and the optimization won't have an effect.)

Granted, to make this strategy sound, the "if you know that you can guess correctly, then raise your hand immediately" rule, which I'm interpreting to mean that the 1-cycles should get out of the way immediately, must be discarded, but that's fine, since they'll be taken care of by the modified algorithm anyway. There's no rush.


Of course, this strategy only works if all the logicians come up with it together. Some sort of superrationality is needed for this to be useful, I think.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Hidden Cards

Postby Xias » Sat Nov 26, 2016 9:06 am UTC

Spoiler:
Essentially, the information immediately available to each person is "who is the next person in my cycle?" So whatever guess someone makes is them guessing who the third person in their cycle would be.

Obviously, any 1-cycle is immediately eliminated. After that, regardless of the distribution of cycles, everyone is on even footing. Since any strategy involving which blue card guesses first can't be agreed upon beforehand, then someone at random will be the first to guess. Their choice, realistically, comes down to guessing themselves, or guessing someone else at random. Is guessing yourself the best option for the first guess?

With a group of 2 or 3, a perfect score can be reached. Lets's take a look at a group of 4. The actual numbers don't matter, so let's say that the person who guesses first is A and the next in their cycle is B. Then the possible cycles are

(ABCD)
(ABDC)
(AB)(CD)

So there is a 1/3 chance* of being in a 2 cycle, and a 2/3 chance of being in a 4 cycle.

If you guess a random third person and turn out wrong (which you will 2/3 of the time), you communicate some information to the group. So let's say you guess C. Then the person who has C as their blue card knows that your blue card is not their red card - or, put another way, that you are not immediately before them in a cycle. In this case, that person must be D, since it can't be B (or you would have been correct) and it can't be C, since then they would be a 1 cycle and would have been eliminated. So now D knows that the cycle that they are in does not end with you. C, on the other hand, can't be sure that you didn't guess your own blue card for some reason, so outside of superrationality, C cannot be certain of anything yet.

Now I'm going to put forward a proposition: that anyone who knows that they have the most information (or are tied for the most information) about what cycles exist will guess next. I think this is safe to suggest without superrationality. Then at this point it is common knowledge that (A knows either that their cycle is not AxCy, or that they are not in a 2-cycle) and (Whoever is immediately before C is not also immediately after A) and (these three statements are common knowledge.) An alternative to this proposition is that whoever has the highest EV goes next, but I don't know if this can be gleaned from assymetrical knowledge.

Since D has C, she knows both which choice A made, and who is immediately before C (herself), so she has the most knowledge about the game AND knows that she does.

Now D wants to guess who comes after C in the game. Since she knows that her cycle can't end with A, her possibilities are

(DC)(AB)
(DCAB)

D can guess her own red card and get out 50% of the time, or guess A and get out 50% of the time. If she guesses her own card, and is correct, then the game finishes with 19 points. If she guesses A and is correct, then C knows that D comes immediately before him, which means he is not in a 2 cycle with A, and can therefore guess B correctly, then A can guess D correctly and the game finishes with 19 points.

If D guesses incorrectly, then she can immediately guess again and the game finishes with 18 points.

Now, let's go back a step and see if you guessed C correctly the first time. This happens with probability 1/3. Then the cycle is (ABCD). B (who would have the C card) can now guess D correctly, which means C can guess A and the game closes with 20 points.

So the expected points value if you guess a third person is (1/3)(20) + (2/3)(1/2)(19) + (2/3)(1/2)(18) = 19, with a min of 18.

If you guess your own red card, you are correct 1/3 of the time. If you are correct, then the game will finish with 20 points. If you are incorrect (2/3), then whichever of C and D will know that you are not at the end of their cycle and also not in a 2-cycle. Then they can guess correctly, finishing the game with 19 points. So the expected point value is 19.33, and the min is 19.

So for 4 players, the optimum strategy is to guess you are in a 2-cycle. This provides the most definite information to everyone.


(EDIT: I made a mistake here. Here is the correction.)

If you are incorrect (2/3), then whichever of C and D that has you as their blue card will know that they are not in a 2 cycle. Then that person will guess either B or the remaining person, with 1/2 chance of being correct. If they are incorrect, they will immediately know and guess correctly, then finishing the game with 18 points. So the EV is (1/3)(20) + (2/3)(1/2)(19) + (2/3)(1/2)(18), or 19, and the min is 18.

This has the result of it being no improvement over one person guessing until they are correct.

This information, including the EV and min, is common knowledge, so as we explore larger groups with more permutations, this can factor in. For example, if you are in a 6-group, then you have a 1/5* chance of being in a 2-cycle. So if you guess that you are in a 2 cycle and you are correct, then your partner will get out as well, leaving a 4 cycle, so your EV is (1/5)(19) + (4/5)(etc.)

*The odds could be affected by the elimination of 1-cycles, but I don't think they are and I haven't put in the work yet.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests