MathDB

Differences equal to a power of 2

Source: Kürschak 2008, problem 2

July 6, 2014

combinatorics unsolvedcombinatorics

Problem Statement

Let

n\ge 1

and

a_1<a_2<\dots<a_n

be integers. Let

S

be the set of pairs

1\le i<j\le n

for which

a_j-a_i

is a power of

2

, and

T

be the set of pairs

1\le i<j\le n

with

j-i

a power of

2

. (Here, the powers of

2

are

1,2,4,\dots

.) Prove that

|S|\le |T|

.

Back to Problems View on AoPS