MathDB

2^k+1 integers, select k+2 with given property

Source: Kürschák 1999, problem 3

July 15, 2014

combinatorics unsolvedcombinatorics

Problem Statement

We are given more than

2^k

integers, where

k\in\mathbb{N}

. Prove that we can choose

k+2

of them such that if some of our selected numbers satisfy

x_1+x_2+\dots+x_m=y_1+y_2+\dots+y_m

where

x_1<\dots<x_m

and

y_1<\dots<y_m

, then

x_i=y_i

for any

1\le i\le m