Coded Paired Information

Most people would be able to guess that the answer is 10, which can be obtained in a variety of ways. The harder part is to explain why we need at least 10, or why it cannot be done with 9 or fewer pairs. More generally, we need to ask $n$ questions (where $n \geq 3$ ).

Showing that n questions is a lower bound

Let each of the numbers that they are thinking of be denoted by $a_i$ . Then, when we ask person $i$ and $j$ , we are given information of $P_{ij} = a_i \times a_j$ . We have $n$ variables, and naively speaking we would expect that we need at least $n$ equations in order to solve this. However, this is only true if we were restricted to linear equations. For example, if we were told $\sum ( a_i - i ) ^2 = 0$ in 1 equation, we can immediately conclude that $a _ i = i$ . Hence, it is not immediately obvious that we need at least $n$ equations.

How then do we convert this into a linear equation? Well, we simply take the logarithm of each equation. Set $b_i = \log a_i$ , which is allowed since $a_i$ is positive. Now, when we're told the product, we know that $\log P_{ij} = b_i + b_j$ , which is a linear equation. Now, it is obvious that with $n$ variables, we need at least $n$ linear equations to obtain a unique solution, and thus $n$ is a lower bound.

Showing that n questions is sufficient

It remains to show that for $n \geq 3$ , by asking certain $n$ pairs, we can obtain all of the individual values. We pick the first 3 people, and ask for their pairwise product. Then, we know the value of $b_1 + b_2, b_2 + b_3, b_3 + b_1$ , from which we can easily determine $b_1, b_2, b_3$ and hence $a_1, a_2, a_3$ . For example, $b_1 = \log P_{12} + \log P_{13} - \log P_{12}$ .

Now, for each of the remaining $n-3$ people, we ask for the product $P_{1i}$ of person 1 and person $i$ . Since we already know $b_1 = \log a_1$ , we can calculate that $b_i = \log P_{1i} - b_1$ and hence $a_i$ .

Hence, since $n$ is a lower bound that can be achieved, it is the minimum.

Let the numbers thought by the $10$ people be $a,b,c,d,e,f,g,h,i,j$ respectively.Now lets first focus on how to determine the numbers of first three people $(ie. a,b,c).$ So,after inquiring we get $ab=x,bc=y,ca=z$ where $x,y,z$ are numbers[which we will know after inquiry].By this we will be able to determine the numbers $a,b,c$ individually.So we needed $3$ pairs for this.We do the same for $(d,e,f)$ and $(g,h,i).$ After doing all this,we get to know $9$ numbers.So we need one last pair- $ij$ so as to determine $j.$ Therefore,totally $3+3+3+1=\boxed{10}$ pairs are required to know all the $10$ numbers.