1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – SFR
    Jul 4, 2019 at 11:10
  • $\begingroup$ @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. $\endgroup$
    – Arthur
    Jul 4, 2019 at 11:27
  • $\begingroup$ 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. $\endgroup$
    – SFR
    Jul 4, 2019 at 12:04
  • $\begingroup$ @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). $\endgroup$
    – Arthur
    Jul 4, 2019 at 12:17
  • $\begingroup$ This thank you is late but still thanks a lot for your help Arthur! :) $\endgroup$
    – SFR
    Jul 16, 2019 at 19:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .