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.