Here’s an example: Let’s say our multi-set contains the elements {1,2,2,3,4,4}. Now lets calculate the cumulative frequencies, i.e bi’s. b0 = 0, b1 = 1, b2 = 3, b3 = 5, b4 = 8, b5 = 12, b6 = 16. Now take the remainders of each of these with 6, which gives {0,1,3,5,2,0,4}. Here we have b0%6 == b5%6, so (b5-b0)%6==0 => b5-b0 is divisible by 6 (or N in this case). what is b5-b0, it’s nothing but
{1+2+2+3+4}, which is the sum of contiguous elements of the multiset. Why did this work? There were 7 bi’s (b0-b6), but bi%6 can take only values 0-5 (6 values), so atleast 2 bi%6’s must be equal.
6 Likes