A set $S$ is called perfect if it has the following two properties: a) $S$ has exactly four elements b) for every element $x$ of $S$, at least one of the numbers $x - 1$ or $x+1$ belongs to $S$. Find the number of all perfect subsets of the set $\{1,2,... ,n\}$
Problem
Source: Fourth Saudi Arabia JBMO TST 2019, P1
Tags: combinatorics
11.04.2020 09:17
Partition the set into $n-1$ subsets of consecutive pairs of integers. See that the first can only pair with the rest of $n-3$ pars of subsets and the second one with only $n-4$ of these going all the way to 1. So, the total no. of perfect subsets is $\frac{(x-2)(x-3)}{2}$.
11.04.2020 09:20
The answer should be $(n-3)(n-2)/2$. And this problem seems to be from the JBMO 2018 Shortlist, C1.
11.04.2020 09:39
S=${/a,a+1,b,b+1}/$ so there are $n-2C2$=$(n-2)(n-3)/2$answers
12.04.2020 00:24
So we can see that if $x-1 \in S$ then we have that $(x-1)+1\in S$ and the same goes for $x+1 \in S$, then we have that $(x+1)-1\in S$ So now we see that our subsets are of the following forms: $1)\{x,x+1,y,y+1\}$ $2)\{x,x-1,y,y+1\}$ $3)\{x,x+1,y,y-1\}$ $4)\{x,x-1,y,y-1\}$ But notice when we set $y \rightarrow k+1$ then the subset $3$ becomes the subset from $1$ Also notice that when we set $y \rightarrow k+1$ and $x \rightarrow j+1$, then the subset $4$ becomes the subset from $1$ Also notice that when we set $x\rightarrow j+1$ the the subset from $2$ becomes the subset $1$ So now we must calculate the number of subsets of the form of $\{x,x+1,y,y+1\}$ So now if we take into account that we have symmetry in the set, we get that the number of perfect subsets is $\frac{(n-2)(n-3)}{2}$