BdMO Online Forum

Posted: **Tue Mar 30, 2021 11:54 am**

Let $S=\{1,2,3,\dots,15\}$, How many sets $X\subseteq S$ are there such that if $x\in X$ and $3x\in S$, then $3x\in X$?

Posted: **Tue Mar 30, 2021 12:24 pm**

The problem statement created confusion among the students, so here's a detailed clarification :

Solution :
We have to focus on these subsets of $S$ :

$A=\{1,3,9\}$
$B=\{2,6\}$
$C=\{4,12\}$
$D=\{5,15\}$
$E=\{7,8,10,11,13,14\}$

Here $A,B,C,D,E$ are disjoint sets whose union is $S$. Also notice that all of them are valid candidates for being the set $X$.
Now we have to choose elements from $A,B,C,D,E$ such that they create the set $X$.

From $A$, we can either choose $1,3,9$ or only $3,9$ or only $9$ or none. (Total $4$ choices)
From $B$, we can either choose $2,6$ or only $6$ or none. (Total $3$ choices)
From $C$, we can either choose $4,12$ or only $12$ or none. (Total $3$ choices)
From $D$, we can either choose $5,15$ or only $15$ or none. (Total $3$ choices)
From $E$, we can choose any element we want and there are total $2^6$ choices for that.

So, total choices, $\boxed{4\times3\times3\times3\times2^6=6912}$

BdMO Online Forum

BdMO Regional 2021 Higher Secondary P6

BdMO Regional 2021 Higher Secondary P6

Re: BdMO Regional 2021 Higher Secondary P6