For every positive integer $n$, let $S_{n}=\{1,2,3, \ldots, n\}$; that is, $S_{n}$ is the set of integers from 1 to $n$ inclusive. There are $2^{n}$ subsets of $S_{n}$. If each subset has the same likelihood of being chosen, let $p(n)$ be the probability that a chosen subset does not contain two integers with a sum of $n+1$.

For example, the subsets of $S_{2}$ are $\emptyset$ (the empty set), $\{1\},\{2\}$, and $\{1,2\}$. Of these four subsets, only $\{1,2\}$ contains a pair of integers with a sum of $2+1=3$. The other three subsets do not contain such a pair, so $p(2)=\frac{3}{4}$.

What is the smallest even positive integer $n$ for which $p(n)<\frac{1}{4}$ ?
Fix a positive integer $k$ and let $n=2 k$ (we are interested in even $n$ ).

The two-element subsets of $S_{2 k}$ consisting of two integers that have a sum of $2 k+1$ are $\{1,2 k\}$, $\{2,2 k-1\},\{3,2 k-2\}$, and so on up to $\{k, k+1\}$. There are $k$ subsets in the list.

A subset $X$ of $S_{2 k}$ contains two integers with a sum of $2 k+1$ exactly when it contains both of the integers from at least one of the $k$ subsets above.

We will now count the number of subsets $X$ of $S_{2 k}$ with the property that no two integers in the subset have a sum of $2 k+1$.

We will do this by counting the number of subsets $X$ of $S_{2 k}$ that contain at most one of the
two integers from each of the $k$ two-element subsets listed earlier.

Suppose $\{a, b\}$ is one of these $k$ subsets. The set $X$ could contain neither $a$ nor $b$, it could contain $a$ and not $b$, and it could contain $b$ and not $a$.

This gives 3 possibilities for each of the $k$ subsets.

Every integer in $S_{2 k}$ appears in exactly one of these $k$ subsets, so a choice of one of these three possibilities for each of the $k$ subsets $\{a, b\}$ completely determines $X$.

These choices are independent, which means the number of subsets $X$ with the desired property is exactly $3^{k}$.

Since there are $2^{2 k}$ subsets in total, we have

$$
p(2 k)=\frac{3^{k}}{2^{2 k}}=\left(\frac{3}{4}\right)^{k}
$$

We want to find values of $k$ that satisfy $p(2 k)<\frac{1}{4}$. Using the formula above, this is equivalent to $\left(\frac{3}{4}\right)^{k}<\frac{1}{4}$, which is equivalent to $3^{k}<4^{k-1}$.

The table below has positive integer values of $k$ in the left column, the value of $3^{k}$ in the middle column, and $4^{k-1}$ in the right column.

| $k$ | $3^{k}$ | $4^{k-1}$ |
| :---: | :---: | :---: |
| 1 | 3 | 1 |
| 2 | 9 | 4 |
| 3 | 27 | 16 |
| 4 | 81 | 64 |
| 5 | 243 | 256 |

We see that $k=5$ is the smallest even positive integer for which $3^{k}<4^{k-1}$, so the answer is $n=2 \times 5=10$.

## Team Problems