BdMO Regional 2021 Higher Secondary P6

Forum rules
Please don't post problems (by starting a topic) in the "X: Solved" forums. Those forums are only for showcasing the problems for the convenience of the users. You can always post the problems in the main Divisional Math Olympiad forum. Later we shall move that topic with proper formatting, and post in the resource section.
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
BdMO Regional 2021 Higher Secondary P6

Unread post by Anindya Biswas » 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$?
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO Regional 2021 Higher Secondary P6

Unread post by Anindya Biswas » Tue Mar 30, 2021 12:24 pm

The problem statement created confusion among the students, so here's a detailed clarification :
This problem asks for those sets $X$ for which "if $x\in X$ and $3x\in S$, then $3x\in X$". That means if $3x\not\in S$, then $X$ does not have to contain $3x$, since $X$ is a subset of $S$. But when $3x\in S$, then it must be included in $X$. For example, if $7\in X$, we will check whether $3\times 7$ is in $S$ or not. Since $3\times 7\not\in S$, that means $3\times7\not\in X$. But if $2\in X$, then $6$ must also be included in $X$ since $6\in S$. Even the empty set $\emptyset$ is also a valid candidate for $X$.
Solution :
We have to focus on these subsets of $S$ :
  1. $A=\{1,3,9\}$
  2. $B=\{2,6\}$
  3. $C=\{4,12\}$
  4. $D=\{5,15\}$
  5. $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}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply