MathDB

partition into subsets not containing convex sequences

Source:

May 30, 2010

inductioninequalitiescombinatorics proposedcombinatorics

Problem Statement

Given an integer

n\ge3

, prove that the set

X=\{1,2,3,\ldots,n^2-n\}

can be divided into two non-intersecting subsets such that neither of them contains

n

elements

a_1,a_2,\ldots,a_n

with

a_1<a_2<\ldots<a_n

and

a_k\le\frac{a_{k-1}+a_{k+1}}2

for all

k=2,\ldots,n-1