Solution to puzzle 46: Consecutive subsequence

Let c₁, ... , 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₁, ... , 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

1. The Puzzlers' Pigeonhole
2. The Pigeonhole Principle

Source: Traditional

Back to top