Three rods have lengths \(a\), \(b\) and \(c\), where \(a< b< c\). The three rods can be made into a triangle (possibly of zero area) if \(a+b\ge c\).
Let \(T_{n}\) be the number of triangles that can be made with three rods chosen from \(n\) rods of lengths \(1\), \(2\), \(3\), \(\ldots\) , \(n\) (where \(n\ge3\)). Show that \(T_8-T_7 = 2+4+6\) and evaluate \(T_8 -T_6\). Write down expressions for \(T_{2m}-T_{2m-1}\) and \(T_{2m} - T_{2m-2}\).
Prove by induction that \(T_{2m}=\frac 16 m (m-1)(4m+1)\,\), and find the corresponding result for an odd number of rods.
Show Solution
Every \(T_7\) triangle is valid, so we are interested in new triangles which have \(8\) has a longest side.
We can have:
\begin{array}{c|c|c}
\text{longest} & \text{middle} & \text{shortest} \\ \hline
8 & 7 & 1-6 \\
8 & 6 & 2-5 \\
8 & 5 & 3-4
\end{array}
which is \(6+4+2\) extra triangles.
The new ones excluding all the sixes are:
\begin{array}{c|c|c}
\text{longest} & \text{middle} & \text{shortest} \\ \hline
8 & 7 & 1-6 \\
8 & 6 & 2-5 \\
8 & 5 & 3-4 \\
7 & 6 & 1-5 \\
7 & 5 & 2-4 \\
7 & 4 & 3 \\
\end{array}
Ie \(2+4+6 + 1 + 3+5\)
\(T_{2m}-T_{2m-1} = 2 \frac{(m-1)m}{2} = m(m-1)\) and \(T_{2m}-T_{2m-2} = \frac{(2m-2)(2m-1)}{2}\)
\(T_4 = 3\) (\(1,2,3\), \(1,3,4\), \(2,3,4\))
and \(\frac16 \cdot 2 \cdot 1 \cdot 9 = 3\) so the base case holds.
Suppose it's true for some \(m = k\), then
\begin{align*}
&& T_{2(k+1)} &= T_{2k} + \frac{2m(2m+1)}{2} \\
&&&= \frac{m(m-1)(4m+1)}{6} + \frac{6m(2m+1)}{6}\\
&&&= \frac{m(4m^2-3m-1+12m+6)}{6} \\
&&&= \frac{m(4m^2+9m+5)}{6}\\
&&&= \frac{m(4m+5)(m+1)}{6}\\
&&&= \frac{(m+1-1)(4(m+1)+5)(m+1)}{6}\\
\end{align*}
as required, therefore it is true by induction.
For odd numbers, we can see that \(T_{2m-1} = \frac{m(m-1)(4m+1)}{6} - m(m-1) = \frac{m(m-1)(4m-5)}{6}\)
A positive integer with \(2n\) digits (the first of which must not be \(0\)) is called a balanced number if the sum of the first \(n\) digits equals the sum of the last \(n\) digits.
For example, \(1634\) is a \(4\)-digit balanced number, but \(123401\) is not a balanced number.
- Show that seventy \(4\)-digit balanced numbers can be made using the digits \(0, 1, 2, 3\) and \(4\).
- Show that \(\frac16 {k \left( k+1 \right) \left( 4k+5 \right) }\) \(4\)-digit balanced numbers can be made using the digits \(0\) to \(k\).
You may use the identity $\displaystyle \sum _{r=0}^{n} r^2 \equiv \tfrac{1}{6} {n \left( n+1 \right)
\left( 2n+1 \right) } \;$.
Show Solution
- For each number from \(1\) to \(8\) (4+4), we can count the number of ways it can be achieved in any way, or without including a leading \(0\).
\begin{array}{c|c|c|c}
\text{total} & \text{ways with }0 & \text{ways without } 0 & \text{comb}\\ \hline
8 & 1 & 1 & 1\\
7 & 2 & 2 & 4 \\
6 & 3 & 3 & 9 \\
5 & 4 & 4 & 16 \\
4 & 5 & 4 & 20 \\
3 & 4 & 3 & 12 \\
2 & 3 & 2 & 6 \\
1 & 2 & 1 & 2 \\ \hline
&&& 70
\end{array}
- For \(2k\) to \(k+1\) there are \(1 \times 1 + 2 \times 2 + \cdots i\times i+\cdots + k\times k\) ways to achieve this, (we can choose anything from \(k\) to \(k-i+1\) for the first digit, and we can never have a \(0\).
For \(1\) to \(k\) we can have \(1 \times 2 + 2 \times 3 + \cdots + k \times (k+1)\) since we cannot start with a \(0\), but can have anything less than or equal to \(i\) for the first digit, and then with the \(0\) we can have the same thing starting with \(0\).
Hence the answer is:
\begin{align*}
&& S &= \sum_{i=1}^k i^2 + \sum_{i=1}^k i (i+1) \\
&&&= 2\sum_{i=1}^k i^2 + \sum_{i=1}^k i \\
&&&= \frac{1}{3} k(k+1)(2k+1) + \frac12k(k+1) \\
&&&= k(k+1) \left (\frac{2k+1}{3} + \frac{1}{2} \right) \\
&&&= \frac16 k(k+1)(4k+2+3) \\
&&&= \frac16 k(k+1)(4k+5)
\end{align*}
\(47231\) is a five-digit number whose digits sum to \(4+7+2+3+1 = 17\,\).
- Show that there are \(15\) five-digit numbers whose digits sum to \(43\).
You should explain your reasoning clearly.
- How many five-digit numbers are there whose digits sum to \(39\)?
Show Solution
- The largest a five-digit number can have for its digit sum is \(45 = 9+9+9+9+9\). To achieve \(43\) we can either have 4 9s and a 7 or 3 9s and 2 8s. The former can be achieved in \(5\) ways and the latter can be achieved in \(\binom{5}{2} = 10\) ways. (2 places to choose to put the 2 8s). In total this is \(15\) ways.
- To achieve \(39\) we can have:
\begin{array}{c|l|c}
\text{numbers} & \text{logic} & \text{count} \\ \hline
99993 & \binom{5}{1} & 5 \\
99984 & 5 \cdot 4 & 20 \\
99974 & 5 \cdot 4 & 20 \\
99965 & 5 \cdot 4 & 20 \\
99884 & \binom{5}{2} \binom{3}{2} & 30 \\
99875 & \binom{5}{2} 3! & 60 \\
99866 & \binom{5}{2} \binom{3}{2} & 30 \\
98886 & 5 \cdot 4 & 20 \\
98877 & \binom{5}{2} \binom{3}{2} & 30 \\
88887 & \binom{5}{1} & 5 \\ \hline
&& 240
\end{array}
How many integers between \(10\,000\) and \(100\,000\) (inclusive) contain exactly two different digits? (\(23\,332\) contains exactly two different digits but neither of \(33\,333\) and \(12\,331\) does.)
Show Solution
First consider \(5\) digit numbers containing at most \(2\) non-zero digits. Then there are \(\binom{9}{2}\) ways to choose the two digits, and \(2^{5}-2\) different ways to arrange them, removing the ones which are all the same.
Considering all the pairs including zero, there are \(9\) ways to choose the non-zero (first) digit. There are \(2^4-1\) remaining digits where not all the numbers are the same.
Finally we must not forget \(100\,000\).
Therefore there are \(\binom{9}{2}(2^5-2) +9\cdot(2^4-1) + 1 = 1216\)
Show that you can make up 10 pence in eleven ways using 10p, 5p, 2p and 1p coins.
In how many ways can you make up 20 pence using 20p, 10p, 5p, 2p and 1p coins?
You are reminded that no credit will be given for unexplained answers.
Show Solution
Writing out the possibilities in order of the largest coin used (and then second largest and so-on):
\begin{align*}
&& 10 &= 10 \\
&&&= 5 + 5 \\
&&&= 5 + 2 + 2 + 1 \\
&&&= 5 + 2 + 1 + 1 + 1 \\
&&&= 5 + 1 + 1 + 1 + 1 + 1\\
&&&= 2 + 2 + 2 + 2 + 2 = 5 \cdot 2\\
&&&= 4 \cdot 2 + 2 \cdot 1 \\
&&&= 3 \cdot 2 + 4 \cdot 1\\
&&&= 2 \cdot 2 + 6\cdot 1\\
&&&= 1 \cdot 2 + 8\cdot 1 \\
&&&= 10 \cdot 1
\end{align*}
For 20p, we have
\begin{align*}
&& 20 &= 20 \\
&&&= 10 + \text{all 11 ways} \\
&&&= 4\cdot 5 \\
&&&= 3\cdot 5 +\text{3 ways} \\
&&&= 2\cdot5 + \text{6 ways} \\
&&&= 1\cdot 5 + \text{8 ways} \\
&&&= k\cdot 2 + (20-2k)\cdot 1 \quad \text{11 ways}
\end{align*}
ie 41 ways
I have two dice whose faces are all painted different colours. I number
the faces of one of them \(1,2,2,3,3,6\) and the other \(1,3,3,4,5,6.\)
I can now throw a total of 3 in two different ways using the two number
\(2\)'s on the first die once each. Show that there are seven different
ways of throwing a total of 6.
I now renumber the dice (again only using integers in the range 1
to 6) with the results shown in the following table
\noindent
| Total shown by the two dice | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Different ways of obtaining the total | 0 | 2 | 1 | 1 | 4 | 3 | 8 | 6 | 5 | 6 | 0 |
\par
Find how I have numbered the dice explaining your reasoning.
{[}You will only get high marks if the examiner can follow your argument.{]}
A \(3\times3\) magic square is a \(3\times3\) array
\[
\begin{array}{ccc}
a & b & c\\
d & e & f\\
g & h & k
\end{array}
\]
whose entries are the nine distinct integers \(1,2,3,4,5,6,7,8,9\) and which has the property that all its rows, columns and main diagonals add up to the same number \(n\). (Thus \(a+b+c=d+e+f=g+h+k=a+d+g=b+e+h=c+f+k=a+e+k=c+e+g=n.)\)
- Show that \(n=15.\)
- Show that \(e=5.\)
- Show that one of \(b,d,h\) or \(f\) must have value \(9\).
- Find all \(3\times3\) magic squares with \(b=9.\)
- How many different \(3\times3\) magic squares are there? Why?
{[}Two magic squares are different if they have different entries in any place of the array.{]}
Show Solution
- \((a+b+c)+(d+e+f)+(g+h+k) = 3n = 1 + 2 + \cdots + 9 = 45 \Rightarrow n = 15\).
- Summing all rows, columns, diagonals through \(e\) we have \((a+e+k)+(b+e+h)+(c+e+g)+(d+e+f) = 45 + 3e = 60 \Rightarrow e = 5\).
- Suppose that one of the corners is \(9\), then we need to find \(2\) ways to make \(6\) not using \(5\) and \(1\) (as \(5\) is in the middle and \(1\) diagonally opposite). Clearly this is not possible as the only remaining numbers are \(2,3,4\) and only \(2+4 = 6\). Therefore \(9\) cannot be in the corner or central squares, ie it's one of \(b,d,h,f\)
- We must have
\begin{array}{ccc}
a & 9 & c\\
d & 5 & f\\
g & 1 & k
\end{array} and so \(a\) or \(c = 4\). Once we place \(4\) by symmetry there will be another solution with \(a = 2\). So:
\begin{array}{ccc}
4 & 9 & 2\\
d & 5 & f\\
g & 1 & k
\end{array}
we now see \(k\), then \(f\), then \(d\) then \(g\) must be determined, ie:
\begin{array}{ccc}
4 & 9 & 2\\
3 & 5 & 7\\
8 & 1 & 6
\end{array}
so our two solutions must be this and
\begin{array}{ccc}
2 & 9 & 4\\
7 & 5 & 3\\
6 & 1 & 8
\end{array}
- For each of the \(4\) possible placements of \(9\) there are two magic squares, so there are \(8\) possible magic squares, all related by reflection and rotation.