Sometime around 25 years ago, Dr. Jeffrey Vaaler at UT Austin gave me the following problem.. He needed the result as a lemma for a paper he was working on.
Let $n$ be a square-free integer with $k$ distinct prime factors and thus $\sigma(n) = 2^k$ divisors. Split the divisors into two sets of equal size: the small divisors $S$ and the large divisors $T$. The statement he was trying to prove was: $$\text{There exists a function}bijection}\ f: S \rightarrow T \hspace{2mm} \text{such that} \hspace{2mm} d \hspace{1mm} | \hspace{1mm} f(d) \hspace{2mm} \text{for every} \hspace{2mm} d \in S.$$ I was an undergraduate and highly motivated to demonstrate my usefulness, but I didn't really have many ideas about how to go about it. The obvious approach is by induction on $k$, but I never really got anywhere despite spending many hours on the problem.
A year later I ran into Dr. Vaaler in the hall and asked if he ever solved it. Of course, he had, by induction on $k$. He went on to explain the "trick" to making the induction work. He proved a more general result. Introduce a parameter $0 \le r \le \frac{1}{2}$ and consider $S_r$ and $T_r$, the smallest $\lfloor r \cdot 2^k \rfloor$ divisors and the largest $\lfloor r \cdot 2^k \rfloor$ divisors respectively, and instead prove the above statement with $S_r$ and $T_r$ in place of $S$ and $T$.
The lemma is then the special case with $r = \frac{1}{2}$.
This example stuck with me. How could it be easier to prove something more general? Though I understand the concept better today, it still surprises me.
