5

Part of 1978 Swedish Mathematical Competition

Problems(1)

a,b are in the same subset and a+1,b+1 in the same subset of partion of

Source: 1978 Swedish Mathematical Competition p5

k > 1

is fixed. Show that for

n

sufficiently large for every partition of

\{1,2,\dots,n\}

k

disjoint subsets we can find

a \neq b

a

b

are in the same subset and

a+1

b+1

are in the same subset. What is the smallest

n

for which this is true?

Subsetspartitioncombinatorics