Puzzles
21 December
There are ten ways to make a list of four As and Bs that don't contain an even* number of consecutive As:
- B,B,B,B
- A,B,B,B
- B,A,B,B
- B,B,A,B
- B,B,B,A
|
- A,B,A,B
- A,B,B,A
- B,A,B,A
- A,A,A,B
- B,A,A,A
|
How many ways are there to make a list of eleven As and Bs that don't contain an even number of consecutive As?
* We don't count 0 consecutive As as being an even number of consecutive As.
Show answer
Hide answer
Valid sequences of length \(n\) can be made by doing one of the following:
- Taking a valid sequence of length \(n-1\) and adding a B to the end of it.
- Taking a valid sequence of length \(n-1\) that ends in B and adding a A to the end of it.
- Taking a valid sequence of length \(n-2\) that ends in A and adding two As to the end of it.
Therefore,
the number of sequences of length \(n\) that end in B is equal to the total number of sequences of length \(n-1\);
and the number of sequences of length \(n\) that end in A is equal to the number of sequences of length \(n-1\) that end in B plus the number of sequences of length \(n-2\) that end in A.
Using this we see that:
| \(n\) | number of sequences that end A | number of sequences that end B |
| 3 | 3 (A,A,A and A,B,A and B,B,A) | 3 (B,B,B and A,B,B and B,A,B) |
| 4 | 4 | 6 |
| 5 | 9 | 10 |
| 6 | 14 | 19 |
| 7 | 28 | 33 |
| 8 | 47 | 61 |
| 9 | 89 | 108 |
| 10 | 155 | 197 |
| 11 | 286 | 352 |
The total number of valid sequences of length 11 is 638.
18 December
There are 5 different ways to make a set of numbers between 1 and 5 such that the smallest number in the set is equal to the number of numbers in the set. These 5 sets are: {1}, {2, 3}, {2, 4}, {2, 5} and {3, 4, 5}.
How many ways are there to make a set of numbers between 1 and 14 such that the smallest number in the set is equal to the number of numbers in the set?
Show answer
Hide answer
The sets of numbers between 1 and \(n\) are either also valid sets with numbers between 1 and \(n-1\); or they can be made by taking a valid set of numbers
between 1 and \(n-2\), adding 1 to each number and appending an \(n\) to the set. Therefore the number of sets is the sum of the previous two terms (ie it's the Fibonacci sequence).
Using this, we can work out that the number of sets of numbers between 1 and 14 is 377.
14 December
There are five ways to make a list of four As and Bs that don't contain an odd number of consecutive As:
- B,B,B,B
- A,A,B,B
- B,A,A,B
- B,B,A,A
- A,A,A,A
How many ways are there to make a list of eleven As and Bs that don't contain an odd number of consecutive As?
Show answer
Hide answer
A valid sequence of length \(n\) can be made by either adding a single B to the right of a valid sequence of length \(n-1\)
or two As to a valid sequence of length \(n-2\). Therefore, the number of sequences of length \(n\) can be calculated by
adding the previous two terms (ie it's the Fibonacci sequence).
Using this, we can work out that the number of sequence of length eleven is 144.
11 December
There are 6 sets of integers between 1 and 5 (inclusive) that contain an odd number of numbers whose median value is 3:
- {3}
- {1,3,4}
- {2,3,4}
- {1,3,5}
- {2,3,5}
- {1,2,3,4,5}
How many sets of integers between 1 and 11 (inclusive) are there that contain an odd number of numbers whose median value is 5?
Show answer
Hide answer
If the set contains one number, then it must be {5}.
If the set contains three numbers, then it must contain 5, one number less than 5, and one number greater than 5. There are 4 numbers less than 5 and 6 numbers greater than 5 to choose from, giving
a total of 4×6 = 24 sets.
More generally, if the set contains \(2n+1\) numbers, then it must contain 5, \(n\) numbers less than 5, and \(n\) numbers greater than 5.
There are \(\left(\begin{array}{c}4\\n\end{array}\right)\) numbers less than 5 and \(\left(\begin{array}{c}6\\n\end{array}\right)\) numbers greater than 5 to choose from, giving
a total of \(\left(\begin{array}{c}4\\n\end{array}\right)\times\left(\begin{array}{c}6\\n\end{array}\right)\) sets.
In total there are
$$
1+24+
\left(\begin{array}{c}4\\2\end{array}\right)\times\left(\begin{array}{c}6\\2\end{array}\right)
+
\left(\begin{array}{c}4\\3\end{array}\right)\times\left(\begin{array}{c}6\\3\end{array}\right)
+
\left(\begin{array}{c}4\\4\end{array}\right)\times\left(\begin{array}{c}6\\4\end{array}\right)
$$
sets. This is equal to 210.
7 December
There are 8 sets (including the empty set) that contain numbers from 1 to 4 that don't include any consecutive integers:
\(\{\}\), \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{4\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{2, 4\}\)
How many sets (including the empty set) are there that contain numbers from 1 to 14 that don't include any consecutive integers?
