# Pigeonhole principle Q: What is the smallest integer k with the following property: whenever x_1, … ,x_k are integers between 1 and 15, either (i) …

Question:

What is the smallest integer $$k$$ with the following property: whenever $$x_1$$, ... ,$$x_k$$ are integers between 1 and 15, either

(i) there are $$i$$ and $$j$$ with $$i\neq j$$ such that $$x_i = x_j$$, or

(ii) there are $$i$$ and $$j$$ with $$i \neq j$$ such that $$x_i + x_j = 16$$?

Your answer should justify that your chosen k has this property, and also that no smaller k has this property.

Where I am at so far:

The pigeonhole principle states that if $$n + 1$$ pigeons are placed in $$n$$ pigeonholes, then there exists a pigeonhole which contains at least two pigeons.

Thus take our pigeons to be our choices and the integers between $$1$$ and $$15$$ to be pigeonholes. If $$16$$ pigeons are placed into $$15$$ pigeonholes then there is some pigeonhole which contains at least two pigeons. This means there is some integer which has been chosen at least two times. This means there is some $$i$$ and $$j$$ where $$i \neq j$$ and $$x_i = x_j$$.

So I know $$k = 16$$ is the smallest integer which satisfies the first property. This means the smallest integers which satifies property two has to be at least $$16$$.

I know that $$1$$ and $$15$$, $$2$$ and $$14$$, $$3$$ and $$13$$, $$2$$ and $$14$$, $$1$$ and $$15$$, $$6$$ and $$10$$, $$7$$ and $$9$$ and $$8$$ and $$8$$ make $$16$$. But I don't know where to go from here.

So let those be the holes. In other words, take the $$8$$ holes $$\{1,15\}, \{2, 14\}, \{3, 13\}, \{4, 12\}, \{5, 11\}, \{6, 10\}, \{7, 9\}, \{8\}$$ As long as there is only one pigeon in each hole, then all pigeons are different (requirement (i)), and none of them add to $$16$$ (requirement (ii)). However, the moment you have two pigeons in the same hole, either those two are equal, or they add to $$16$$. Problem solved.
• @CubbyKushi Placing pigeon 1 in the hole $\{1, 15\}$ means that $x_1$ is either $1$ or $15$. For the sake of this argument, it doesn't matter which one. The only thing that matters is that if you at a later point place another pigeon in the same hole (i.e. the corresponding $x_i$ is also either 1 or 15), then you break one of the two given requirements. So in order to not break the requirements, you can at most have one pigeon in each hole. – Arthur Jul 4 '19 at 11:27
• So the minimum integer which satisfies both properties is 9? Because if 9 pigeons are placed into 8 pigeonholes this means there is some pigeonholes with at least 2 pigeons in it which means there is an i and a j where**i** ≠ j where $x_i$ = $x_j$ or $x_i$ + $x_j$ = 16. – CubbyKushi Jul 4 '19 at 12:04
• @CubbyKushi Exactly. Technically, you also have to show that the answer is not $8$, which is rather simple as $\{1, 2, 3, 4, 5, 6, 7, 8\}$ is a collection of $8$ numbers which satisfies neither requirement (i) nor (ii). – Arthur Jul 4 '19 at 12:17