MathDB

Combinatorial numbers are all even

Source: 2019 China TST Test 4 P6

March 29, 2019

number theorycombinatorics

Problem Statement

Given positive integer

n,k

such that

2 \le n <2^k

. Prove that there exist a subset

A

of

\{0,1,\cdots,n\}

such that for any

x \neq y \in A

,

{y\choose x}

is even, and

|A| \ge \frac{{k\choose \lfloor \frac{k}{2} \rfloor}}{2^k} \cdot (n+1)

Back to Problems View on AoPS