# Solution to puzzle 46: Consecutive subsequence

Let c_{1}, ... , c_{n} be any sequence of n integers.

Consider sequence a_{i}, for i = 1, ... , n, the sum (modulo n) of the first i elements of c_{1}, ... , c_{n}.

If any a_{i} = 0, then we have found a consecutive subsequence the sum of whose elements is a multiple of n.

Otherwise, a_{i} has n elements, which can take only n−1 possible values: 1, 2, ... , n−1.

Then, by the Pigeonhole Principle, there exists a pair of elements, a_{j} and a_{k}, with j < k, such that a_{j} = a_{k}.

Hence 0 a_{k} − a_{j} c_{j+1} + ... + c_{k} (mod n), and again we have found a consecutive subsequence the sum of whose elements is a multiple of n.

Therefore, given any sequence of n integers, there exists a consecutive subsequence the sum of whose elements is a multiple of n.

## Further reading

- The Puzzlers' Pigeonhole
- The Pigeonhole Principle

Source: Traditional

Back to top