 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/discrete-mathematics-continuous-mathematics-and-probability/3/d/solution

Assume

n \geq 1

and list the elements of

X

a_{1}, \dots, a_{n}

s_{j} = a_{1} + \dots + a_{j}

for

1 \leq j \leq n

. If one is divisible by

n

, its corresponding nonempty prefix is a suitable

Y

Otherwise the

n

n - 1

i < j

with

s_{i} \equiv s_{j} (mod n)

. Thus

s_{j} - s_{i} = a_{i + 1} + \dots + a_{j}

is divisible by

n

, giving a nonempty subset

Y = {a_{i + 1}, \dots, a_{j}}

Therefore a nonempty $Y$ exists. This strengthens the literal assertion, which would otherwise allow the trivial empty set with sum zero.

 New to topics? Read the docs here!