3

Part of 2012 China National Olympiad

Problems(2)

There exist a increasing sequence

Source: 2012 China Mathematical Olympaid P3

M>2

, there exists an increasing sequence of positive integers

a_1<a_2<\ldots

a_i>M^i

i

; 2) There exists a positive integer

m

b_1,b_2,\ldots ,b_m\in\left\{ -1,1\right\}

n=a_1b_1+a_2b_2+\ldots +a_mb_m

n\in\mathbb{Z}/ \{0\}

ceiling functionalgebra proposedalgebra

Least k for which there exist x,y,z

Source: 2012cmo,problem6

Find the smallest positive integer

k

such that, for any subset

A

S=\{1,2,\ldots,2012\}

|A|=k

, there exist three elements

x,y,z

A

x=a+b

y=b+c

z=c+a

a,b,c

S

and are distinct integers.
Proposed by Huawei Zhu

modular arithmeticpigeonhole principleinequalitiescombinatorics proposedcombinatorics