Skip to main content.

Solution to puzzle 46: Consecutive subsequence

Let c1, ... , cn be any sequence of n integers.
Consider sequence ai, for i = 1, ... , n, the sum (modulo n) of the first i elements of c1, ... , cn.
If any ai = 0, then we have found a consecutive subsequence the sum of whose elements is a multiple of n.

Otherwise, ai 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, aj and ak, with j < k, such that aj = ak.
Hence 0 congruent to ak − aj congruent to cj+1 + ... + ck (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. (Adobe) Portable Document Format The Pigeonhole Principle

Source: Traditional

Back to top