# 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.

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.

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.

• I'm having a hard time understanding your solution. So what I've got so far is that we now consider 8 pigeonholes labelled {1,15},{2,14},{3,13},{4,12},{5,11},{6,10},{7,9},{8} and we still consider "choices" as being pigeons. That's all I understand really. Firstly, If one pigeon is placed into a pigeonhole, say {1, 15}, what does this mean? – CubbyKushi Jul 4 '19 at 11:10
• @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
• This thank you is late but still thanks a lot for your help Arthur! :) – CubbyKushi Jul 16 '19 at 19:26