There are ten coins a line, which are indistinguishable. It is known that two of them are false and have consecutive positions on the line. For each set of positions, you may ask how many false coins it contains. Is it possible to identify the false coins by making only two of those questions, without knowing the answer to the first question before making the second?
Problem
Source:
Tags: vector, analytic geometry, function, combinatorics proposed, combinatorics
24.09.2010 22:34
Suppose the coins are $M_1, M_2, ..., M_{10}$, and for each $n=1,2,...,9$ let $X_n = \{M_n, M_{n+1}\}$. We know one of the $X_n$ contains the two fake coins. We'll prove that it is possible to reach the goal with two questions. To see that, suppose $S$ is a set of coins. When we ask how many fake coins are in $S$, the answer we are given is the number of elements there are in the intersection between $S$ and the $X_n$ which contains the fake coins. Hence, it is enough to find two subsets $S_1, S_2$ of $\{M_1, M_2, ..., M_{10}\}$ such that the answers given in the two questions are different for each $X_n$. Take $S_1 = \{M_4, M_7, M_8, M_9, M_{10}\}$, $S_2 = \{M_1, M_5, M_6, M_7, M_8\}$. If the answers given are $(0,0) \Rightarrow M_2, M_3$ are the fake coins $(0,1) \Rightarrow M_1, M_2$ are the fake coins $(0,2) \Rightarrow M_5, M_6$ are the fake coins $(1,0) \Rightarrow M_3, M_4$ are the fake coins $(1,1) \Rightarrow M_4, M_5$ are the fake coins $(1,2) \Rightarrow M_6, M_7$ are the fake coins $(2,0) \Rightarrow M_9, M_{10}$ are the fake coins $(2,1) \Rightarrow M_8, M_9$ are the fake coins $(2,2) \Rightarrow M_7, M_8$ are the fake coins The solution is complete
02.10.2010 05:12
Let $c_1,c_2,...,c_{10}$ the coins, because the two fake coins are consecutive, there are $9$ posible positions for these fake coins (namely, $F=\{b_1,b_2,...,b_9\}$, where $b_1=c_1c_2, b_2=c_2c_3,...,b_9=c_9c_{10}$). Supose that it is posible to know the positions of the two fake coins. We fix two subsets $A,B$ of $\{c_1,c_2,...,c_{10}\}$, and then we get a vector $(a,b)$ in $\mathbb{Z}_{3}\times \mathbb{Z}_{3}$, were the first coordinate $a$ is the number of fake coins in the set $A$, and the second coordinate $b$ is the number of fake coins in the set $B$ (we consider $\mathbb{Z}_3=\{0,1,2\}$ cause each set $A,B$ can have $0,1$ or $2$ fake coins). Because there are $|\mathbb{Z}_{3}\times \mathbb{Z}_{3}|=3\cdot 3=9$ posible vectors, we define a function $f: F\to \mathbb{Z}_{3}\times \mathbb{Z}_{3}$, where $f(b_i)=(x,y)$ if $b_i$ have $x$ coins in $A$ and $y$ coins in $B$ ($1\le i\le 9$). We claim that $f$ is injective. Assume that $f(b_i)=f(b_j)$ if $i\not= j$, then if the two consecutive fake coins are in $b_i$, then we can chose $b_j$ as the set with fake coins and we cannot determinate the positions of the fake coins. Then $f$ is injective and because $|F|=|\mathbb{Z}_{3}\times \mathbb{Z}_{3}|$, $f$ is indeed bijective. Now the work is easy and it's not difficult to see that $A=\{c_3,c_4,c_8,c_9,c_{10}\}$ and $B=\{c_3,c_4,c_5,c_6,c_{10}\}$ satisfies.
26.07.2021 05:44
The answer is positive. Number the coins $1$ through $10$ in order from left to right. In the first question, we ask about coins $1, 3, 4, 5, 6$ and for the second question we ask about coins $2, 3, 4, 9, 10$. Then, we can determine which coins are false according to the following table: \begin{tabular}{|c|c|c|} \hline Answer to Q1 & Answer to Q2 & False Coins \\ \hline 0 & 0 & 7, 8 \\ 0 & 1 & 8, 9 \\ 0 & 2 & 9, 10 \\ 1 & 0 & 6, 7 \\ 1 & 1 & 1, 2 \\ 1 & 2 & 2, 3 \\ 2 & 0 & 5, 6 \\ 2 & 1 & 4, 5 \\ 2 & 2 & 3, 4 \\ \hline \end{tabular}This proves it is possible. $\blacksquare$
29.09.2021 04:09
If we use the sets $\{3, 4, 8, 9, 10\}$ and $\{3, 4, 5, 6, 10\}$, it satisfies the condition. Shamelessly copying @above's table we get \begin{tabular}{|c|c|c|} \hline Answer to Q1 & Answer to Q2 & False Coins \\ \hline 0 & 0 & (1, 2) \\ 0 & 1 & (6, 7) \\ 0 & 2 & (5, 6) \\ 1 & 0 & (7, 8) \\ 1 & 1 & (2, 3) \\ 1 & 2 & (4, 5) \\ 2 & 0 & (8, 9) \\ 2 & 1 & (9, 10) \\ 2 & 2 & (3, 4) \\ \hline \end{tabular}