Partitioning into subsets

Probability Level 2

The number of ways that the set of distinct positive integers { 1 , 2 , . . . , 2018 1,2, . . ., 2018 } can be partitioned into three nonempty sets so that none of these sets contains two consecutive integers is 2 a − 1 2^a - 1 . What is a a ?

Note: The order of the sets does not matter.


The answer is 2016.

Sathvik Acharya by Sathvik Acharya , 17, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

It was actually a lucky guess, but trying with smaller sets led me to the feeling that it might be that a= n-2. Haven't come to prove that or disproof that statement. So if anyone feels like he should or could Feel welcome to try!

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Let there be three sets say A, B, C. Say 1 and 2 go to set A and set B respectively, now observe that the number 3 can placed in any of the two sets (A or C). Applying a similar idea for all numbers from 3 to 2018 we get 2 2016 2^{2016} ways. But we are not done here! Note that there is a case where one of the sets becomes a null set. (Against the question) Hence 2 2016 − 1 2^{2016}-1 . And the generalization now is fairly obvious.

Sathvik Acharya - 3 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...