MathDB

Let

n \geq 2

be a positive integer and let

A, B

be two finite sets of integers such that

|A| \leq n

. Let

C

be a subset of the set

\{(a, b) | a \in A, b \in B\}

. Achilles writes on a board all possible distinct differences

a-b

for

(a, b) \in C

and suppose that their count is

d

. He writes on another board all triplets

(k, l, m)

, where

(k, l), (k, m) \in C

and suppose that their count is

p

. Show that

np \geq d^2.

Problem Statement