Dhaka H. Secondary 2014/7

For discussing Olympiad Level Combinatorics problems
Ragib Farhat Hasan
Posts:62
Joined:Sun Mar 30, 2014 10:40 pm
Dhaka H. Secondary 2014/7

Unread post by Ragib Farhat Hasan » Fri Aug 31, 2018 11:21 pm

If A = {1, 2, 3… 11, 12} then how many subsets of A are possible where the minimum number of element is 2 and no two numbers are consecutive.

Ahmed Ashhab Mahir
Posts:4
Joined:Mon Aug 16, 2021 9:10 pm

Re: Dhaka H. Secondary 2014/7

Unread post by Ahmed Ashhab Mahir » Wed Nov 02, 2022 5:04 pm

Subsets containing 2 elements:
Let the elements be ${a_1,a_2}$. It is obvious that, $1 \leq a_1 < a_2 -1 \leq 11$ . Set $a_1=b_1 , a_2-1=b_2$ . So we get, ,$1 \leq b_1 < b_2 \leq 11$ . We can choose $b_1,b_2$ in $11 \choose 2$
Subsets containing 3 elements:
Let the elements be ${a_1,a_2,a_3}$. It is obvious that, $1 \leq a_1 < a_2 -1 < a_3 -2 \leq 10$ . Set $a_1=b_1 , a_2-1=b_2,a_3 -2=b_3 $ . So we get, ,$1 \leq b_1 < b_2 <b_3 \leq 10$ . We can choose $b_1,b_2,b_3$ in $10\choose 3$
Simillarly for cases subsets containing 4,5 and 6 elements we get $ {9\choose 4} , {8\choose 5 } , {7\choose 6} $ subsets respectively. Thus the require answer ${ 11 \choose 2}+ {10\choose 3}+ {9\choose 4 }+ {8\choose 5} +{ 7\choose 6} = \fbox{364} $

Post Reply