Competition problem — Combinatorics

Library / /12 of 155

Combinatorics Difficulty 4.8 AIME Prove it Saudi Arabia

A set $S$ is called neighboring if it has the following two properties:
i) $S$ has exactly 4 elements,
ii) for every element $x \in S$ at least one of the $x-1$ or $x+1$ belongs to $S$ .
Find the number of all neighboring subsets of the set $\{1,2, \ldots, n\}$ .

Solution

Let $x$ be the smallest index and $y$ be the largest index of the neighboring set. Then our set consists of elements
$a_{x}, a_{x+1}, a_{y-1}, a_{y}$
So the number of neighboring sets is equal to the number of pairs $(x, y)$ where $y-x \geq 3$ . The number of such sets is equal to
$1+2+\cdots+(n-3)=\frac{(n-3)(n-2)}{2}$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.