BDMO 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.
Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm
BDMO higher secondary P6

Unread post by Asif Hossain » Sat Mar 27, 2021 3:44 pm

Let $S= {1,2,...,15}$. How many sets $x \subseteq S$ are there such that if $x \in X$ and $3x \in S$ then $3x \in X$
Hmm..Hammer...Treat everything as nail

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: BDMO higher secondary P6

Unread post by Asif Hossain » Sat Mar 27, 2021 3:48 pm

We first establish a bijection.
Notice there are $5$ multiples of $3$ in $S$ which we write in pairs like $(1,3),(2,6),(3,9),(4,12),(5,15)$
now notice the desired sets are just subsets of this multiset except $\phi$ so the desired number is $2^5 -1=31$
Is it right?
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BDMO higher secondary P6

Unread post by Mehrab4226 » Sat Mar 27, 2021 7:42 pm

Asif Hossain wrote:
Sat Mar 27, 2021 3:48 pm
We first establish a bijection.
Notice there are $5$ multiples of $3$ in $S$ which we write in pairs like $(1,3),(2,6),(3,9),(4,12),(5,15)$
now notice the desired sets are just subsets of this multiset except $\phi$ so the desired number is $2^5 -1=31$
Is it right?
Let me take one of your subsets,
$X=\{(1,3),(2,6),(4,12),(5,15)\}$
$3\in X$
But $3\times 3 = 9 \notin X$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BDMO higher secondary P6

Unread post by Mehrab4226 » Sat Mar 27, 2021 8:49 pm

My solution is like this,
Let us find all the sets that cannot be X. And let the sets of that class be called Y.
There are 5 cases,

Case:1
If $1 \in Y$ then
$Y=\{1\} \cup\{ \text{Any subset of} \{2,4,5,6,\cdots , 15\}\}$

Case:2
If $2 \in Y$ then
$Y= \{2\} \cup \{ \text{Any subset of}\{3,4,5,7,\cdots 15\}\}$

Case:3
If$3 \in Y$then,
$Y=\{3\} \cup \{\text{Any subset of} \{4,5,6,7,8,10,\cdots 15\}\}$

Case:4
If $4 \in Y$ then,
$Y=\{4\} \cup \{\text{any subset of} \{ 5,6,7,8,9,10,11,13,14,15\}\}$

Case:5
If $5 \in Y$then,
$Y=\{5\}\cup \{\text{Any subset of}\{6,7,8,9,10,11,12,13,14,15\}\}$

The other numbers are not of our concern. As $3x \notin S$ for the other numbers. And yes I did not add the empty set as a Y because the empty set satisfies all the criteria of X.

So the total number of Y is $=2^{13}+2^{12}+2^{11}+2^{10}+2^{9}$
So the number of X possible $=2^{15}-(2^{13}+2^{12}+2^{11}+2^{10}+2^{9}
)$
$=16896$
Last edited by Mehrab4226 on Sat Mar 27, 2021 9:37 pm, edited 1 time in total.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: BDMO higher secondary P6

Unread post by Asif Hossain » Sat Mar 27, 2021 9:21 pm

Mehrab4226 wrote:
Sat Mar 27, 2021 7:42 pm
Asif Hossain wrote:
Sat Mar 27, 2021 3:48 pm
We first establish a bijection.
Notice there are $5$ multiples of $3$ in $S$ which we write in pairs like $(1,3),(2,6),(3,9),(4,12),(5,15)$
now notice the desired sets are just subsets of this multiset except $\phi$ so the desired number is $2^5 -1=31$
Is it right?
Let me take one of your subsets,
$X=\{(1,3),(2,6),(4,12),(5,15)\}$
$3\in X$
But $3\times 3 = 9 \notin X$
Does the question say that for "every" $x \in X$ the property holds? :( (sorry i didn't notice that i missed some countings..)
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BDMO higher secondary P6

Unread post by Mehrab4226 » Sat Mar 27, 2021 9:32 pm

Asif Hossain wrote:
Sat Mar 27, 2021 9:21 pm
Mehrab4226 wrote:
Sat Mar 27, 2021 7:42 pm
Asif Hossain wrote:
Sat Mar 27, 2021 3:48 pm
We first establish a bijection.
Notice there are $5$ multiples of $3$ in $S$ which we write in pairs like $(1,3),(2,6),(3,9),(4,12),(5,15)$
now notice the desired sets are just subsets of this multiset except $\phi$ so the desired number is $2^5 -1=31$
Is it right?
Let me take one of your subsets,
$X=\{(1,3),(2,6),(4,12),(5,15)\}$
$3\in X$
But $3\times 3 = 9 \notin X$
Does the question say that for "every" $x \in X$ the property holds? :(
Yes. The question said if $x$ is in $X$, then $3x$ is also in $X$. That is enough to let us know that $x$ can be any number in $X$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: BDMO higher secondary P6

Unread post by Asif Hossain » Sat Mar 27, 2021 9:36 pm

Mehrab4226 wrote:
Sat Mar 27, 2021 9:32 pm
Asif Hossain wrote:
Sat Mar 27, 2021 9:21 pm
Mehrab4226 wrote:
Sat Mar 27, 2021 7:42 pm

Let me take one of your subsets,
$X=\{(1,3),(2,6),(4,12),(5,15)\}$
$3\in X$
But $3\times 3 = 9 \notin X$
Does the question say that for "every" $x \in X$ the property holds? :(
Yes. The question said if $x$ is in $X$, then $3x$ is also in $X$. That is enough to let us know that $x$ can be any number in $X$
Didn't it said if "$x \in X$ and $3x \in S$" then $3x \in X$ :oops: :oops:
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BDMO higher secondary P6

Unread post by Mehrab4226 » Sat Mar 27, 2021 9:45 pm

Asif Hossain wrote:
Sat Mar 27, 2021 9:36 pm
Mehrab4226 wrote:
Sat Mar 27, 2021 9:32 pm
Asif Hossain wrote:
Sat Mar 27, 2021 9:21 pm


Does the question say that for "every" $x \in X$ the property holds? :(
Yes. The question said if $x$ is in $X$, then $3x$ is also in $X$. That is enough to let us know that $x$ can be any number in $X$
Didn't it said if "$x \in X$ and $3x \in S$" then $3x \in X$ :oops: :oops:
Yes, it said if $x$ is in $X$ and $3x$ in $S$. Then $3x$ must be in $X$. It implies that we cannot find any $x$ inside $X$ whose $3x$ if in $S$ not in $X$.
Last edited by Mehrab4226 on Sat Mar 27, 2021 9:49 pm, edited 1 time in total.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: BDMO higher secondary P6

Unread post by Asif Hossain » Sat Mar 27, 2021 9:47 pm

Mehrab4226 wrote:
Sat Mar 27, 2021 9:45 pm
Asif Hossain wrote:
Sat Mar 27, 2021 9:36 pm
Mehrab4226 wrote:
Sat Mar 27, 2021 9:32 pm

Yes. The question said if $x$ is in $X$, then $3x$ is also in $X$. That is enough to let us know that $x$ can be any number in $X$
Didn't it said if "$x \in X$ and $3x \in S$" then $3x \in X$ :oops: :oops:
You maybe right. But in let's say set builders method we write a set,
$K=\{x:x\in \mathbb{N}\}$
Then $K=\{1,2,3,4,\cdots\}
You know what, I don't know which one is right.
well even if my assumption is right is the ans $31$ right..
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: BDMO higher secondary P6

Unread post by Mehrab4226 » Sat Mar 27, 2021 9:55 pm

Asif Hossain wrote:
Sat Mar 27, 2021 9:47 pm
Mehrab4226 wrote:
Sat Mar 27, 2021 9:45 pm
Asif Hossain wrote:
Sat Mar 27, 2021 9:36 pm


Didn't it said if "$x \in X$ and $3x \in S$" then $3x \in X$ :oops: :oops:
You maybe right. But in let's say set builders method we write a set,
$K=\{x:x\in \mathbb{N}\}$
Then $K=\{1,2,3,4,\cdots\}
You know what, I don't know which one is right.
well even if my assumption is right is the ans $31$ right..
Depends on your assumption,
If you assume that if any single element of a subset of $S$ follows that criteria,then that subset is a valid $X$, then your answer is probably not correct.
If you assumed that $X$ can only contain the numbers which have $3x \in S$. Then you are maybe correct.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply