Pair of numbers using pigeon hole principle

Question

n ∈ N, A ⊆ {1, . . . , 2n}, |A| = n + 1. Show that:

a) In A there is a pair of numbers whose sum is equal to 2n + 1.

b) In A there is a pair of relatively prime numbers.

c) In A there is a pair of numbers, such that one is a multiple of the other.

For the first part, I started by making pairs of numbers whose sum equals 2n + 1, which is literally the first number and the last one in the set A, {2n + 1, 2n - 1 + 2, 2n - 2 + 3 ...} I'm not sure how to prove that there exists this pair, when it clearly does.

I'm not sure how to go about part b) and c) any hint would be much appreciated.

Answer 1

Let's put the given data as $$ \left\{ {\begin{array}{*{20}c} {U = \left\{ {1,\; \ldots ,\;2n} \right\}} & {\left| U \right| = 2n} \\ {A \subseteq U} & {\left| A \right| = n + 1} \\ {B = U\backslash A} & {\left| B \right| = n - 1} \\ \end{array} } \right.\quad $$ Now, consider the ordered couples, e.g. $(a,b)\;|\,a \leqslant b$, of elements of $U$ that satisfy a given property.
If (at least) one of the elements of the couple pertains to $B$, then the whole couple cannot pertain to $A$.
So if $B$ can accomodate at least one distinct element per each couple, then all the couples are "destroyed", i.e. none will pertain to $A$.
We do not loose of generality if we perform this check on the first (distinct) element of each couple, since we can always switch the elements.
Since the cardinality of $B$ is $n-1$, that means that if within the ordered couples with the given property, the count of those that have a distinct first element is less than $n$, then there could be the case that $B$ contains all such elements, leaving no couple for $A$.
Viceversa, if they account to $n$ or more, than at least one couple will remain out and will end in $A$.

Now, also taking in consideration the other answers, for the proposed properties we have

• a) the ordered couples summing to $2n+1$ are $(1,\,2n)\; \cdots \;(n,n+1)$, for a total of $n$ with all distinct first el. $\quad \Rightarrow \quad \text{demonstrated}$
• b) the ordered couples with coprime elements are at least those given by $(n \, ,n+1)$, for a total of $n \leqslant 2n-1$, with all distinct first el. $\quad \Rightarrow \quad \text{demonstrated}$
• c) the ordered couples with one element multiple of the other are at least those given by $(1 \, ,n+1)$, for a total of $n \leqslant 2n-1$, with all distinct second el., and switching the order $\quad \Rightarrow \quad \text{demonstrated}$

Answer 2

$$ \begin{array}{rcl} 2n & \longleftrightarrow & 1 \\ 2n-1 & \longleftrightarrow & 2 \\ 2n-2 & \longleftrightarrow & 3 \\ 2n-3 & \longleftrightarrow & 4 \\ & \vdots \end{array} $$

If your set $A$ contains at most one number from each of these $n$ pairs, then you have $|A|\le n.$

Answer 3

For the first part, you started well. You need to make pairs that add up to $2n+1$. Except $(1,2n)$, we can have $(2,2n-1)$ and more. In general $(1+d,2n-d)$, where $d=1,2,...,n$. So, there are $n$ pairs. Having $n$ pairs, taking $n+1$ numbers would force to take two numbers from a same pair.

For the second part, notice that any pair $(a,a+1)$ are mutually prime. So, make pairs of consecutive numbers.

For the last part, You need to make sets as the following. In $\{1,2,...,2n\}$, there are exactly $n$ odd numbers. Consider $n$ empty sets and put one of the $n$ odd numbers in each of them. Then, if $\{x\}$ is one the sets, complete the set as below.

$\{x\times 2^{k}|k\in\mathbb{N}\cup\{0\} , x\times 2^{k}\leq2n\}$

It can be shown that, by this way of constructing the sets, no repetition of numbers would happen. Also, it would cover all the numbers.