MathDB

power of 2

Source: Ireland 1997

July 3, 2009

pigeonhole principlecombinatorics unsolvedcombinatorics

Problem Statement

Let

A

be a subset of

\{ 0,1,2,...,1997 \}

containing more than

1000

elements. Prove that either

A

contains a power of

2

(that is, a number of the form

2^k

with k\equal{}0,1,2,...) or there exist two distinct elements

a,b \in A

such that a\plus{}b is a power of

2