Prefix Sums and Divisibility: Olympiad Problems and Proofs

Original practice lesson: an IOQM-to-RMO learning bridge, with a harder counting extension. The multiple-choice questions support learning; they are not a reproduction of an official examination paper.

You will learn: turn a consecutive block into the difference of two running totals, use that representation to prove existence, and count blocks without counting any twice.

Before you start: signed integer addition, standard nonnegative remainders, and the pigeonhole principle. Revisit remainders and congruences if negative remainders are unfamiliar.

Choose your pace: first work through the three examples and Level 1. Then try the representation changes in Level 2. Level 3 and the proof challenges need longer written reasoning; they are not a speed test.

Three small checks before the new idea

In these checks, a_k means the entry in position k, and S_k means the sum of the first k entries. For example, S₂ = a₁ + a₂. The subscript is a position label, not a multiplication. We set S₀ = 0 for the total before the first entry. A boundary is a position before, between or after the entries; its running total is the sum of entries before it.

Try these on paper. If a check feels uncertain, read its repair before continuing. The third check becomes important when we count several blocks.

PSD-D1

The running totals of a list satisfy S₂ = 9 and S₅ = 4. What is a₃ + a₄ + a₅?

Solution PSD-D1

S₅ contains the first five entries and S₂ contains the first two. Subtracting cancels a₁ and a₂, leaving a₃ + a₄ + a₅ = S₅ − S₂ = 4 − 9 = −5.

Repair: Write both totals in full before subtracting. The first entry left over is numbered one more than the earlier boundary.

PSD-D2

What is the remainder of −7 on division by 5, using a remainder from 0 to 4?

Solution PSD-D2

Write −7 = 5 × (−2) + 3. The remainder is 3 because it lies between 0 and 4. Negative entries are allowed; the remainder labels still use the same five boxes.

Repair: Start with a multiple of 5 below −7, namely −10, then count up to −7.

PSD-D3

Five boundary positions have the same remainder. How many distinct pairs of different positions can be chosen?

Solution PSD-D3

There are 5 × 4 ordered choices of two different positions. Every pair was counted in both orders, so divide by 2: 5 × 4 ÷ 2 = 10. A pair of boundary positions will describe one interval, even if another interval has the same numerical sum.

Repair: List the pairs among three positions first: (1,2), (1,3), (2,3). Do not count (2,1) again.

Put totals at the boundaries

Suppose integers a₁, a₂, …, a_N are written in a fixed order. A nonempty consecutive block means all entries from one chosen position through the same or a later position, with no gaps. A single entry is allowed. We never rearrange the list.

Write S_k for the sum of the first k entries. Introduce S₀ = 0, the total before any entry has been taken. A list of N entries has N + 1 boundary sums: S₀ through S_N. Think of a boundary just before the first entry, between each pair of entries, and after the last entry.

For 0 ≤ i < j ≤ N, subtract the total at the earlier boundary from the total at the later boundary:

S_j − S_i = a_i+1 + a_i+2 + ⋯ + a_j.

The first i entries cancel. What remains begins at i + 1, ends at j, and contains j − i entries. This is why we look at running totals rather than only at the entries themselves. A difference between two original entries would not usually be the sum of a whole block.

The zero boundary is a bookkeeping tool; it is not an extra list entry. It lets a block beginning with a₁ use the same formula as every other block. We always use different boundaries i < j, so no empty block is counted.

Why matching remainders are useful

If S_i and S_j leave the same remainder on division by a positive integer m, their difference is a multiple of m. Conversely, if their difference is divisible by m, their remainders match. Thus a divisible block corresponds exactly to a pair of different boundary positions in the same remainder box.

The entries may be positive, negative or zero. The running totals need not rise. None of this changes the cancellation identity. For m = 5, use remainder labels 0, 1, 2, 3, 4 even for negative totals: −3 = 5(−1) + 2, so its label is 2. A zero block sum is allowed: 0 = m × 0 is divisible by every positive integer m.

Worked example 1: see all the endpoints

PSD-E1. In the ordered list 4, −7, 6, 2, −5, find every nonempty consecutive block whose sum is divisible by 5.

Solution PSD-E1. Only remainder 0 repeats, at boundaries 0, 4 and 5. Their three pairs give:

• (0,4): entries 1–4 have sum S₄ − S₀ = 5.
• (0,5): entries 1–5 have sum S₅ − S₀ = 0.
• (4,5): entry 5 alone has sum S₅ − S₄ = −5.

These are all the answers because every qualifying block must come from a repeated remainder. Notice the three different kinds of multiples: positive, zero and negative. The method handles them together.

Worked example 2: a guarantee without knowing the entries

PSD-E2. Prove that every list of seven integers contains a nonempty consecutive block whose sum is divisible by 7.

The previous example found all matching remainders in a known list. Now the entries are hidden. We cannot fill a numerical table, but we can still count its rows and possible remainder labels.

Solution PSD-E2. Form the eight boundary sums S₀, S₁, …, S₇. There are seven possible remainders modulo 7. The pigeonhole principle gives two different boundaries with matching remainders. Call the earlier one i and the later one j. Then S_j − S_i is divisible by 7 and equals the sum of the nonempty consecutive block from a_i+1 to a_j. This proves the claim.

We did not need one of the seven entries to be divisible by 7. We did not need the whole list to have divisible sum. We only needed two of the eight boundary sums to match. Adding S₀ also avoids a separate argument for a prefix sum that itself is divisible by 7.

The reusable statement and its limit

For every positive integer m, any list of m integers contains a nonempty consecutive block with sum divisible by m: use m + 1 boundary sums and m remainder boxes. For m ≥ 2, m − 1 entries do not give the same guarantee. A list of m − 1 ones has every nonempty block sum between 1 and m − 1. This counterexample proves that the length threshold is sharp. A particular shorter list may still work; it simply need not work.

Count positions, not just repeated values

Suppose a remainder box contains f boundary positions. There are f(f − 1) ways to choose a first and a different second position. This counts each pair twice, so the box contributes f(f − 1)/2 blocks. For each pair, place the smaller index first. That order gives a unique block. Conversely, the block’s endpoints recover its unique boundary pair.

Add this pair count over the remainder boxes. Blocks are allowed to overlap; they are counted separately when their endpoint pairs differ. We are not claiming that all the counted blocks can be selected disjointly.

Worked example 3: count without listing every block

PSD-E3. A list has eight integer entries. Among its nine boundary sums, four have remainder 0 modulo 3, three have remainder 1, and two have remainder 2. Exactly how many nonempty consecutive blocks have sum divisible by 3?

Solution PSD-E3. Remainder 0 contributes 4 × 3 ÷ 2 = 6 pairs; remainder 1 contributes 3 × 2 ÷ 2 = 3; remainder 2 contributes 2 × 1 ÷ 2 = 1. Thus there are exactly 6 + 3 + 1 = 10 blocks. The positions of the labels are not needed for this count: each pair in a box has one earlier and one later boundary. The pair-to-block correspondence ensures that none is missed or repeated.

Choose a representation that remembers the condition

Require an even number of entries

The block between boundaries i and j has length j − i. This length is even exactly when i and j have the same parity. To force even length, compare even-indexed boundaries with even-indexed boundaries, or odd with odd. Comparing an even boundary with an odd one cannot work. Inside either group, matching remainder labels still control divisibility.

For counting, label a boundary by (index parity, sum remainder). Two boundaries belong to the same box exactly when they satisfy both required conditions. For example, divisibility by 3 with even length gives six boxes: even/0, even/1, even/2, odd/0, odd/1 and odd/2. The boxes may be empty; do not assume an even distribution without proving it.

Require average 2 instead of sum zero

A block from a_i+1 through a_j has average 2 exactly when S_j − S_i = 2(j − i). Rearranging gives S_j − 2j = S_i − 2i. So define T_k = S_k − 2k. Equal transformed totals now identify the desired blocks.

This has a concrete meaning: replace each entry a by a − 2. A block averages 2 when its total excess above 2 is zero. For example, the pair −1, 5 becomes −3, 3 and has excess sum zero. Here we need equality of totals, not merely congruence modulo some number.

A first lower bound when the box sizes are unknown

If f ≥ 1 positions occupy one box, they make at least f − 1 pairs: choose one fixed position and pair it with each of the other f − 1 positions. Consequently, P positions spread across c occupied boxes create at least P − c same-box pairs. Empty boxes contribute nothing.

This bound is often enough. If eight boundary sums can take only five integer values, they give at least 8 − 5 = 3 equal pairs. A stronger exact minimum may need more work; the first proof challenge explains how balancing box sizes gives that minimum.

Where a correct idea can go wrong

• Leaving out S₀: you lose the boundary before the first entry, so blocks beginning there are missed.
• Starting at i rather than i + 1: S_j − S_i cancels entry i too.
• Pairing a boundary with itself: this would be an empty block; insist on i < j.
• Rejecting negative or zero sums: divisibility means being an integer multiple, with no positivity requirement.
• Counting repeated sums only once: distinct endpoint pairs are distinct blocks, even if their sums agree.
• Assuming the blocks are disjoint: pair counting allows overlapping intervals. Disjointness needs an additional argument, such as the separated ranges in PSD-T2.
• Calling a bound the minimum or maximum too early: prove the bound for all lists and then give a list attaining it.

Practise with feedback

Choose a starting level for a six-question session. Hints are welcome; the next question adjusts to your answers. Saving progress is optional and stays in this browser.

Interactive practice loads here. You can also use the complete question set below.

Nine graded questions

Use the interactive practice when available, or work through the same questions below. After a wrong answer, follow the repair and retry the reasoning on paper. A correct choice is a useful check, but it does not replace the written argument in a proof problem.

Level 1 · Question 1

Let Sₖ be the sum of the first k entries of a list of at least eight integers, with S₀ = 0. If S₂ and S₇ have the same remainder modulo 5, which block is guaranteed to have sum divisible by 5?

1. a₂ + a₃ + ⋯ + a₇
2. a₂ + a₃ + ⋯ + a₆
3. a₃ + a₄ + ⋯ + a₈
4. a₃ + a₄ + ⋯ + a₇

Hint 1

Think of S₂ as the total just before the desired block begins.

Hint 2

Expand S₇ − S₂ and cancel the first two entries.

Solution prefix-sums-divisibility-1

Answer: D. S₇ − S₂ = (a₁ + ⋯ + a₇) − (a₁ + a₂) = a₃ + ⋯ + a₇. Equal remainders make this difference divisible by 5. Its endpoints are 3 and 7, not 2 and 7.

If you were stuck: A boundary numbered i lies after entry i. The surviving block begins at entry i + 1; practise writing one subtraction in full.

Level 1 · Question 2

For the ordered list 2, −5, 4, −1, how many nonempty consecutive blocks have sum divisible by 4? Different positions count as different blocks.

1. 1
2. 2
3. 3
4. 4

Hint 1

Include the total before the first entry.

Hint 2

The five boundary sums are 0, 2, −3, 1, 0. Sort them by their remainders modulo 4.

Solution prefix-sums-divisibility-2

Answer: B. The remainders are 0, 2, 1, 1, 0. Remainder 0 occurs at boundaries 0 and 4, giving the whole list with sum 0. Remainder 1 occurs at boundaries 2 and 3, giving the single entry 4. No other remainder repeats, so there are exactly 2 blocks. Zero is divisible by 4 because 0 = 4 × 0.

If you were stuck: Do not drop S₀ or reject a sum of zero. If negative remainders cause trouble, use −3 = 4(−1) + 1.

Level 1 · Question 3

What is the smallest L such that every list of L integers, including negative integers, contains a nonempty consecutive block whose sum is divisible by 6?

1. 5
2. 7
3. 6
4. 12

Hint 1

A list of L entries has L + 1 boundary sums.

Hint 2

For sufficiency use the six remainder boxes. For necessity test a shorter list consisting only of ones.

Solution prefix-sums-divisibility-3

Answer: C. For L = 6, the seven boundary sums S₀ through S₆ occupy six remainder boxes; two match and their difference is a nonempty block sum divisible by 6. Five ones do not work: every nonempty block has sum between 1 and 5. Any still shorter list of ones also avoids a multiple of 6. Thus the smallest L is 6. Negative entries do not change the subtraction identity or the number of remainder boxes.

If you were stuck: A least-value answer needs two parts: prove that the proposed value always works, then exhibit a shorter list that fails.

Level 2 · Question 4

Ten integers a₁, …, a₁₀ are written in order. Which collection gives a direct pigeonhole proof that some nonempty block has both even length and sum divisible by 5? As usual Sₖ is the sum of the first k entries.

1. S₀, S₂, S₄, S₆, S₈, S₁₀, grouped by their remainders modulo 5
2. The ten entries, grouped by their remainders modulo 5
3. S₁, S₃, S₅, S₇, S₉, grouped by their remainders modulo 5
4. S₀, S₁, S₂, S₃, S₄, grouped by their remainders modulo 5

Hint 1

Even block length means that the two boundary indices have the same parity.

Hint 2

There are six even-indexed boundary sums but only five possible remainders.

Solution prefix-sums-divisibility-4

Answer: A. The six even-indexed sums occupy five remainder boxes, so two of them, Sᵢ and Sⱼ with i < j, match. Their difference is divisible by 5 and their index difference j − i is even. It describes the nonempty block aᵢ₊₁ through aⱼ. The five odd-indexed sums need not repeat a remainder; grouping original entries does not turn a collision into the required block sum.

If you were stuck: Translate both conditions before counting: equal sum remainders control divisibility, while equal index parity controls length.

Level 2 · Question 5

For five integer entries, let Sₖ be the sum of the first k entries, with S₀ = 0, and define Tₖ = Sₖ − 2k. The values T₀, T₁, …, T₅ are 0, 2, −1, 2, 4, 5. Which block must have average exactly 2?

1. Entries 1 through 3
2. Entries 2 through 4
3. Entries 3 through 5
4. Entries 2 through 3

Hint 1

A block of length j − i has average 2 exactly when Sⱼ − Sᵢ = 2(j − i).

Hint 2

Rearrange that equation into Tⱼ = Tᵢ, then locate the repeated value.

Solution prefix-sums-divisibility-5

Answer: D. T₁ = T₃ = 2, so S₃ − 6 = S₁ − 2. Hence S₃ − S₁ = 4. This is the sum of entries 2 and 3, a block of length 2, whose average is 4 ÷ 2 = 2. As a check, the boundary sums are 0, 4, 3, 8, 12, 15 and the entries are 4, −1, 5, 4, 3; the selected pair is −1, 5.

If you were stuck: Subtracting 2k changes the question from an average to equality of transformed totals. Remember that the number of entries between boundaries i and j is j − i.

Level 2 · Question 6

A list has six integer entries. Among its seven boundary sums S₀, …, S₆, the numbers leaving remainders 0, 1, 2, 3 on division by 4 are respectively 3, 2, 1, 1. How many nonempty consecutive blocks have sum divisible by 4?

1. 3
2. 4
3. 5
4. 7

Hint 1

Every pair within one remainder box produces one block.

Hint 2

Count 3 × 2 ÷ 2 pairs in the first box and 2 × 1 ÷ 2 in the second.

Solution prefix-sums-divisibility-6

Answer: B. The three positions in remainder box 0 produce 3 distinct pairs. The two in box 1 produce 1 pair. The two singleton boxes contribute none. Thus there are exactly 3 + 1 = 4 blocks. For each pair, take the earlier index first; different pairs give different endpoint pairs, so nothing is counted twice. No knowledge of the order of the remainder labels is needed for this count.

If you were stuck: A box containing three positions gives three pairs, not just one collision or two. Count intervals by endpoints, not by distinct numerical sums.

Level 3 · Question 7

For a list of eleven arbitrary integers, count the nonempty consecutive blocks whose length is even and whose sum is divisible by 3. What is the smallest possible number of such blocks?

1. 6
2. 3
3. 5
4. 9

Hint 1

Separate the twelve boundary positions into six even indices and six odd indices.

Hint 2

Within each parity group distribute six positions among three remainder boxes; then seek a list attaining the resulting bound.

Solution prefix-sums-divisibility-7

Answer: A. The even-indexed boundary positions are 0, 2, 4, 6, 8, 10; the odd-indexed positions are 1, 3, 5, 7, 9, 11. Each group therefore contains six positions. Within either parity group, let c be the number of occupied remainder boxes. A box with t ≥ 1 positions makes t(t − 1)/2 pairs, which is at least t − 1. Adding over the group gives at least 6 − c ≥ 3 pairs because c ≤ 3. The even and odd groups therefore give at least 3 + 3 = 6 qualifying blocks, and no block is counted in both groups. Eleven ones attain 6: a block sum equals its length, so an even length with sum divisible by 3 must have length 6 (length 12 is unavailable). There are 11 − 6 + 1 = 6 such blocks. Therefore the minimum is 6.

If you were stuck: The lower bound alone is not a minimum proof. Also give a concrete list with exactly that many blocks. The parity split must happen before counting remainder pairs.

Level 3 · Question 8

Four integers are written in order, and none is divisible by 5. What is the largest possible number of nonempty consecutive blocks with sum divisible by 5?

1. 3
2. 5
3. 4
4. 6

Hint 1

The five boundary remainders cannot be equal at adjacent positions.

Hint 2

A fixed remainder can occur at most three times. Consider a box of size three, and then the case where every box has size at most two.

Solution prefix-sums-divisibility-8

Answer: C. Adjacent equal boundary remainders would make the entry between them divisible by 5, which is forbidden. A remainder can therefore appear at most at three of the five positions, such as positions 0, 2, 4. Four nonadjacent occurrences would need at least seven positions: four occupied positions and at least one separating position in each of the three gaps. Only five boundary positions are available. If one box has three positions, it contributes 3 pairs; the other two positions contribute at most 1 more pair. If no box has three, every box has at most two positions, so at most two boxes can contribute a pair, giving at most 2. Thus the overall upper bound is 4. It is attained by 1, −1, 1, −1: the prefix remainders are 0, 1, 0, 1, 0, giving 3 + 1 = 4 pairs. None of its entries is divisible by 5.

If you were stuck: Here an extra restriction prevents arbitrary box sizes. First use the ban on divisible entries to exclude adjacent matching boundary remainders; only then maximise the pair count.

Level 3 · Question 9

A row consists of four entries equal to +1 and three entries equal to −1, in any order. What is the smallest possible number of nonempty consecutive blocks with sum exactly zero?

1. 3
2. 2
3. 4
4. 6

Hint 1

Use equal boundary sums, not merely equal remainders.

Hint 2

Show that the largest and smallest boundary sums differ by at most 4, so at most five different integer values occur among eight boundaries.

Solution prefix-sums-divisibility-9

Answer: A. Let M and m be the largest and smallest boundary sums. If a position with sum m occurs before one with sum M, their difference uses at most the four +1 entries, so M − m ≤ 4. If M occurs first, the fall to m uses at most the three −1 entries, giving M − m ≤ 3. In either case the eight boundaries occupy at most five integer values. A value occurring t times gives at least t − 1 pairs, so there are at least 8 − 5 = 3 zero-sum blocks. The order +1,+1,+1,+1,−1,−1,−1 attains 3: its boundary sums are 0,1,2,3,4,3,2,1, where only 1,2,3 repeat, each twice. The minimum is 3.

If you were stuck: Equal exact totals force sum zero. Bound the range of the running total in both possible orders of its minimum and maximum; do not assume the minimum always comes first.

From an answer to a proof

Attempt these after Level 2; challenges PSD-C1 and PSD-C3 extend the counting ideas in Level 3. Use a hint only when needed. The rubrics are for self-review, not an automatic grade of an arbitrary proof.

PSD-C1: How many divisible blocks are forced?

Let N ≥ 1 and m ≥ 2 be integers. Write N + 1 = mq + r, where q and r are integers and 0 ≤ r < m. Among all ordered lists of N integers, prove that the smallest possible number of nonempty consecutive blocks with sum divisible by m is m q(q − 1)/2 + rq.

Hint 1

Count pairs of boundary positions within each of the m remainder boxes. What happens if one box has at least two more positions than another?

Hint 2

If the two sizes are a and b with a ≥ b + 2, move one position from the larger box to the smaller. The number of pairs falls by a − b − 1. For attainment, test a list of N ones.

Solution PSD-C1

Let f₀, …, f_m−1 be the sizes of the remainder boxes containing the N + 1 boundary sums, including S₀. A box with f positions contributes f(f − 1)/2 pairs, so the desired count is the sum of these m contributions.

Suppose two sizes are a and b with a ≥ b + 2. Replace them by a − 1 and b + 1. The first box loses a − 1 pairs and the second gains b pairs. The total therefore decreases by a − b − 1, a positive integer. Repeating this operation eventually leaves sizes differing by at most one, because a nonnegative integer pair count cannot decrease forever. Thus a minimum over all possible size distributions occurs at balanced sizes.

Since N + 1 = mq + r, the balanced distribution has r boxes of size q + 1 and m − r of size q. Its pair count is r q(q + 1)/2 + (m − r)q(q − 1)/2 = m q(q − 1)/2 + rq. Every actual list gives one of these size distributions, so the same lower bound applies to every list.

We must still show that an actual list attains this distribution. Take N entries all equal to 1. Its boundary sums are 0, 1, …, N. Each run of m successive integers contributes once to every remainder box, and the final r values contribute once more to r boxes. The sizes are exactly q or q + 1. Therefore the bound is attained. When N + 1 < m, q = 0 and the formula correctly gives zero.

Self-review rubric PSD-C1

• Define all N + 1 boundary positions and prove the pair-to-block correspondence.
• Establish the pair count and justify why balancing cannot increase it.
• Derive the stated formula from r sizes q + 1 and m − r sizes q.
• Use N ones to attain the bound, including the q = 0 boundary case.

PSD-C2: Divisibility with an even-length condition

Let m ≥ 2 be an integer. Prove that every list of 2m integers contains a nonempty consecutive block of even length whose sum is divisible by m. Show that 2m cannot be replaced by 2m − 1.

Hint 1

Use only the boundary positions with even indices.

Hint 2

For the sharpness example, try 0, 1, 0, 1, …, 0, a list with 2m − 1 entries.

Solution PSD-C2

Define S₀ = 0 and S_k = a₁ + ⋯ + a_k. Consider S₀, S₂, …, S_2m. There are m + 1 of these sums and only m possible remainders. Hence S_i and S_j have the same remainder for some even i < j.

The block a_i+1, …, a_j has sum S_j − S_i, divisible by m. Its length j − i is positive and even. This proves the guarantee for every list, including lists with negative entries.

Now take the alternating list 0, 1, 0, 1, …, 0 of length 2m − 1. Any even-length block has length 2t for an integer t with 1 ≤ t ≤ m − 1. Because the entries alternate, this block contains exactly t zeros and t ones, whether it begins with zero or one. Its sum is t, strictly between 0 and m, and hence is not divisible by m. Thus 2m − 1 entries do not suffice; truncating this counterexample also rules out a smaller universal threshold.

Self-review rubric PSD-C2

• Use m + 1 even-indexed boundary sums, including S₀.
• Explain both consequences of a collision: divisibility and even positive length.
• Give the alternating counterexample of exactly 2m − 1 entries.
• Check every possible even-length block of the counterexample.

PSD-C3: Turn an average into a return to the same height

Five entries equal to 1 and five entries equal to 3 are arranged in a row. Prove that at least four proper nonempty consecutive blocks have average exactly 2. Here proper means that the block is not the entire ten-entry row. Show that four is the best possible guarantee.

Hint 1

Replace every entry a by a − 2. Now a block has average 2 exactly when its new sum is zero.

Hint 2

The new entries are five −1s and five +1s. Bound the range of their eleven boundary sums, count equal pairs, then remove the pair corresponding to the whole row.

Solution PSD-C3

Set b_k = a_k − 2 and T₀ = 0, T_k = b₁ + ⋯ + b_k. There are five steps +1 and five steps −1. For boundaries i < j, the original block has average 2 exactly when its sum is 2(j − i), or equivalently when T_j − T_i = 0.

Let M and m be the largest and smallest T values. If a minimum occurs before a maximum, the rise M − m uses at most the five +1 steps. If a maximum occurs before a minimum, the fall uses at most the five −1 steps. In either order M − m ≤ 5. The eleven integer boundary sums therefore have at most six distinct values.

If a value appears f ≥ 1 times, it contributes f(f − 1)/2 pairs, at least f − 1. Summing over at most six occupied values gives at least 11 − 6 = 5 equal pairs, hence at least five blocks with average 2. The whole row has average 2 and corresponds to exactly the one pair (0,10). Removing it leaves at least four proper blocks.

For equality, use 1,1,1,1,1,3,3,3,3,3. The transformed boundary sums are 0,−1,−2,−3,−4,−5,−4,−3,−2,−1,0. The five values 0,−1,−2,−3,−4 each occur twice, while −5 occurs once. They produce exactly five equal pairs. After excluding the whole row, exactly four proper blocks remain. Therefore four is the best possible guarantee.

Self-review rubric PSD-C3

• Translate average 2 into equality of transformed boundary sums.
• Prove the range bound in both possible orders of the extreme values.
• Use the number of occupied values to force five equal pairs, then exclude the whole-row pair once.
• Give and verify an arrangement attaining exactly four proper blocks.

Explain the method in your own words

Without looking back, explain why a list of m integers has enough boundary sums to force a block divisible by m. Your explanation should identify the objects and boxes, mention S₀, recover the precise block from two indices, and explain why it is nonempty. Then explain what extra label would force even length.

If you can calculate but cannot explain the last step, revisit the cancellation identity and PSD-E2. If the counting is uncertain, draw three labelled boundary positions and list their three pairs before returning to PSD-E3. If Level 3 needed hints, return later and try one problem again without opening its solution.

Sources and your next step

This original lesson builds from IOQM concepts towards RMO-style proof writing. It is not an official paper or a claim to reproduce the difficulty of every RMO or INMO problem. HBCSE lists RMO as six proof problems in three hours and INMO as six proof problems in four and a half hours. The optional final challenges develop longer counting arguments.

HBCSE 2026–27 programme · Official past papers. Stage information checked 2 October 2026; official questions are linked, not reproduced.

Continue with five IOQM mock papers or five RMO mock papers, then use the India selection guide to check your next stage. Or return to the combinatorics learning path.