A cooperative guessing game - Guess your order and card

Question

6 players sitting in a circle and each assigned a card among 2 Hearts, 3 Hearts, ..., Ace Hearts (i.e. any of the Hearts cards). Holding her card above his forehead (i.e. Indian Poker fashion), each of them can see everyone else's cards, but not her own.

Round 1: Starting from player 1 and going clockwise until player 6, they take turn to call out their best guesses of what is their respective order among themselves (i.e. am I largest, or 2nd largest, etc.).

Round 2: Starting from player 6 and going counter-clockwise until player 1, they take turn to call out their best guesses of their respective order and the number on their respective card.

Objective: To maximise, as a group, the number of people who announced correctly in round 2.

Remarks:

• At any point in time, player's calls can incorporate any information that has been provided thus far.
• If it matters, the group is only told whether each call in round 2 is correct or incorrect at the end of the round, not immediately after calling.
• Technically, in rounds 1 and 2, the rule does not forbid calling out other integers that might convey more useful information (as long as they are in the allowable range for the order and card values).
• Players may discuss their strategies prior to distribution of the cards.

Find a strategy for the players that maximizes the expected score. What happens if we generalise to $n$ players with card values $1,\dots,m$?

Answer 1

Let's do better. I claim that we can fully win when:

$m \leq n^{n-1}$.
(To use a comparison started by Thomas Blue, with 6 players you can perfectly guess up to 7776 cards, or slightly less than 150 decks worth.)

This can be done as follows:

First, agree on an enumeration of all the cards and players. Express these enumerations in base $n$. For each player $k$, announce the sum of the $i$th digit of player $k+i$'s card, summed over all $1 \leq i \leq n-1$, mod $n$. In the second phase, every person can use every other person's stated number to each produce a different digit on their own card, which allows everyone to derive all $n-1$ digits of their own card, thus guessing their number.
(Corollary - if you don't have 5 friends to do the earlier trick, you can in fact devise a system to solve a standard deck with only 4 people!)

This seems to be tight:

From an information theoretic perspective, obviously your own statements provide no new additional information to yourself. So all you can do is to utilize everyone else's statements, each which gives $\log(n)$ bits of information. So we can discern between $n^{n-1}$ different states at most.

Answer 2

- So, the answer is six? - said A. - What are we aiming for now? It's no use trying to increase the six, since, ha-ha, there are only six of us here. And if there were more of us, I suppose, we could do the same feat easily, since everyone would provide even more information with the first number.

- Yeah... - added C, struggling to shuffle the deck of hearts - 13 cards total. - I believe, we could try to solve this in the common case. Start with one player, then move on to two, and et cetera.

- Well excuse me, gentlemen, but I came here to play, not to answer the infinite amount of questions at the same time. The strategies we could use are (figuartively) countless, and the site would just crack under the full solutions, - declared D.

- I believe I have an idea, - said F. - Nobody here wants to listen to boring proofs. How about I suggest particular case, and we compete at who gets a higher score? Say,

For six of us, what's the highest amount of cards we can play with, so that we still can all guess them during the second round?

- It's thirteen now... So you're thinking that the same could be done with, say... a deck?

- A deck sounds good, but for a baseline I would give... twenty.

- That doesn't seem a lot for...

- I meant twenty decks, 1040 different cards per se. We get 6 cards out of 1040, and then guess them all on the second round. That should be enough for a baseline here.

The strategy bases off athin's ideas.
First, A and B count and summarize numbers of four cards - C-D-E-F correspondingly. Then they get a modullo of this number by 32. As they both get the same number, they can encode it with two numbers, because they have 36 variants of what to say.
After A and B say their numbers, everyone of C-D-E-F knows the index of their card by modullo 32.
Then, the same happens for C-D against A-B-E-F with one difference - they get a modullo of the sum not by 32, but by 33. After they declare the number, A,B,E and F know the modullo of their corresponding cards by 33. The last two do the same, but by modullo 35.
After that, everyone knows at least two modullos of the card the are holding. Given that these three numbers are pairwise coprime, and we know the proper theorem, each of them can recover the card, if there's no more than 32*33=1056 cards total.

Answer 3

As a starter, there is a strategy to make

$5$ players

specifically

Player $2$, $3$, $4$, $5$, and $6$

to guess correctly.

The strategy is

Player $1$ should sum the numbers ($J$, $Q$, $K$ are numbered $11$, $12$, $13$ respectively) on Player $2$, $3$, $4$, $5$, and $6$'s cards; modulo it by $6$, and call that number publicly. If the modulo results $0$, call $6$.

By doing that,

Player $2$, $3$, $4$, $5$, and $6$ will know the number on his own card modulo by $6$. That means they will know his number's possibility is one of the following sets: $\{1, 7, 13\}$, $\{2, 8\}$, $\{3, 9\}$, $\{4, 10\}$, $\{5, 11\}$, or $\{6, 12\}$.

Take a note that

Every players know which set belongs to Player $2$, $3$, $4$, $5$, and $6$. And also, $2$ players may have the same set and that's ok.

The next step is

Player $2$ will help Player $3$ to determine his card from the set, Player $3$ will help Player $4$, Player $4$ will help Player $5$, Player $5$ will help Player $6$, and Player $6$ will help Player $2$

by calling

the respective order of his partner's card on his set. For example, Player $2$ knows Player $3$'s card is $8$ and his set should be $\{2, 8\}$. Player $2$ will call $2$ because $8$ is on $2$-nd order on the set.

Hence,

Player $2$, $3$, $4$, $5$, and $6$ will know his own card, and will know the answer in round $2$.

---

For bonus question, the above strategy of

winning $n-1$ players

is possible for

$m$ up to $n^2$.

Answer 4

My strategy is not entirely original; it is based on athin's strategy. It works for any $m \leq n^{\lfloor n/2\rfloor}$. For $n=6$, it works for up to $m = 6^3 = 216$.

Like with athin's strategy, the first player

calculates the sum of all the cards he/she can see, modulo $n$, and announces that (saying $n$ in place of zero).

The second player does likewise.

At this point, all players can easily calculate the value of their card, modulu $n$.

The third and fourth players

calculate the sum of all the cards they can see, in base $n$, then announce the second digit from the right (again, saying $n$ in place of zero). At this point, all players can calculate the value of the second digit of their card (base $n$).

This continues similarly for each pair of players.

At this point, each player knows $i = \lfloor n/2 \rfloor$ digits of their card, base $n$, and thus if $m < n^i$, then all players know the values of their cards, uniquely.

Thus, for an even number of players, it is always possible for all players to correctly identify their cards (and thus their rankings) for $m \leq n^{(n/2)}$.

For an odd number of players, all players can always identify the cards correctly for $m \leq n^{(n-1)/2}$. And they can all always identify their ranking and $n-1$ always identify their card for up to $m \leq n^{(n+1)/2}$. The first player will always correctly identify his/her ranking, relative to other players, but will only know the value of his/her card about 1 time in $1/e$.

To do this:

For round 1, reverse the order. Thus players $n$ and $n-1$ return the last digit of the sum of the cards they see, base $n$. The $n-2$ and $n-3$ return the second-to-last digit, etc. The first player will be the only one who returns the first digit (including zeros as leading digits). Thus, all players but the first will know the values of their cards. Since round 2 goes in the other order, the first player will know his/her rank, as all the others have been announced. The player will not know the first digit of their card, but will know the other digits. There is approximately a $1/e$ chance that this, plus the values/rankings of the other cards, will uniquely identify their card.

For the maximum value for $m$, each player will have approximately equal chance of saying each of the values in the range $[1,n]$. Thus, no other strategy should be able to always allow all players to uniquely identify all their cards for larger values of $m$.

Answer 5

My solution for m = 13 and n = 6 is below

Players one and two sum up the values of players 4-6 and they announce the digits of the sum in base 6. The sum's max value is 36 (13+12+11) so only 2 players are needed to communicate this information (6^2 = 36 >= 36). Player 3 is not needed (at least not for m=13 and n=6). Players 4-6 calculate the sum of the values of players 1-6 (player 1 + player 2 + player 3 + sum of players 4-6) and announce the digits of the sum in base 6. The max value is 63 (13+12+11+10+9+8) so only 3 players are needed here (6^3 = 216 >= 63). Everyone subtracts from the sum of all players the values of all other players to find their own value. At the end of round 1, for m = 13 and n = 6, all players know their value.

Generalizing the solution,

Let n and m be defined as in the original problem. Let log(x) be the log base 2 of x. Let r(x) be ceil(log(sum of m-a+1 from a=1 to x)/log(n)). r(x) is the number of players who need to announce to communicate the sum of values of x other players. It must be true that r(r(n)) + r(n) <= n. This inequality means that the number of players who need to announce the sum of all players plus the number of players needed to announce the sum of those announcing players is less than or equal to n.

My best shot at making an upper bound for m and simplifying was m <= (n * 2^n - n^3 + n + 1 + log(n) - (log(n))^2)/(2(1+log(n)))

I didn't include the derivation of r(x) and the upper bound of m because I'm not quite sure how to format it lol. And who would wanna read my poorly formatted explanation?

Answer 6

Here's a strategy that fits within the rules and solves all 6 of them:

Separate the cards into three groups and assign corresponding numbers:
1. A-6 (highest, second highest, ..., sixth highest)
2. 7-Q (lowest, second lowest, ..., sixth lowest)
3. K ("I have no guess")

Each player chooses a partner prior to the start of the game. On their turn in the first round, they speak the phrase corresponding to their partner's card.

When the second round comes along, each player can now accurately speak their card's number.

Let's look at an example.

Partners: (1, 2), (3, 4), (5, 6)

Now deal out the cards (as chosen by random.org):
Player 1: K
Player 2: 6
Player 3: 4
Player 4: 5
Player 5: 2
Player 6: 7

On the first go round, the players speak the following:
Player 1: "I believe my card is the 6th highest." (This indicates to Player 2 that their card is the 6.)
Player 2: "I don't know what my card is." (This indicates to Player 1 that their card is the K.)
Player 3: "I believe my card is the 5th highest." (This indicates to Player 4 that their card is the 5.)
Player 4: "I believe my card is the 4th highest." (This indicates to Player 3 that their card is the 4.)
Player 5: "I believe my card is the lowest." (This indicates to Player 6 that their card is the 7.)
Player 6: "I believe my card is the 2nd highest." (This indicates to Player 5 that their card is the 2.)

In the second round, Players 6 through 1 will announce their card numbers based on the precise information they just received from their partners. You may notice that Player 1 and Player 5 claimed the same thing (the 6th highest is the lowest), but by our encoding, these two phrases have very different meanings.

So what happens when we have $n$ players and $1,...,m$ cards?

This particular strategy does not work for most values of $n$ and $m$. It will, however, work for any values such that $m \le 2n+1$. Simply divide the $m$ cards into two equal groups and players speaking the ordinal within the group and "lowest" or "highest" as the group identifier. In the case of an odd $m$, the maximal card value is instead replaced with the phrase "I don't know my card" in the first round.

Answer 7

Update:

sorry! I did not see that players needed to give the number on their card as well. I thought this solution was close but it doesn't address half the problem. I'll keep it up in case its interesting, but this (almost) solves only half the problem.

Original response:

here is a solution which (almost) works for arbitrary n, m.

In round 1, each player gives the number of cards (which they can see) which are greater than the card of the person to their left. If players are allowed to respond in round 2 in an arbitrary order (which they aren't!) then we can get them all right.

A helpful observation: If player A knows the index of player B, and how many cards B can see which are greater than A's then A can determine their own index: Suppose B observes that there are x cards greater than A's. There must be either x or x + 1 such cards present (excluding or including B's respectively). If B's index is > x then their count didn't need to include their own card (A has idx x). Alternatively, if B's index is <= x, then A ought to correct for their omission (A has idx x + 1).

But who knows their index immediately after round 1? Where to begin? The unique* player who was told they are last (i.e. "I see n-2 cards which are greater than yours") knows they are last. Why? Only the player who told them they are last might also be last but that player was told they had at most n-3 cards which were greater than theirs (uniqueness).

So given this last player who knows their index, the person to their right knows their index (by "helpful observation"). We proceed by induction.

*When is the last player unique? Note if there are k "last" players then they were each told there are n-k-1 cards greater than their own. Well there can't be 3 or more last players: somebody along the way will see two or more of these players at once and will include the greater card in their count. Two players could run into this trouble but only if these observations never compared them to each other. In other words they told each other they were last (i.e. n = 2). So this solution only works for n > 2 ... but there isn't much you can say to these two players outside of bayes rule on m type of stuff anyways.