TIFR CSE 2023 | Part B | Question: 4

Question

Amar, Balu, and Chhaya are three friends and they play the following game. Chhaya first chooses a number $k \in U$ where $U=\{1,2, \ldots, 127\}$. She either gives $k$ to both Amar and Balu, or else she gives $k$ to Amar and $k+1$ to Balu. Amar computes a function $f: U \rightarrow\{0,1\}^{n}$ on the number he receives from Chhaya and sends the output of this function to Balu. Using this output and his own input, Balu has to decide whether Chhaya gave the same number to Amar and him, or if she gave numbers that differed by $1.$ What is the minimal $n$ that allows Balu to distinguish between these two cases?

• A. $1$
• B. $2$
• C. $7$
• D. $127$
• E. $128$

Comments

Amar will create a function that will determine that the number given is odd or even. If both their numbers are odd/even simultaneously then numbers are same else different. So using only n=1 we can create a division between odd and even number like if odd then 0 and if even then 1. So answer A.

Answer 1

Amar and Balu can use $f$ such that $f$ assigns different values to consecutive numbers ie they only need $2$ distinct elements in the range of $f$, example of one such function is $f : U \rightarrow \{0, 1\}, f(x) = x \text{ mod } 2$.

Balu will say Chaya gave same numbers to both of them if the output received from Amar and the output calculated by using his own input are same, otherwise he'll say Chaya gave them numbers that differ by $1$.

$\therefore$ the smallest value of $n$ is $1$.

Answer – A.