MathDB

so much nt in bulgarian mo 2004 :) [Cauchy-Davenport theorem

Source: Bulgarian Math Olympiad MO 2004, problem 6

May 17, 2004

inductionnumber theory unsolvednumber theory

Problem Statement

Let

p

be a prime number and let

0\leq a_{1}< a_{2}<\cdots < a_{m}< p

and

0\leq b_{1}< b_{2}<\cdots < b_{n}< p

be arbitrary integers. Let

k

be the number of distinct residues modulo

p

that a_{i}\plus{}b_{j} give when

i

runs from 1 to

m

, and

j

from 1 to

n

. Prove that a) if m\plus{}n > p then k \equal{} p; b) if m\plus{}n\leq p then k\geq m\plus{}n\minus{}1.