Clarification on pigeonhole principle for case of choosing $k$ elements from a set such that $2$ elements from the subset sum to a particular number

The pigeonhole principle is that if $kn+1$ (or more) "pigeons" are divided amongst $n$ "holes" then at least one of the holes contains at least $k+1$ pigeons.

Here, the holes are the pairs (so $n=10$), and you want to conclude that at least one pair contains at least $2$ pigeons, so $k+1=2$.

The answer is the number of cards selected, which corresponds to the number of pigeons. So this is $nk+1=11$.

An example which shows this is best possible is that if you only selected $10$ numbers, they could be the smallest $10$, in which case the maximum sum of any pair would be $19$.

Tags:

Combinatorics

Pigeonhole Principle

Solution Verification

Related

A canonical construction proving $\left|HK\right| = \left|H\right|\left|K\right| / \left|H \cap K\right|$? Conceptual reason for why the volume of an ocahedron is four times the volume of a tetrahedron In a commutative ring, GCD exists implies LCM exists? Necessary and sufficient condition for convergence of series Solve $x^5 - 1 = y^2$ for integer values of $(x,y)$ . Can we derive results from infinite sequences of integration by parts? Residue Theorem Integral of $\frac{1}{\sinh(x)-1}$ How to understand an example in Krattenthaler's “Advanced Determinant Calculus”? Prove that, if $y''+w(x)y=0,$ then $y$ has infinitely many zeroes Proving $\frac{a}{b^3}+\frac{b}{c^3}+\frac{c}{a^3}\geqslant \frac{a+b}{b^3+c^3}+\frac{b+c}{c^3+a^3}+\frac{c+a}{a^3+b^3}$ Prove $\sum_{m=i}^{n}2^{n-m}\binom{m}{i}=\binom{n+1}{i+1}+\ldots+\binom{n+1}{n+1}=\sum_{m=i}^{n}\binom{n+1}{m+1}$ without induction Is Steiner ellipse defining a unique triangle?

Recent Posts