Problem 61069. Clueless - Lord Ned in the Game Room with the Technical Computing Language

[Warning: this is a nontrivial programming problem]
Worried about the decline in reasoning skills in the clueless populace of Nedland, Lord Ned had the finest minds at the University of Nedsburg develop a fun game to sharpen logical inference skills.
The game consists of a deck of 3n cards, with n cards in each of three categories.
One card from each category is randomly selected and these three cards are placed, unseen, in an envelope. The goal of the game is for the players to figure out which cards are in the envelope.
The remaining 3(n-1) cards are shuffled together and then dealt to the players. Every player receives the same number of cards; any leftover cards are placed face-up so that all players can see them. Because all the cards are shuffled together, the players will not all have an equal distribution of cards from the three categories.
Players take it in turns to ask any other player about three cards, one from each category. If the player asked has any of the cards asked for, they must show one of those cards to the player who asked. (If they have more than one of the specified cards, they can choose which card to show.) The other players do not get to see which card has been shown, but they do know which three cards were asked for and that the player asked had one of them. If the player asked has none of the cards asked for, they simply state this and do not have to show any of their cards.
Once a player believes they have deduced the identity of the three cards in the envelope, they can, on their turn, announce their guess, then check the cards in the envelope. If the player is correct, they can reveal the cards as proof and they win the game. If not, they are eliminated. They must return the cards to the envelope, and the game continues without them.
Write a function that takes information about a game as inputs and returns the solution (that is, the deduced identity of the cards in the envelope) as output.
The inputs to the function are:
  • m, the number of players
  • n, the number of cards in each category
  • pnum, which player you are (from 1 to m). Players take turns in order (1 to m, and back to 1). If a card is revealed and it is your turn, you know the exact identity of that card. If it is not your turn, you know only that one of the cards asked for was revealed.
  • yourcards, a 3-element cell array representing the cards dealt to you. Each cell contains the cards for one category. The cards from that category are given as a vector of values from 1 to n. If there are no cards for that category, the cell will contain an empty vector. In the example image, if you are the player in the bottom left (player 4), yourcards = {[1 3],[],[]}. If instead you are the player in the bottom right (player 3), yourcards = {[],[4],[2]}.
  • commoncards, a 3-element cell array representing the extra cards visible to everyone. The format is the same as for yourcards. In the example image, commoncards = {[],[3],[]}.
  • turns, an nt-by-5 matrix representing nt turns of the game. Each row of turns records one player's turn as a 5-element vector. The first value is the number of the player asked. The next three values are the cards asked for, one for each category in order. The final value is the result: -1 represents the asked player responding that they do not have any of the requested cards; 0 represents the asked player showing a card (but you do not know which specific card); a value of 1-3 represents the asked player showing you a specific card, where the value is the index (or, equivalently, category) of the three cards asked for. For example, a row of turns that was the vector [5 4 3 2 1] would represent player 5 being asked for card 4 in category 1, card 3 in category 2, and card 2 in category 3, and showing you card 4 of category 1.
The output should be a single 3-element vector of the cards in the envelope, in order. For the example image, the output would be [4 2 1].
Assumptions
The game is still new to Nedland, so don't expect the players to make the best requests on their turn, but the solution can be inferred from the inputs given. It may be possible to determine the solution from less information than is given, but the information given will always be sufficient.
Although it shouldn't matter for your implementation, the official rules have 4-8 players (m) and card decks with up to 8 cards in each category (n), using at least enough cards to ensure that each player gets at least two cards in their hand.
Example
For the example images, m = 4, n = 4. Suppose pnum = 4, in which case yourcards = {[1 3],[],[]} and commoncards = {[],[3],[]}.
moves = 12×5
3 1 4 3 0
1 3 4 4 0
2 3 1 3 0
1 4 2 2 -1
4 3 1 1 0
3 2 2 2 0
2 1 1 4 0
2 4 2 3 3
3 3 2 1 -1
1 4 4 2 -1
2 4 2 1 -1
1 2 2 4 1
In the first turn, player 1 asks player 3 for cards [1 4 3] (that is, card 1 from category 1, card 4 from category 2, and card 3 from category 3). Player 3 shows them a card but you, player 4, don't know which. You have the first card in your hand, so it must have been one of the other two, but so far no further information can be extracted.
Similarly, player 2 then asks player for cards [3 4 4] and is shown one. Again, you hold the first card, so player 1 must have either card 4 from category 2 or card 4 from category 3, but you don't yet know which.
On the fourth turn, you ask player 1 for cards [4 2 2], but player 1 has none of these.
More turns occur where you cannot determine any concrete information yet.
On the eight turn, things suddenly get interesting. You ask player 2 for [4 2 3] and are shown the third of these. That is, you know that player 2 holds card 3 from category 3.
Moreover, this makes some of the earlier turns more useful. Revisiting the first turn where player 3 was asked for [1 4 3], you now know that you held the first card and player 2 held the third card. The card that player 3 showed player 1 must therefore be the second card, so now you know that player 3 has card 4 from category 2.
And similarly, now you can deduce from turn 2 that player 1 has card 4 from category 3 (because you hold the first card and player 3 holds the second card). And again from turn 7, you can now deduce that player 2 has card 1 from category 2, using the same logic.
At this point, you now know both cards that player 2 holds, so you can eliminate all other cards from possibly being held by them.
You also now know the locations of three of the four cards in category 2: player 2 has card 1, the common card is card 3, and player 3 has card 4. That means the remaining card (2) is in the envelope.
Turn 9 tells you that player 3 does not have card 1 from category 3. The next two turns provide no new information.
Finally, turn 12 reveals that player 1 has card 2 from category 1. This means you now know both cards player 1 holds (2 from category 1 and 4 from category 3). Consequently, you know that no player has card 1 from category 3 (you know both cards held by players 1 and 2, you know player 3 doesn't have it, you don't have it, and it's not the common card), so it must be in the envelope.
This just leaves category 1 but you now know the location of three of the four cards (you have cards 1 & 3, player 1 has card 2). And so you have the solution: [4 2 1].
soln = infercards(m,n,pnum,yourcards,commoncards,moves)
soln =
4 2 1
Implementation Suggestions/Tips
One way to find the solution is to keep an array of all cards and all players, with values indicating your state of knowledge about whether that player has that card: unknown, yes, or no. Start with everything unknown, and fill in information as you go. For this tracking, you can treat the common cards as player m+1. Each category has one card that nobody has, which is the card in the envelope. Once you have identified that card for each category, you have your solution.
You start with complete knowledge of which cards you and the common "player" do and do not have.
Go through the turns and use the provided information to update your state of knowledge. Also use the following observations to extend the logic to find new information:
  • If you know a player has a card, you know all other players do not.
  • You know how many cards each player has: the same number that you have. Equivalently, you can calculate it: ncards = floor(3*(n-1)/m). If you know the identities of ncards cards for a player, you know they have no other cards. (The common cards are an exception, but this doesn't matter because you already know exactly what cards are and are not in the common set.)
  • Once you know the locations of (n-1) cards in a category, the remaining card must be in the envelope.
  • Each player holds ncards cards. If you can identify 3n-ncards cards that a player definitely does not hold, then they must hold the remaining ncards cards. That is, if the no, yes, and maybe/unknown cards for a player are distributed such that there are ncards yes or maybe (and 3n-ncards no), then all the remaining maybes are yeses.
Remember that, as in the example, new information disclosed in a turn may make previous turns more relevant.
Solve

Solution Stats

24.0% Correct | 76.0% Incorrect
Last Solution submitted on Nov 11, 2025

Solution Comments

Show comments

Problem Recent Solvers6

Suggested Problems

More from this Author33

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!