MathDB

Socialists Republic Of Czechoslovakia 8

Source: IMO LongList 1959-1966 Problem 42

September 2, 2004

SequenceDivisibilitynumber theoryIMO LonglistIMO Shortlist

Problem Statement

Given a finite sequence of integers

a_{1},

a_{2},

...,

a_{n}

for

n\geq 2.

Show that there exists a subsequence

a_{k_{1}},

a_{k_{2}},

...,

a_{k_{m}},

where

1\leq k_{1}\leq k_{2}\leq...\leq k_{m}\leq n,

such that the number

a_{k_{1}}^{2}+a_{k_{2}}^{2}+...+a_{k_{m}}^{2}

is divisible by

n.

Note by Darij: Of course, the

1\leq k_{1}\leq k_{2}\leq ...\leq k_{m}\leq n

should be understood as

1\leq k_{1}<k_{2}<...<k_{m}\leq n;

else, we could take

m=n

and

k_{1}=k_{2}=...=k_{m},

so that the number

a_{k_{1}}^{2}+a_{k_{2}}^{2}+...+a_{k_{m}}^{2}=n^{2}a_{k_{1}}^{2}

will surely be divisible by

n.

Back to Problems View on AoPS