MathDB

For each positive integer

n

, define

f(n)

to be the least positive integer for which the following holds:
For any partition of

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

into

k>1

disjoint subsets

A_1, \dots, A_k

, all of the same size, let

P_i(x)=\prod_{a\in A_i}(x-a)

. Then there exist

i\neq j

for which

\deg(P_i(x)-P_j(x))\geq \frac{n}{k}-f(n)

a) Prove that there is a constant

c

so that

f(n)\le c\cdot \sqrt{n}

for all

n

.
b) Prove that for infinitely many

n

, one has

f(n)\ge \ln(n)

P3