MathDB

Binary sequences with n terms

Source: Kürschák 2015, problem 3

October 7, 2016

combinatoricsBinary

Problem Statement

Let

Q=\{0,1\}^n

, and let

A

be a subset of

Q

with

2^{n-1}

elements. Prove that there are at least

2^{n-1}

pairs

(a,b)\in A\times (Q\setminus A)

for which sequences

a

and

b

differ in only one term.

Back to Problems View on AoPS