6
$\begingroup$

I have posed the following question on math.stackexchange.com but have not received an answer. So I would like to seek experts' opinion here.

Consider the set of all binary sequence of length $n+1$, $B=\big\{(b_i)_{i=0}^n\,\big| b_i\in\{0,1\}, \forall i\big\}$. Construct a function $f: \{0,\cdots,n\}\times \{0,1\}\to \{0,\cdots, n\}$, such that $\forall (b_i)_{i=0}^n\in B,\,\exists i \colon f(i,b_i)=\sum_{j\ne i}b_j$.

What is a systematic way to construct this function?


Putting it more colloquially, we assign $n+1$ persons one-to-one to all the digits of an arbitrary binary sequence of length $n+1$. Each person can see but the digit assigned to him. Devise a strategy so that at least one person guesses correctly the sum of the remaining digits.

$\endgroup$
6
$\begingroup$

Since every person knows his assigned digit, the problem is equivalent to guessing the sum of all digits.

Label the persons with $0,1,...,n$. Let person $0$ guess $0$ when given a $0$, and $n+1$ when given a $1$. Let person $k$ guess $k$ for every $k\in \{1,...,n\}$.

At least one person can correctly guess the sum of all digits. So when they subtract their given digit from the guessed sum, at least one person can correctly guess the sum of the remaining digits.

$\endgroup$
  • 1
    $\begingroup$ +1 and accepted. Darn, it is so easy when the answer is revealed! I had person $k$ guess $k$ $\forall k$. But then the strategy is one short of covering all $n+2$ cases. Having person $0$ take care of the remaining two cases is the key and is brilliant. $\endgroup$ – Hans Sep 23 '19 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.