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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Sep 23, 2019 at 3:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .