A run of days that nets a multiple of n

Question

A trader logs her daily profit or loss for $n$ consecutive days. Each day's figure is a whole number, and it may be positive, negative, or zero. The numbers can be anything at all.

Prove that there is always a stretch of one or more consecutive days whose profits and losses add up to an exact multiple of $n$ .

Accepted Answer

The clean tool here is running totals combined with pigeonhole. Build the running totals. Let S0 = 0, and for each day k let Sk = (	ext{day 1}) + (	ext{day 2}) + \cdots + (	ext{day } k), the total profit through the end of day k. This gives n + 1 numbers: S0,\ S1,\ S2,\ \dots,\ Sn. Look at them modulo n. Divide each running total by n and keep only the remainder. There are only n possible remainders: 0, 1, 2, \dots, n-1. But we have n + 1 running totals. With more totals than possible remainders, the pigeonhole principle forces two of them to share the same remainder, say Si and Sj with i …

A run of days that nets a multiple of n

Your answer

More Brainteasers questions