0
$\begingroup$

We can divide a proof by induction in two parts: Inductive base and Inductive step. One proves for the case when n = 1, and after one suppouse what we want to prove is the case for an arbitrary k, then we prove k+1 is also true.

Now, I want to know the parts of the pigeonhole principle. When I want to prove something using the pigeonhole principle what I must to do?. An example will make it clear, say this problem

enter image description here

In the problem assume that n is a natural number greater or equal to 2 and even.

How can I solve it using the pigeonhole principle, more concret, what are the parts of the proof using the pigeonhole principle?

$\endgroup$
6
  • $\begingroup$ I'm assuming, $n\in\mathbb N$, where $n\geq 2$? $\endgroup$
    – Seong
    Oct 4, 2021 at 1:10
  • $\begingroup$ Yes Owen, I forgot it $\endgroup$ Oct 4, 2021 at 1:13
  • $\begingroup$ Note for $n=2$, set up your pigeonholes and prove the trivial case. Then suppose for some $n\in\mathbb N$ that it holds with your associated pigeonholes. Then show for $n +1$. Also note that for $n=2$, one could easily do brute force, but setting up your pigeonholes first allows you to easily extend to $n\in\mathbb N$. $\endgroup$
    – Seong
    Oct 4, 2021 at 1:14
  • $\begingroup$ Please do not use images, especially for such small piece of text. See here why images should not be used to convey key information. $\endgroup$ Oct 4, 2021 at 1:22
  • $\begingroup$ @Ratamágica, also, I feel like it should also say that $n$ should be even. Consider $n=5 \implies \frac 52 +1 = 2.5 + 1 = 3.5$. Picking 3.5 elements from the set doesn't make sense. $\endgroup$
    – Seong
    Oct 4, 2021 at 1:24

1 Answer 1

1
$\begingroup$

Direct approach that does not use induction.

Assume that the selected (distinct) numbers, in ascending order are

$A = \{a_1, a_2, \cdots, a_{(n/2) + 1}\}.$

For $k \in \{1,2, \cdots, [(n/2) + 1]\},~$ let $b_k = (n+1) - a_k$.

Let $B = \{b_1, b_2, \cdots, b_{(n/2) + 1}\}.$

As defined, $B \subseteq \{1,2,\cdots, n\}.$

Note that the set $\{1,2,\cdots, n\}$ only has $(n)$ elements, while the sets $A$ and $B$ each have [(n/2) + 1] distinct elements from $\{1,2,\cdots,n\}$. Therefore, by the pigeonhole principle, there must be an element $b_r \in B$ that equals some element $a_s \in A$.

Therefore, $a_r + a_s = (n+1).$

Note that since $n$ even, $(n+1)$ is odd.
Therefore, $a_r, a_s$ must be two distinct elements (else their sum would be even).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.