Problems

Solution: We are choosing any \(5\) digit number from \(\{1,2,3,4,5\}\). There are \(5^5\) such numbers. \begin{align*} && \mathbb{E}(\text{different digits}) &= \frac1{5^5} \left (1 \cdot 5 + 2 \cdot \binom{5}{2}(2^5-2)+3 \cdot \binom{5}{3}(3^5-3 \cdot 2^5+3)+4 \cdot \binom{5}{4}(4^5 - 4 \cdot 3^5+6 \cdot 2^5-4) + 5 \cdot 5! \right) \\ &&&= \frac{2101}{625} = 3.3616 \end{align*}

Solution: There are \(1\,000\,000\) numbers between 1 and a million (inclusive). \(500\,000\) are divisible by \(2\), \(200\,000\) are divisible by \(5\) and \(100\,000\) are divisible by both. Therefore there are: \(1\,000\,000 - 500\,000-200\,000+100\,000 = 400\,000\). (Alternatively, the only numbers are those which are \(1,3,7,9 \pmod{10}\) so there are \(4\) every \(10\), or \(4 \cdot 100\,000\)). We can sum all these values similarly, \begin{align*} S &= \underbrace{\sum_{i=1}^{10^6} i}_{\text{all numbers}}-\underbrace{\sum_{i=1}^{5 \cdot 10^5} 2i}_{\text{all multiples of } 2}-\underbrace{\sum_{i=1}^{2 \cdot 10^5} 5i}_{\text{all multiples of } 5}+\underbrace{\sum_{i=1}^{10^5} 10i}_{\text{all multiples of } 5} \\ &= \frac{10^6 \cdot (10^6 + 1)}{2} - \frac{10^6 \cdot (5\cdot 10^5+1)}{2} - \frac{10^6 \cdot (2\cdot 10^5+1)}{2} + \frac{10^6 \cdot (10^5+1)}{2} \\ &= \frac{10^6 (10^5 \cdot (10-5-2+1))))}{2} \\ &= \frac{10^6 \cdot 10^5 \cdot 4}{2} \\ &= 2\cdot 10^{11} \end{align*} So the average value is \(\frac{2 \cdot 10^{11}}{4 \cdot 10^5} = \frac{10^6}{2} = 500\,000\). (Alternatively, each value can be paired off eg \(999\,999\) with \(1\) and so on, leaving averages of \(500\,000\)). Note that \(4197\) is divisible by \(3\) and \(7\). Using the same long we have: \(4179 - \frac{4179}{3} - \frac{4179}{7} + \frac{4179}{21} = 4179 - 1393 - 597 + 199 = 2388\). The sum will be: \begin{align*} S &= \underbrace{\sum_{i=1}^{4179}i }_{\text{all numbers}}- \underbrace{\sum_{i=1}^{1393}3i }_{\text{multiples of }3}- \underbrace{\sum_{i=1}^{597}7i }_{\text{multiples of }7}+ \underbrace{\sum_{i=1}^{199}21i }_{\text{mulitples of }21} \\ &= \frac{4179 \cdot 4180}{2} - \frac{4179 \cdot 1394}{2} - \frac{4179 \cdot 598}{2} +\frac{4179 \cdot 200}{2} \\ &= \frac{4179 \cdot 2388}{2} \end{align*} So the average value is \(\frac{4179}{2}\).

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\)

Solution:

1. \begin{align*} && p_n &= \mathrm{P}(A\leqslant k\mbox{ and }B\geqslant1-k) \\ &&&= \mathrm{P}(A\leqslant k) +\P(B\geqslant1-k) - \mathrm{P}(A\leqslant k\mbox{ or }B\geqslant1-k)\\ &&&= 1-\mathrm{P}(A\geq k) +1-\P(B \leq 1-k) - \l 1- \mathrm{P}(A\geq k\mbox{ and }B\leq 1-k)\r\\ &&&= 1 - \P(X_i \geq k) - \P(X_i \leq 1-k) + \P(k \leq X_i \leq 1-k) \\ &&&= 1 - k^n - (1-k)^n + (1-2k)^n \end{align*} Therefore as \(n \to \infty\) \(p_n \to 1\), since \(k, (1-k), (1-2k)\) are all between \(0\) and \(1\) and so their powers will tend to \(0\).
2. Let \(N = 4\,000\,000\). The probability exactly one person wins is \(Np(1-p)^{N-1}\). The probability exactly two people win is \(\binom{N}{2} p^2 (1-p)^{N-2}\). We wish to maximise the sum of these probabilities. To find this maximum, differentiate wrt \(p\). \begin{align*} \frac{\d}{\d p} : && \small N(1-p)^{N-1}-N(N-1)p(1-p)^{N-2} + N(N-1)p(1-p)^{N-2} - \frac12 N(N-1)(N-2)p^2(1-p)^{N-3} \\ &&= N(1-p)^{N-3} \l (1-p)^2 - \frac12(N-1)(N-2)p^2\r \\ \Rightarrow && \frac{(1-p)}{p} = \sqrt{\frac{(N-1)(N-2)}{2}} \\ \Rightarrow && p = \frac{1}{1+ \sqrt{\frac{(N-1)(N-2)}{2}}} \end{align*} This will be a maximum, since this is an increasing function at \(p=0\) and decreasing at \(p=1\) and there's only one stationary point. Note that \(p > \frac{\sqrt{2}}{(N-2)}\) and \(p < \frac{\sqrt{2}}{N-1+\sqrt{2}} < \frac{\sqrt{2}}{N}\) and so: \begin{align*} Np(1-p)^{N-1} &< \sqrt{2}(1-\frac{\sqrt{2}}{N-2})^{N-1} \\ &\approx \sqrt{2} e^{-\sqrt{2}} \end{align*} \begin{align*} \frac{N(N-1)}{2}p^2(1-p)^{N-2} &<(1-\frac{\sqrt{2}}{N-2})^{N-1} \\ &\approx e^{-\sqrt{2}} \end{align*} Alternatively, we can use a Poisson approximation. The number of winners is \(B(N, p)\) where we are hoping \(np\) is small but not zero. Therefore it's reasonable to approximation \(B(N,p)\) by \(Po(Np)\). (Call this value \(\lambda\)). Then we wish to maximise: \begin{align*} && p &= e^{-\lambda} \l \lambda + \frac{\lambda^2}{2} \r \\ &&&= e^{-\lambda} \lambda \l 1+ \frac{\lambda}{2} \r \\ \Rightarrow && \ln p &= -\lambda + \ln \lambda + \ln(1+\frac12 \lambda) \\ \frac{\d}{\d \lambda}: && \frac{p'}{p} &= -1 + \frac{1}{\lambda} + \frac{1}{2+\lambda} \\ &&&= \frac{-(2+\lambda)\lambda+2+2\lambda}{\lambda(2+\lambda)} \\ &&&= \frac{2-\lambda^2}{\lambda(2+\lambda)} \\ \Rightarrow && \lambda &= \sqrt{2} \end{align*} \begin{align*} \frac{\sqrt{2}+1}{e^{\sqrt{2}}} &< \frac{\sqrt{2}+1}{1+\sqrt{2}+1+\frac{1}{3}\sqrt{2}+\frac{1}{6}} \\ &= \frac{30\sqrt{2}-18}{41} \end{align*} Either way, we find we want to estimate \(e^{-\sqrt{2}}(1+\sqrt{2})\)