Million Monster Movies

Assume that there are $n$ distinct monsters.

Now consider a set of $n$ distinct numbers. In each movie there must be atleast 2 different monsters, so numbers of way in which we can select two numbers from this set is $n\choose2$ Therefore, there will be $n\choose2$ distinct subsets (this distinction meets the criteria that the two movies cannot have same set of monsters)

But the movie can also have more than 2 monsters, so consider 3 set of monsters, then there will be $n\choose3$ different subsets. Similarly consider for $4,5,6 \ldots n$ set of monsters.

Now the total distinct subsets will be $n\choose2$ $+$ $n\choose3$ $+$ $n\choose4$ $+\ldots$ $n\choose n$ and hence these many set of monsters.

But we need to make 1 million movies so

$n\choose2$ $+$ $n\choose3$ $+$ $n\choose4$ $+\ldots$ $n\choose n$ $\geq 1,000,000$

$2^n-$ $n\choose0$ $-$ $n\choose1$ $\geq 1,000,000$

Now here you need to calculate that for which value of $n$ it is true.

We get it is true for all $n \geq 20$ . Hence $n_{min} = 20$

If the number of monsters is equal to $n$ , then the number of subsets (the ways to choose the monsters) is equal to $2^n$ . This is because every monster can be included or not included in the movie. However, since we want every movie to have at least two monsters, we must subtract the possibilities where there is only 1 or no monsters.

For no monsters, there is only one possibility. None are included For one monster, there are $n$ possibilities; the one included can be any of the $n$ .

So, we have the inequality

$2^n-1-x\ge 1000000$

Notice that $2^{20}=1048576$ and $1048576-20-1=1048555$ . If we try 19, we will obtain an amount too small (less than one million), so the correct answer is equal to $\boxed{20}$ .

Let us consider, the minimum number of monsters required to make million movies=n. By the problem, each movie should have at least 2 different monsters. So, the number of movies can be formed $=nC2+nC3+.......+nCn$ $= nC1+nC2+.......+nCn-nC1$ = $2^{n}-n-1$ . Here, $2^{n}-n-1>1000000.$ By solving this, the minimum value of $n = 20.$ So, minimum 20 monsters will be needed to make a million movie.

We have a set of n monsters. We can choose 2, 3, 4... all the way to n monsters. This is Pascal's triangle sum minus the 0th and 1st terms, or 2^n - 1 - n >= 1000000 possibilities. Note 2^10=1024, so 2^20 is greater than a million. Verify that 20 is indeed the first number that works. And we're done.

We want to evaluate the value of: nC2+nC3+...+nCn We see from the binomial expansion that (1+1)^n = 1+n + (nC2+nC3+...+nCn) We want that value to be larger than 1 million, we see that 2^20 >1000,000. Hence, n=20

Let the minimum number of monsters be N. Numbers of ways to choose k out of N objects is $\frac{N!}{k!(N-k)!}$ , and $2^{N}$ = $\sum_{k=0}^N$ $\frac{N!}{k!(N-k)!}$ .

We cannot choose the sets which only have 1 or 0(means that it is an empty set) monster,each set have N and 1 types respectively.So we have $2^{N}$ -(n+1)> $10^{6}$ . Trying a few times, we get $2^{20}$ -21=1048555, thus N=20.

If M=number of monsters they need, then the sum $M \choose 2$ + $M \choose 3$ + $...$ + $M \choose M$ should be equal to or greater than $1,000,000$ since it is just the sum of the combinations of monsters possible. This is similar to $M \choose 0$ + $M \choose 1$ + $...$ $M \choose M$ which is just $2^M$ . We see that $2^20$ is just above $1,000,000$ , and after subtracting $20 \choose 0$ and $20 \choose 1$ , the answer is still above $1,000,000$ So, our answer is $20$ .

if n is the number of monster and 2 is the number used in each movie from n monsters then 2^n=1,000,000 . solving this equation results in the solution n=20

Basically, if there are n monsters to choose from, we will select nC2+nC3+nC4+.....+nCn

Now, we know that, nC0+nC1+nC2+..+nCn= 2^n

Checking for 1,000,000=1000x1000=(2^10)x(2^10) {approx} =2^20 therfore, n is 20

Suppose we have N as the minimal amount of monsters needed.

So, we have $\binom{N}{2}$ ways of choosing 2 monsters for a movie, $\binom{N}{3}$ ways of choosing 3 monsters for a movie.... $\binom{N}{N}$ ways of choosing N monsters for a movie.

So, we must find minimal N for which $\sum_{i=2}^n \binom{N}{i} \geq 1,000,000 (I)$ .

Since $\sum_{i=0}^n = 2^n$ , we must find minimal N for which $2^N - \binom{N}{0} - \binom{N}{1} \geq 1,000,000 \rightarrow 2^N - N - 1 \geq 1,000,000$

As this is a transcendental inequation, and the exponential grows way faster than a one-degree polynomial, let's find $m \leq N$ for which $2^m \geq 1,000,000 \rightarrow m = 20$ (m must be an integer)

By trying $N = m = 20$ , we get, from $(I)$ : $2^{20} - 20 - 1 = 1,048,555 \geq 1,000,000$ and there is no other small N, since $m \leq N$