基于鸽巢原理的离散数学证明问题求助

Hey there! Great call zeroing in on the pigeonhole principle—it's definitely the key here. Let's walk through how to frame the "boxes" and work through the problem step by step.

First, let's restate the problem clearly for reference:

Prove that among $15$ distinct natural numbers not exceeding 100, there are four numbers $a,\ b,\ c,\ d$ such that: $a + b = c + d$ or the numbers $a, b, c$ form an arithmetic sequence.

Here's the breakdown of the approach:

• Step 1: Sort the numbers
  Let's arrange the 15 distinct numbers in ascending order: $x_1 < x_2 < ... < x_{15}$. Sorting helps us systematically analyze sums and differences between pairs.

• Case 1: Finding four numbers with equal pairwise sums
  Calculate how many unique pairwise sums we can have: that's the combination formula $\binom{15}{2} = 105$ sums. Now, what's the range of these sums? The smallest possible sum is $x_1 + x_2 ≥ 1 + 2 = 3$, and the largest is $x_{14} + x_{15} ≤ 99 + 100 = 199$. That gives us $199 - 3 + 1 = 197$ possible distinct sum values.
  If there is a duplicate sum (i.e., two different pairs $(a,b)$ and $(c,d)$ where $a+b=c+d$), we've already satisfied the first condition of the problem.

• Case 2: If all pairwise sums are unique, we must get an arithmetic sequence
  Now suppose every pairwise sum is unique. Let's shift our focus to pairwise differences. For any $j > i$, consider $x_j - x_i$. How many such differences are there? Again, $\binom{15}{2} = 105$.
  What's the range of these differences? The smallest difference is $x_2 - x_1 ≥ 1$, and the largest is $x_{15} - x_1 ≤ 100 - 1 = 99$. That's only 99 possible distinct difference values.
  Here's the pigeonhole principle kicker: we have 105 differences, but only 99 possible values. So at least two differences must be equal!

  Now, let's analyze what equal differences mean here:

  • If the equal differences come from pairs with no shared elements (e.g., $x_j - x_i = x_l - x_k$ where $i < j < k < l$), rearranging gives $x_j + x_k = x_i + x_l$—which would mean we have duplicate pairwise sums, contradicting our "all sums are unique" assumption.
  • The only other possibility is that the equal differences share a middle element: $x_k - x_i = x_j - x_k$ (where $i < k < j$). Rearranging this gives $2x_k = x_i + x_j$, which means $x_i, x_k, x_j$ form an arithmetic sequence—exactly the second condition we needed to prove!

So putting it all together: either we have duplicate pairwise sums (giving us four numbers with $a+b=c+d$), or the pigeonhole principle forces us to have duplicate differences that must form an arithmetic sequence. Either way, the statement holds.

备注：内容来源于stack exchange，提问作者artobjective