Problem of the Month
Solution to Problem 0: What’s my card?

1. Denote the integer on Adina’s card by $a$ and the integer on Budi’s card by $b$.

   If $b=1$ or $b=10$, then Adina would know the answer to the question in the first line and hence would not have asked it. Therefore, $b\ne 1$ and $b\ne 10$. Budi deduces this information from the fact that Adina asked the question in the first line.

   After Dewei answers "No" in the second line, Budi knows the following information: the value of $a$, that $b\ne 1$, that $b\ne 10$, and that $a<b$. According to the third line of the dialogue, Budi is able to determine the value of $b$ from this information.

   Since $a<b$ and $b<10$, it must be that $a\le 8$. If $a<8$, then there is no way for Budi to deduce the value of $b$ from the information in the previous paragraph. Therefore, $a=8$ and $b=9$.

   Although we have already deduced the integers on the two cards, it is worth pointing out that the final line of the dialogue makes sense. Indeed, the fact that Budi determined the value of $b$ immediately after Adina’s question was answered tells Adina that $a=8$. Otherwise, as discussed in the previous paragraph, there is no way that Budi could have determined the value of $b$ after line 2 in the dialogue.

2. The smallest possible sum of three different integers from $1$ to $10$ inclusive is $1+2+3=6$ and the largest is $8+9+10=27$. Therefore, $9$, $16$, and $25$ are the only possible perfect squares that can be equal to the sum of the integers on the cards. It is not difficult to deduce that there are exactly $15$ sets of three distinct integers from $1$ to $10$ having a sum equal to a perfect square. One way to approach this is to examine possibilities by considering the largest integer in the set. For instance, if $10$ is the largest integer, then we seek distinct positive integers $x$ and $y$ such that $x+y+10$ is a perfect square. Since $10>9$, $x+y+10>9$, and so $16$ and $25$ are the only possibilities for this sum. This means either $x+y=6$ or $x+y=15$. In the former case, $x$ and $y$ could be $1$ and $5$ or $2$ and $4$ in either order ($x$ and $y$ need to be different, so $x=y=3$ is not possible). In the latter case, $x$ and $y$ equal to $6$ and $9$ or $7$ and $8$. Therefore, four of the sets of three distinct positive integers are $\{1,5,10\}$, $\{2,4,10\}$, $\{6,9,10\}$, and $\{7,8,10\}$. Moreover, these four are the only such sets that contain $10$. All fifteen sets are listed below. $$\{1,2,6\},\{1,3,5\},\{1,5,10\},\{1,6,9\},\{1,7,8\},\{2,3,4\},\{2,4,10\},\{2,5,9\},$$ $$\{2,6,8\},\{3,4,9\},\{3,5,8\},\{3,6,7\},\{4,5,7\},\{6,9,10\},\{7,8,10\}$$

   After the dialogue, each player knows that the sum of the integers on the three cards is a perfect square. Each player can see two cards. If a player sees the integers $1$ and $6$, then the integer on their own card could be $2$ or $9$, but they will not be able to tell which since in either case the sum would be a perfect square. Since every player is able to deduce the integer on their card once they learn that the sum is a perfect square, it is not possible for $1$ and $6$ to be two of the integers on the cards. Therefore, the sets $\{1,2,6\}$ and $\{1,6,9\}$ can be eliminated as possibilities for the integers on the three cards. $$\cancel{\{1,2,6\}},\{1,3,5\},\{1,5,10\},\cancel{\{1,6,9\}},\{1,7,8\},\{2,3,4\},\{2,4,10\},\{2,5,9\},$$ $$\{2,6,8\},\{3,4,9\},\{3,5,8\},\{3,6,7\},\{4,5,7\},\{6,9,10\},\{7,8,10\}$$ If a player sees the integers $1$ and $5$, then the integer on their card could be $3$ or $10$, but they cannot determine which of the two. Therefore, the three cards cannot be $\{1,3,5\}$ or $\{1,5,10\}$.

   Continuing with this sort of reasoning, all possibilities except $\{2,5,9\}$, $\{3,6,7\}$, and $\{4,5,7\}$ can be eliminated from the list above.

   If the integers are $2$, $5$, and $9$, then one of the players sees the cards $2$ and $5$. The only way for the sum to be a perfect square is for the integer on their card to be $9$ (remember, there is only one of each card, so they cannot be holding a card with a $2$ since they see a $2$). Therefore, they know the integer on their card. The player who sees $2$ and $9$ knows their card must have $5$ on it since there is no other integer that can be added to $2+9=11$ to get a perfect square. Finally, the player who sees $2$ and $5$ knows their card must have $9$ on it by the same reasoning. Therefore, if the cards have $2$, $5$, and $9$ on them (in any order), then all three players will know the integer on their card as soon as they learn that the sum is a perfect square.

   By similar reasoning, if the integers are $3$, $6$, and $7$ in any order, then each player will know the integer on their card once they learn that the sum is a square. Similar reasoning applies if the integers are $4$, $5$, and $7$ in any order.

   This gives a total of $3\times 6=18$ configurations of the cards because there are $6$ ways to distribute the three cards among the three players for each of the three possible sets of cards. However, it is possible that some of these configurations would lead to Adina knowing the answer to her question immediately from the cards she can see. To finish the argument, we will show that in any of these $18$ configurations of the cards, Adina could not possibly know just from the cards that she sees that the sum is or is not a perfect square.

   The possible pairs of integers that Adina can see are $\{2,5\}$, $\{2,9\}$, $\{5,9\}$, $\{3,6\}$, $\{3,7\}$, $\{6,7\}$, $\{4,5\}$, $\{4,7\}$, or $\{5,7\}$. These are the two-element subsets of the three possible sets of integers on the cards. In each of these nine cases, there is at least one possibility for the integer on her card that would make the sum a perfect square. As well, in each of these nine cases, if the integer on her card were $1$, then the sum would not be a perfect square. Therefore, if Adina sees any of these nine pairs of integers, there is no way for her to know whether the sum is a perfect square. Therefore, all $18$ configurations described above are possible.

3. Since none of the cards have a prime number on them, the possibilities for the integers on the cards are $1$, $4$, $6$, $8$, $9$, and $10$. As well, the sum of the three integers is prime, which rules out many possibilities. By carefully checking, one finds that there are exactly seven sets of three distinct integers from the list $1$, $4$, $6$, $8$, $10$ that have a prime sum. They are listed below. $$\{1,4,6\},\{1,4,8\},\{1,6,10\},\{1,8,10\},\{4,6,9\},\{4,9,10\},\{6,8,9\}$$ The first column in the table below contains the fifteen pairs of two distinct integers selected from $1$, $4$, $6$, $8$, $9$, and $10$, which are the possible pairs of cards that a player can see. The right column contains the corresponding number of three-element sets from the list above of which the given two-element set is a subset. For example, the number $2$ occurs to the right of $\{1,4\}$ because $\{1,4\}$ is a subset of $\{1,4,6\}$ and $\{1,4,8\}$ and none of the other sets.

   $\{1,4\}$	$2$
   $\{4,6\}$	$2$
   $\{6,9\}$	$2$
   $\{1,6\}$	$2$
   $\{4,8\}$	$1$
   $\{6,10\}$	$1$
   $\{1,8\}$	$2$
   $\{4,9\}$	$2$
   $\{8,9\}$	$1$
   $\{1,9\}$	$0$
   $\{4,10\}$	$1$
   $\{8,10\}$	$1$
   $\{1,10\}$	$2$
   $\{6,8\}$	$1$
   $\{9,10\}$	$1$

   If a pair in the table above has a $1$ next to it, then a player who sees those two integers will know the integer on their card after the first four lines of dialogue. For instance, if a player sees $4$ and $8$, they will know that their card is $1$ since $\{1,4,8\}$ is the only one of the seven sets above that contains $4$ and $8$. On the other hand, if there is a $2$ next to a set in the table above, then a player who sees those two integers will not be able to determine the integer on their card after the first four lines of dialogue. For instance, if a player sees $1$ and $4$, then the set of integers is either $\{1,4,6\}$ or $\{1,4,8\}$, so a player who sees $1$ and $4$ knows that their card is $6$ or $8$, but cannot determine which.

   We know that after the first four lines of dialogue, exactly one player is able to determine the integer on their card. Suppose the set of integers on the cards is $\{4,9,10\}$. The two-element subsets of this set are $\{4,9\}$, $\{4,10\}$, and $\{9,10\}$. Both $\{4,10\}$ and $\{9,10\}$ have a $1$ next to them in the table above, so this means that if the set of integers is $\{4,9,10\}$, then two players would know the integer on their card after the first four lines of dialogue. Therefore, the set of integers on the cards is not $\{4,9,10\}$. For similar reasons, the integers cannot be $\{6,8,9\}$.

   The two-element subsets of $\{1,4,6\}$ all have a $2$ next to them in the table above, which means that if the set of integers is $\{1,4,6\}$, then none of the players would know the integer on their card after the first four lines of dialogue. Therefore, the set of integers is not $\{1,4,6\}$, and for the same reason, it is not $\{4,6,9\}$.

   The three players will also deduce this information as soon as the statements in line 5 of the dialogue are spoken. Thus, after these statements are made, all three players know that the only possibilities for the set of integers on the cards are those below: $$\{1,4,8\},\{1,6,10\},\{1,8,10\}$$ Furthermore, in each of these three cases, the integer on Charlie’s card must be $1$ since only the player with $1$ on their card is able to deduce the integer on their card after the first 5 lines of dialogue. For instance, if the cards are $1$, $4$, and $8$, then the players who have $4$ and $8$ on their card see the pairs of integers $\{1,8\}$ and $\{1,4\}$ respectively. Since these sets each have a $2$ next to them in the table above, these players cannot deduce the integer on their card from the first five lines of dialogue. However, the player whose card has a $1$ on it sees the set $\{4,8\}$, which has a $1$ next to it in the table above, so they can deduce the integer on their card from the first five lines. By similar reasoning, if the cards are $\{1,6,10\}$ or $\{1,8,10\}$, then the player who is able to deduce the integer on their card must be holding the card with $1$ on it. Therefore, the integer on Charlie’s card is $1$.

   We have now narrowed down to $6$ possibilities for how the cards are distributed:

   Adina	Budi	Charlie
   4	8	1
   8	4	1
   6	10	1
   10	6	1
   8	10	1
   10	8	1

   Since Charlie’s card has $1$ on it, Adina and Budi each see a $1$ and one of $4$, $6$, $8$, and $10$. If Adina or Budi sees $1$ and $4$, then they know that the integer on their card is $8$ since $\{1,4,8\}$ is the only possible remaining set that contains both $1$ and $4$. Similarly, if one of them sees $1$ and $6$, then they know the integer on their card is $10$. If they see $1$ and $8$, then the integer on their card could be either $4$ or $10$, and if they see $1$ and $10$, then the integer on their card could be either $6$ or $8$.

   In the sixth line of dialogue, we find out that after line 5, Adina does not know the integer on her card and Budi does know the integer on his card. This means Adina sees either $1$ and $8$ or $1$ and $10$, and Budi sees either $1$ and $4$ or $1$ and $6$. Of the six possibilities in the table above, the only two that satisfy both of these conditions are

   Adina	Budi	Charlie
   4	8	1
   6	10	1

   Therefore, Charlie is holding the card with $1$ on it, and either Adina’s card has $4$ on it and Budi’s has $8$ on it, or Adina’s card has $6$ on it and Budi’s has $10$ on it.

   In fact, both of these are possible. Denote by $a$ the integer on Adina’s card, by $b$ the integer on Budi’s card, and by $c$ the integer on Charlie’s card. We will verify that when $a=4$, $b=8$, and $c=1$ the dialogue makes sense. Verifying the case when $a=6$, $b=10$, and $c=1$ can be done similarly. Therefore, we assume that $a=4$, $b=8$, and $c=1$.

   1. Adina sees $8$ and $1$, neither of which is prime, so she can ask the question in line 1 since she does not know its answer.

   3. Budi sees that $c=1$ and $a=4$ and knows that $b$ is not prime. If $b=8$, then $a+b+c$ is prime. If $b=10$, then $a+b+c$ is not prime. Therefore, Budi cannot know the answer to the question in the third line before he asks it.

   5. • Adina sees that $b=8$ and $c=1$, knows that $a+b+c=a+9$ is prime, and knows $a$ is not prime. Therefore, she knows that either $a=4$ or $a=10$, but cannot tell which.

      • Budi sees that $a=4$ and $c=1$, knows that $b$ is not prime, and knows that $a+b+c=5+b$ is prime. Therefore, he knows that $b=6$ or $b=8$, but cannot tell which.

      • Charlie sees $a=4$ and $b=8$, knows that $c$ is one of $1$, $6$, $9$, and $10$, and knows that $a+b+c=12+c$ is prime. Since $12+6=18$, $12+9=21$, and $12+10=22$ are all composite, Charlie knows at this point that $c=1$.

   6. • Budi knew that either $b=6$ or $b=8$ after he learned that $a+b+c$ was prime. He knows that Charlie knows the values of both $a$ and $b$. If $b=6$, then Charlie would not have been able to determine whether $c=1$ or $c=9$ since the sums $a+b+c=4+6+1$ and $a+b+c=4+6+9$ are both prime. Therefore, Budi concludes that $b=8$.

      • Adina knows that $a=4$ or $a=10$ and she knows that Charlie knows that $b=8$. She also knows that Charlie is able to deduce the value of $c$ from the information revealed in the first four lines of dialogue. If $a=10$, then Charlie could see an $8$ and a $10$ and would know that $c$ was one of $1$, $4$, $6$, and $9$. The sum $8+10+1=19$ is prime, but $8+10+4$, $8+10+6$, and $8+10+9$ are all composite. This means Charlie would be able to deduce that $c=1$ if $a=10$. Similarly (as previously argued), if $a=4$, then Charlie would be able to deduce that $c=1$. Therefore, Charlie’s ability to deduce the value of $c$ after the first five lines does not tell Adina the value of $a$. As well, whether Adina is holding $4$ or $10$, Budi would not be able to tell whether he is holding $6$ or $8$ after the first five lines. This is because $4+1+6$, $4+1+8$, $10+1+6$, and $10+1+8$ are all prime. Therefore, Budi’s inability to determine the value of $b$ after the first five lines of dialogue does not tell Adina the value of $a$.

   7. If $a=10$ and $b=6$ or $b=8$, then Charlie would still be able to deduce that $c=1$ after the first four lines of dialogue. However, Budi would not be able to deduce the value of $b$ after the first five lines of dialogue. Both of these facts follow from reasoning similar to that which is above. Therefore, once Budi announces that he has deduced the integer on his card, Adina knows that $a\ne 10$, so she knows that $a=4$.

   In conclusion, the complete set of possibilities for the integers on the cards are that Adina’s card has $4$, Budi’s card has $8$, and Charlie’s card has $1$, or Adina’s card has $6$, Budi’s card has $10$, and Charlie’s card has $1$.