Problems

Filters
Clear Filters

3 problems found

2020 Paper 2 Q5
D: 1500.0 B: 1500.0
number theory digit sum divisibility modular arithmetic proof base 10 representation exhaustive search

If \(x\) is a positive integer, the value of the function \(\mathrm{d}(x)\) is the sum of the digits of \(x\) in base 10. For example, \(\mathrm{d}(249) = 2 + 4 + 9 = 15\). An \(n\)-digit positive integer \(x\) is written in the form \(\displaystyle\sum_{r=0}^{n-1} a_r \times 10^r\), where \(0 \leqslant a_r \leqslant 9\) for all \(0 \leqslant r \leqslant n-1\) and \(a_{n-1} > 0\).

  1. Prove that \(x - \mathrm{d}(x)\) is non-negative and divisible by \(9\).
  2. Prove that \(x - 44\mathrm{d}(x)\) is a multiple of \(9\) if and only if \(x\) is a multiple of \(9\). Suppose that \(x = 44\mathrm{d}(x)\). Show that if \(x\) has \(n\) digits, then \(x \leqslant 396n\) and \(x \geqslant 10^{n-1}\), and hence that \(n \leqslant 4\). Find a value of \(x\) for which \(x = 44\mathrm{d}(x)\). Show that there are no further values of \(x\) satisfying this equation.
  3. Find a value of \(x\) for which \(x = 107\mathrm{d}\left(\mathrm{d}(x)\right)\). Show that there are no further values of \(x\) satisfying this equation.

View
2007 Paper 1 Q1
D: 1500.0 B: 1500.0
combinatorics counting balanced number digit sum summation identity enumeration

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.

  1. Show that seventy \(4\)-digit balanced numbers can be made using the digits \(0, 1, 2, 3\) and \(4\).
  2. 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) } \;$.

Solution:

  1. 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}
  2. 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*}

View
2005 Paper 1 Q1
D: 1500.0 B: 1500.0
combinatorics digit sum stars and bars counting with constraints enumeration integer partitions

\(47231\) is a five-digit number whose digits sum to \(4+7+2+3+1 = 17\,\).

  1. Show that there are \(15\) five-digit numbers whose digits sum to \(43\). You should explain your reasoning clearly.
  2. How many five-digit numbers are there whose digits sum to \(39\)?

Solution:

  1. 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.
  2. 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}

View