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.