MathDB

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

March 26, 2021

Subsetspartitioncombinatorics

Problem Statement

k > 1

is fixed. Show that for

n

sufficiently large for every partition of

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

into

k

disjoint subsets we can find

a \neq b

such that

a

and

b

are in the same subset and

a+1

and

b+1

are in the same subset. What is the smallest

n

for which this is true?