# K-subsets, counting, and the pigeon hole principle

Fellow mathematicians, please take a look at these practice test questions and try to help if you can:

Question $1$:

Let $n ≥ 8$ be an even integer and let $S = \{1, 2, 3, . . . , n\}$. Consider $7$-element subsets of $S$ that consist of $4$ even numbers and $3$ odd numbers. How many such subsets are there?

(a) ${{n/2}\choose4} \cdot {{n/2}\choose3}$
(b) ${{n}\choose4} \cdot {{n}\choose3}$
(c) ${{n/2}\choose4} + {{n/2}\choose3}$
(d) ${{n}\choose4} + {{n}\choose3}$

Answer is (a). Why do we divide $n$ by $2$ here? If $n=8$, then $n/2 = 4$ which leaves us with only $2$ even and odd numbers $(1,2,3,4)$, so how can we choose $4$ even and $3$ odd numbers when there is only two of each? My initial guess was (b).

Question $2$:

What does this count? $\sum_{k=2}^{n} {n\choose{k}} \cdot 2^{n-k}$

(a) The number of strings of length $n$, where each character is $a$ or $b$, that contain at least one $a$.
(b) The number of strings of length $n$, where each character is $a$ or $b$, that contain at least $2$ many $a$’s.
(c) The number of strings of length $n$, where each character is $a$, $b$, or $c$, that contain at least one $a$.
(d) The number of strings of length $n$, where each character is $a$, $b$, or $c$, that contain at least $2$ many $a$’s.

Where does the the $c$ in "$a$, $b$, or $c$" come from?

Question $3$:

Consider a square with sides of length $17$. This square contains $n$ points. What is the minimum value of $n$ such that we can guarantee that at least two of these points have distance at most $17/\sqrt 2$? Edit: This was originally $17\sqrt 2$, I had made a typo.

(a) 4
(b) 5
(c) 6
(d) 7

The diagonal distance of this square is $\sqrt{{17^2} + {17^2}} = 17\sqrt 2$. This means that even with $2$ points, this rule would still hold because even if the two points were in either corner of the square, and since the longest distance is the diagonal distance, they would always be within a distance of $17\sqrt 2$. In this case, the lowest number to choose from is $4$, so that is the minimum -- however the answer is $5$. Where am I going wrong?

• I think @Robert Z has a point below, can you recheck the Question 3 because if distance is at most $17\sqrt{2}$ then $2$ points are enough. So it should be something else. And if the answer is $5$, it is probably $\frac{17}{\sqrt{2}}$. – ArsenBerk Feb 25 '18 at 8:28
• Indeed I have made a typo. It is the latter! – udpcon Feb 25 '18 at 16:49

Question 1. If $n$ is even then in $S = \{1, 2, 3, . . . , n\}$ there are $n/2$ even numbers and $n/2$ odd numbers. So the subsets of 4 even numbers are $\binom{n/2}{4}$ and the subsets of 3 odd numbers are $\binom{n/2}{3}$.

Question 2. Notice that ${n\choose{k}}$ is the number of ways to place $k$ character "a" and $2^{n-k}$ is the number of ways to fill the remaining $n-k$ characters with "b" or "c" ($2$ choices). Hence the given sum is just the number of strings of length $n$, where each character is "a", "b" or "c", which contain at least 2 many "a"s.

Question 3. Is distance at most $17\sqrt{2}$ or distance at most $17/\sqrt{2}$? (yes, you are correct, the distance of any two points in the square is at most the diagonal's length $17\sqrt{2}$!). For the second option, divide the square into $4$ equal squares. Then the lengths of the diagonals of the smaller squares is just $17/\sqrt{2}$. Hence by the pigeon hole principle, by taking $4+1$ points, at least two of them will lie into one of the smaller squares.

Question 1: If $n$ is even, then $\frac{n}{2}$ gives you the number of even numbers in $S$, as well as number of odd numbers. Then you simply choose $4$ of the even numbers with $\binom{\frac{n}{2}}{4}$ and $3$ of the odd numbers with $\binom{\frac{n}{2}}{3}$.

Question 2: Notice that here, we need $3$ characters because of $2^{n-k}$ (There must be two options for the rest of the $n-k$ places after putting $a$ to $k$ places).

Question 3: HINT: Here, I'm considering the distance is at most $\frac{17}{\sqrt{2}}$. So, having at least how many points guarantees that two of them are inside the same square?