Let $n>1$ be an integer. A set $S \subset \{ 0,1,2, \ldots, 4n-1\}$ is called rare if, for any $k\in\{0,1,\ldots,n-1\}$, the following two conditions take place at the same time (1) the set $S\cap \{4k-2,4k-1,4k, 4k+1, 4k+2 \}$ has at most two elements; (2) the set $S\cap \{4k+1,4k+2,4k+3\}$ has at most one element. Prove that the set $\{0,1,2,\ldots,4n-1\}$ has exactly $8 \cdot 7^{n-1}$ rare subsets.
Problem
Source: Romanian IMO TST 2006, day 4, problem 3
Tags: algebra, polynomial, linear algebra, combinatorics, Set systems
maxal
20.05.2006 06:22
I believe that the formula $7^n$ is incorrect. Let $f(n)$ be the number of rare subsets of $\{0,1,\dots,4n-1\}$ and $g(n)$ be the number of rare subsets such that they do not contain $4n-1$ or $4n-2$. Considering all cases of (not) containing elements $4n-4$, $4n-3$, $4n-2$, $4n-1$ we get \[ \begin{array}{l}f(n) = 6 f(n-1) + 2 g(n-1)\\g(n) = 3 f(n-1) + g(n-1)\end{array} \] Since the characteristic polynomial of the matrix $\left(\begin{matrix} 6 & 2\\ 3 & 1\end{matrix}\right)$ is $x^2-7x$, for $n>1$ we have $f(n) = 7 f(n-1)$ that together with $f(1)=8$ implies $f(n)=8\cdot 7^{n-1}$.
maky
21.05.2006 14:58
yes, you are correct the number is indeed $8\cdot 7^{n-1}$.
Taha1381
08.10.2017 22:40
maxal wrote: I believe that the formula $7^n$ is incorrect. Let $f(n)$ be the number of rare subsets of $\{0,1,\dots,4n-1\}$ and $g(n)$ be the number of rare subsets such that they do not contain $4n-1$ or $4n-2$. Considering all cases of (not) containing elements $4n-4$, $4n-3$, $4n-2$, $4n-1$ we get \[ \begin{array}{l}f(n) = 6 f(n-1) + 2 g(n-1)\\g(n) = 3 f(n-1) + g(n-1)\end{array} \]Since the characteristic polynomial of the matrix $\left(\begin{matrix} 6 & 2\\ 3 & 1\end{matrix}\right)$ is $x^2-7x$, for $n>1$ we have $f(n) = 7 f(n-1)$ that together with $f(1)=8$ implies $f(n)=8\cdot 7^{n-1}$. Can anyone explain more on how did we get to recurrent relations?
Taha1381
09.10.2017 15:12
Taha1381 wrote: maxal wrote: I believe that the formula $7^n$ is incorrect. Let $f(n)$ be the number of rare subsets of $\{0,1,\dots,4n-1\}$ and $g(n)$ be the number of rare subsets such that they do not contain $4n-1$ or $4n-2$. Considering all cases of (not) containing elements $4n-4$, $4n-3$, $4n-2$, $4n-1$ we get \[ \begin{array}{l}f(n) = 6 f(n-1) + 2 g(n-1)\\g(n) = 3 f(n-1) + g(n-1)\end{array} \]Since the characteristic polynomial of the matrix $\left(\begin{matrix} 6 & 2\\ 3 & 1\end{matrix}\right)$ is $x^2-7x$, for $n>1$ we have $f(n) = 7 f(n-1)$ that together with $f(1)=8$ implies $f(n)=8\cdot 7^{n-1}$. Can anyone explain more on how did we get to recurrent relations?