Guessing the number of other $1$'s in a binary sequence

161 Views Asked by At

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\ni 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 other than his own.


Epilogue: It was answered brilliantly on Mathoverflow.net after I posted the question there.

1

There are 1 best solutions below

0
On

The following is the answer by Bullet51 posted on MO.
https://mathoverflow.net/a/342264/32660

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.