Problem 1478

To prove that the number of 5-element non-isolated subsets of $\{1, 2, \ldots, n\}$ is $(n-4)^2$, we will analyze the structure of such subsets and count the possible configurations.

1. Define the structure of the subset:
Let a 5-element non-isolated subset of $\{1, 2, \ldots, n\}$ be $(a, b, c, d, e)$ with $a < b < c < d < e$. By the definition of a non-isolated set, for every element $x$ in the subset, at least one of $x-1$ or $x+1$ must also be in the subset. This implies:
- $b = a + 1$
- $e = d + 1$

Therefore, the subset must be of the form $(a, a+1, c, d, d+1)$.

2. Case Analysis:
We need to consider different cases for the positions of $c$ and $d$ relative to $a$.

**Case 1: $c = a + 2$ and $c \neq d - 1$**
- Here, $c = a + 2$ and $d > c + 1 = a + 3$.
- Let $x$ be the number of elements before $a$, $y$ be the number of elements between $a+2$ and $d$, and $z$ be the number of elements after $d+1$.
- We have $x + y + z = n - 5$ and $y > 0$.
- The number of solutions for this case is $\binom{n-4}{2}$.

**Case 2: $c = d - 1$ and $c \neq a + 2$**
- Here, $d = c + 1$ and $c > a + 2$.
- This case is symmetric to Case 1, so it also has $\binom{n-4}{2}$ solutions.

**Case 3: $c = a + 2 = d - 1$**
- Here, $c = a + 2$ and $d = c + 1 = a + 3$.
- We simply need to select 5 consecutive numbers from $\{1, 2, \ldots, n\}$.
- The number of solutions for this case is $n - 4$.

3. Summing the cases:
- The total number of required subsets is the sum of the solutions from all three cases:
$$2\binom{n-4}{2} + (n-4)$$
- Simplifying this expression:
$$2\binom{n-4}{2} + (n-4) = 2 \cdot \frac{(n-4)(n-5)}{2} + (n-4) = (n-4)(n-5) + (n-4) = (n-4)^2$$

Thus, we have proved that the number of 5-element non-isolated subsets of $\{1, 2, \ldots, n\}$ is $(n-4)^2$.

$\blacksquare$