3
$\begingroup$

Call a set of integers sparse if any two elements in the set differ by at least 3. Find the number of sparse subsets of $\{1, 2, 3, \dots, 12\}.$ (Both $\emptyset$ and one-element sets are sparse, to my understanding.) For example, {$1, 5, 11, 12$} is a sparse set, since $1$ and $5$ differ by 3 or more.

I was thinking of a way using recursion. Here's my approach:

Call $a_n$ the number of sparse sets in the set of integers {$1, 2, 3, \dots, n$}. If we look at the set {$1, 2, 3, \dots, n-1$}, there are $a_{n-1}$ sparse sets. If we assign $n-1$ to a sparse set, when we incorporate $n$, then we can either

  • include $n$ in the sparse set
  • include $n$ and remove $n-1$ in the sparse set
  • keep it as it is.

There are $3$ cases, each with the same value, so we have $a_n = 3a_{n-1}$ so far.

However, I don't know how to continue, and I'm not even sure if my current approach is correct.

$\endgroup$
19
  • 1
    $\begingroup$ Wouldn't we also have to remove $n - 2$ in order to include $n$? $\endgroup$ Commented Aug 20, 2020 at 20:45
  • 1
    $\begingroup$ Either $n$ is in the set, in which case you have $a_{n-3}$ since we know that $ n-2, n-1$ can't be in the set, or $n$ is not in the set, in which case you have $a_{n-1}$. $\endgroup$
    – lulu
    Commented Aug 20, 2020 at 20:54
  • 3
    $\begingroup$ @FruDe I read the condition as requiring that no two elements are closer than $3$, so I would not count the set you propose. $\endgroup$
    – lulu
    Commented Aug 20, 2020 at 20:56
  • 1
    $\begingroup$ @lulu Alright, I'll go with that. So then the recursion would be $a_n = a_{n-1}+a_{n-3}$. $\endgroup$ Commented Aug 20, 2020 at 20:58
  • 2
    $\begingroup$ When mathematicians say something like "any two" they mean "for all pairs." Your interpretation seems closer to saying "for some pair." $\endgroup$ Commented Aug 20, 2020 at 22:56

1 Answer 1

1
$\begingroup$

Let $S_n$ be the set of sparse subsets on $\{1..n\}$. Then $S_0 = \{\emptyset\}$, $S_1 = \{\emptyset, \{1\}\}$, $S_2 = \{\emptyset, \{1\}, \{2\}\}$, and in general

$S_{n + 3} = S_{n + 2} \cup \{A \cup \{n + 3\} : A \in S_n\}$

Define $F_n = |S_n|$. Then we see that $F_0 = 1$, $F_1 = 2$, $F_2 = 3$, and $F_{n + 3} = F_{n + 2} + F_n$.

To efficiently calculate $F_n$, we note that, defining

$M = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$

We have

$M \begin{pmatrix} F_{n + 2} \\ F_{n + 1} \\ F_n \end{pmatrix} = \begin{pmatrix} F_{n + 3} \\ F_{n + 2} \\ F_{n + 1} \end{pmatrix}$

And consequently, by induction on $n$, we have

$M^n \begin{pmatrix} F_{2} \\ F_{1} \\ F_0 \end{pmatrix} = \begin{pmatrix} F_{n + 2} \\ F_{n + 1} \\ F_{n} \end{pmatrix}$

Calculating $M^n$ will take $O(\log n)$ multiplications.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .