A Level Options

Probability Level 4

Problem accredited to Aaron Pain (Bexhill College).

In A level further mathematics you study core content and take two options. However, you are instead allowed to take as many options as you like, and be graded on your best two.

The options system works in this way: there are $n\in\N$ different topics to choose from, $A_1, ..., A_n$ , and for each topic $A_i:i\in\{1, 2, ..., n\}$ there are two options: $a_i$ and $b_i$ . The only rules are that $\forall i\in \{1, 2, ..., n\}$ you are not allowed to take $b_i$ unless you also take $a_i$ , and obviously you have to take at least two options in total.

Define an option set as a set of options you could take. Then for example, you could take the option sets: $\{a_1, b_1\}$ , $\{a_2, a_4\}$ , or $\{a_1, a_5, b_5, a_7, a_9, b_9\}$ , but you would not be allowed to take the option set: $\{a_1, b_3\}$ because you cannot take $b_3$ without also taking $a_3$ .

Given $n\in\N$ , how many different choices do you have for option sets to take?

Find a general formula and give your answer as the total number of different option sets corresponding to $n=10$ .

The answer is 59038.

1 solution

Daniel Ellesar
Jul 3, 2020

For each topic $A_i:i\in\{1, 2, ..., n\}$ , you can either:

not take that topic at all
take only $a_i$
take both $a_i$ and $b_i$

Hence there are three different choices corresponding to each topic. This means there are a total of $3^n$ different option sets.

Then also, you have to take at least two options in total.

In this, we have counted $n$ different option sets that only contain one option, and also the empty set.

Subtracting these from our answer, we get the total number of option sets that follow both the two rules is:

$3^n-n-1$

Indeed $3^{(10)}-(10)-1=\boxed{59038}$

A Level Options

The answer is 59038.

1 solution

0 pending reports