Proving Subset Sum/Difference Properties with PHP

Remainders as Pigeonholes

A vast number of problems in number theory revolve around divisibility by some integer $n$. When you see such a problem, it should immediately trigger the thought: "What are the possible remainders when a number is divided by $n$?" These remainders are $0,1,2,\dots ,n-1$. There are exactly $n$ of them, which makes them perfect candidates for our pigeonholes.

Let's formalize this. Given any integer $a$, the division algorithm guarantees that we can write $a=nq+r$, where $r$ is the remainder and $0\le r<n$. This remainder is unique. In modular arithmetic notation, we write $a\equiv r(\mathrm{mod}n)$.

The core strategy is simple:

• Pigeons: The set of integers you are analyzing.
• Pigeonholes: The $n$ possible remainders modulo $n$.

If you have at least $n+1$ integers (pigeons) and you consider their remainders upon division by $n$ (the $n$ holes), the Pigeonhole Principle guarantees that at least two of the integers must have the same remainder. This simple fact has profound consequences.

Let's watch a video that demonstrates this fundamental application.

As the video showed, if two numbers $a_i$ and $a_j$ have the same remainder modulo $n$, then $a_i\equiv r(\mathrm{mod}n)$ and $a_j\equiv r(\mathrm{mod}n)$. Subtracting them gives $a_i-a_j\equiv r-r\equiv 0(\mathrm{mod}n)$, which is precisely the definition of $a_i-a_j$ being a multiple of $n$.

The Subset Sum Problem

We can extend this idea beyond just differences. A classic and slightly more advanced application involves proving the existence of a subset of numbers whose sum has a specific property. This requires a more clever choice of pigeons.

A famous result states: Given any set of $n$ integers, there exists a non-empty subset whose sum is divisible by $n$.

To prove this, we can't just use the integers themselves as pigeons, because we only have $n$ of them for $n$ holes, which isn't enough to force a collision. Instead, we construct a special set of n pigeons: the partial sums.

Let the set be $S=\{a_1,a_2,\dots ,a_n\}$. Consider these $n$ sums:

• $s_1=a_1$
• $s_2=a_1+a_2$
• ...
• $s_n=a_1+a_2+\cdots +a_n$

Now, we analyze the remainders of these $n$ sums when divided by $n$. There are two possibilities:

1. One of the sums is divisible by $n$: If some sum $s_k$ has a remainder of 0 when divided by $n$, we're done! The subset $\{a_1,a_2,\dots ,a_k\}$ has a sum that is divisible by $n$.

2. None of the sums are divisible by $n$: If no $s_k$ is divisible by $n$, then their remainders must come from the set $\{1,2,\dots ,n-1\}$. We have $n$ sums (pigeons) but only $n-1$ possible remainders (pigeonholes). By the PHP, two sums, say $s_i$ and $s_j$ (with $i<j$), must have the same remainder modulo $n$.
   As we saw before, this means their difference, $s_j-s_i$, is divisible by $n$.
   What is this difference?
   $s_j-s_i=(a_1+\cdots +a_i+a_{i+1}+\cdots +a_j)-(a_1+\cdots +a_i)=a_{i+1}+a_{i+2}+\cdots +a_j$
   This is the sum of the elements in the subset $\{a_{i+1},a_{i+2},\dots ,a_j\}$, and this sum is divisible by $n$.

In either case, we find a subset with the desired property. The following resource provides a concise written proof of this exact result.

This technique of using partial sums is a powerful pattern for solving problems related to subset sums and divisibility.

Practice Problems

Now it's your turn to apply these number-theoretic PHP techniques. For each problem, carefully identify your pigeons and pigeonholes.

1. Difference of Squares: Prove that among any 7 perfect squares, there exist two whose difference is divisible by 10.

   • Hint: What are the possible last digits of a perfect square (i.e., remainders modulo 10)? How many distinct possibilities are there? These are your pigeonholes.

2. Summing to 102: Show that in any set of 27 different positive odd numbers, all less than 100, there is at least one pair whose sum is 102.

   • Hint: This is a "sum" problem, but not with partial sums. Instead, construct your pigeonholes by pairing up numbers that add to 102. For example, $(3,99)$, $(5,97)$, etc. How many such pairs are there? Are there any odd numbers left over that don't fit in a pair?

3. The Repunit Problem: A "repunit" is a number consisting only of the digit 1 (e.g., 1, 11, 111). Prove that for any positive integer $n$ that is not divisible by 2 or 5, there is a multiple of $n$ that is a repunit.

   • Hint: This is a classic Olympiad problem. Consider the first $n$ repunits: $1,11,111,\dots ,\underset{n}{\underbrace{11\dots 1}}$. What are their remainders when divided by $n$? Apply the same logic as the subset sum problem. If two repunits $R_i$ and $R_j$ (with $i<j$) have the same remainder, what can you say about their difference, $R_j-R_i$? The fact that $n$ is not divisible by 2 or 5 is crucial.

You can find excellent worked solutions for problems very similar to #1 and #2 in the February-March 2011 Segment 4 PDF from AwesomeMath. Problem 2 in that document is almost identical to practice problem #1 here, and problem 8 covers the logic for #2. Problem 7 in the "Practice Problems" section of that same PDF is exactly practice problem #3. Try to solve them on your own first!

Conclusion

In this lesson, you've combined the Pigeonhole Principle with your knowledge of number theory to prove some non-obvious results. This is a significant step toward the kind of creative problem-solving required in math Olympiads.

Key Takeaways:

• When a problem involves divisibility by $n$, the $n$ possible remainders $\{0,1,\dots ,n-1\}$ serve as natural pigeonholes.
• To prove that a difference is divisible by $n$, you can show that two numbers from a sufficiently large set must share the same remainder modulo $n$.
• To prove that a subset sum is divisible by $n$, you can use the partial sums $\{s_1,s_2,\dots ,s_n\}$ as your pigeons. Either one sum is divisible by $n$, or two sums share the same remainder, leading to a sub-interval sum that is divisible by $n$.
• Sometimes, pigeonholes can be constructed by pairing elements that have a desired property (e.g., summing to a target value).

In our next lesson, we will tackle one of the most famous results proven with the Pigeonhole Principle: the Erdős-Szekeres theorem, which guarantees the existence of long monotonic subsequences within any sequence of numbers. This will be our final lesson on PHP before moving on to new principles.