CSAT 1

Section A

1. You have a card of 10cm by 10cm. What is the largest volume in cm³ of a box (without a lid) that can be obtained by cutting out a square of side x from each corner and then folding the flaps up?

We can obtain an idea of the solution by looking at the following diagram:

The box will have a base (marked in red on the diagram) with area $(l-2x)^2$ and height $x$. Therefore the volume of this box will be \begin{equation*} V=(l-2x)^x. \end{equation*} To maximize the volume first calculate \[ \dv{V}{x}=-4(l-2x)x+(l-2x)^2 \] using the product rule $d(u\cdot v)=du \cdot v + u \cdot dv$. Solve for $\dv*{V}{x}=0$ to find a (potential) maximum. If we assume that $x\neq l$ (a reasonable assumption since $x=l/2$ creates a nothing box) then \begin{align*} -4(l-2x)x+(l-2x)^2& =0 \\ l-2x-4x & = 0 \\ x & = \frac{l}{6}. \end{align*} To check that this is indeed a maximum calculate \[ \dv[2]{V}{x}=8x-4(l-2x)-4(l-2x)=24x-8l. \] If we substitute $l/6$ for $x$ in this equation we obtain \[ \eval{\dv[2]{V}{x}}_{x=\frac{l}{6}} = 24 \frac{l}{6} - 8l =-4l<0 \] and hence the volume of the box is the greatest when $x=l/6 = 5/3$ cm. Substituting $l=10$ cm and the value for $x$ in the formula for the volume we obtain \[ V^*=\qty(10-2\frac{10}{6})^2\frac{5}{3}=10^2 \frac{4}{9}\frac{5}{3}=\frac{2}{27} 10^3 \; \text{cm}^3 \] where the $*$ in $V^*$ indicates that this is an optimal quantity.

2. Let $f(x)$ mean that function $f$ is applied to $x$ and $f^n(x)$ mean $f(f(\ldots f(x)))$, that is $f$ is applied to $x$, $n$ times. Let $g(x)=x+1$ and $h_n(x)=g^n(x)$. What is $h^m_n(0)$?

Since $g(x)=x+1$ \begin{align*} g^2(x) & = g(g(x))=g(x+1)=(x+1)+1=x+2 \\ g^3(x) & = g(g^2(x))=g(x+2)=x+3 \\ \ldots & \phantom{-----}\ldots \end{align*} Extending this pattern we have $g^n(x)=x+n$ and therefore $h_n(x)=x+n$.

Following the same logic we have \begin{align*} h_n^2(x) & = h_n(h_n(x))=h_n(x+n)=(x+n)+n=x+2n \\ h_n^3(x) & = h_n(h_n^2(x))=h_n(x+2n)=x+3n \\ \ldots & \phantom{-----}\ldots \end{align*} and so $h^m_n(x)=x+nm$ from which we obtain $h^m_n(0)=nm$.

3. Triangle $ABC$ is isosceles with $AB = AC$. Let the circle having diameter $AB$ and centre $O$ intersect $BC$ at some point $P$. Find the ratio $BP/BC$.

The diagram gives some ideas how to go about it. $AB$ is the diameter of the circle (by construction) and point $P$ lies on the circumference of the circle (also by construction). $\angle APB$ subtends the diameter of the circle and is therefore equal to $90^\circ$. For an isosceles triangle, the height to its base $AP$ intersects it at the midpoint so $BP=CP$. Since $BC=BP+CP$ we conclude that $BP/BC=1/2$.

4. What is the units digit of the number $\sum_{n=1}^{1337}(n!)^4$?

Looking at the formula in the question we are faced with the possibility of calculating factorials for a very long time. The only possibility that this question can be solved within the time alloted is if most of the factorials have a zero units digit. This is correct; it is the case that 1!, 2!, 3!, 4! have a non-zero units digit; but for $n\geq 5$ we have \[ n!=n(n-1)\cdots 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = n (n-1) \cdots 4 \cdot 2 \cdot 10. \] Therefore for $n\geq 5$ all factorials have a unit digit equal to 0. The units digit of $\sum_{n=1}^{1337}(n!)^4$ is the same as the units digit of $\sum_{n=1}^{4}(n!)^4$.

Next we must find the units digits of these factorials to the power of four. The units digit of any integer $n$ is given by $\def\mod#1#2{#1 \;(\operatorname{mod} #2)}\mod{n}{10}$; this expression is read as "the residue of $n$ modulo 10." The rules of modular arithmetic show that for any $n$, $$ \mod{n}{10}=\{0,1,2,3,4,5,6,7,8,9\}. $$ For any two integers $n,m$, $$ \mod{nm}{10}=\mod{\qty(\qty(\mod{n}{10})\qty(\mod{m}{10}))}{10}. $$ Using this property we can construct the following table: \[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline n= & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline n^2 & 0 & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64 & 81 \\ n^2 & 0 & 1 & 4 & 9 & 6 & 5 & 6 & 9 & 4 & 1 \\ \hline n\cdot n^2 & 0 & 1 & 8 & 27 & 24 & 25 & 36 & 63 & 32 & 9 \\ n^3 & 0 & 1 & 8 & 7 & 4 & 5 & 6 & 3 & 2 & 9 \\ \hline n \cdot n^3 & 0 & 1 & 16 & 21 & 16 & 25 & 36 & 21 & 16 & 81 \\ n^4 & 0 & 1 & 6 & 1 & 6 & 5 & 6 & 1 & 6 & 1 \\ \hline n\cdot n^4 & 0 & 1 & 12 & 3 & 24 & 25 & 36 & 7 & 48 & 9 \\ n^5 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \end{array} \] Using the rules of modular arithmetic \begin{equation*} \mod{\qty(\sum_{n=1}^{4}(n!)^4)}{10} = \sum_{n=1}^{4} \mod{(n!)^4}{10}. \end{equation*} All factorials except from the factorial of 1 are even; from the table $\mod{n^4}{10}$ is equal to 1 for odd and 6 for even numbers. Therefore \[ \mod{\sum_{n=1}^{1337}(n!)^4}{10} = \mod{(1 + 6 + 6 + 6)}{10}=9. \]

5. Using only the functions $\max$ and $\min$ and arithmetic operations (no if clauses), express the amount of possible overlap between two intervals $[a_1,a_2]$ and $[b_1,b_2]$, where $a_1,a_2,b_1,b_2$ are arbitrary real numbers with $a_1< a_2$ and $b_1< b_2$.

Lets first start with a case in which there is non-zero overlap:

The overlap in this case is $a_2-b_1$; one way of writing this using $\min$ and $\max$ and all the real numbers is \[ \min(a_2,b_2)-\max(a_1,b_1)=a_2-b_1. \] We use the $\max$ for $a_1,b_1$ and $\min$ for $a_2, b_2$ since in this case the overlap extends from the largest of the smallest numbers to the smallest of the largest numbers in each pair. Note that since $a_2=\max(a_2,b_1)$ we can obtain the same result by writing \[ \max(a_2,b_1)-\max(b_1,a_1) \] but the problem with this formula is that it is devoid of $b_2$. So, for the moment, we are happy using this first stab at the problem.

Another overlap scenario is shown below:

Now the overlap is $a_2-a_1$; the formula still works since \[ \min(a_2,b_2)-\max(a_1,b_1)= a_2-a_1. \] The next scenario is

in which case the overlap is $b_2-b_1$. The formula still works since now $\min(a_2,b_2)=b_2$ and $\max(a_1,b_1)=b_1$. The final case of non-zero overlap we have to consider is

in which case the overlap is $b_2-a_1$. Now the formula produces \[ \min(a_2,b_2)-\max(a_1,b_1)=b_2 -a_1 \] which is correct.

We have not considered the two cases for which there is zero overlap. First

Here the formula no longer works since \[ \min(a_2,b_2)-\max(a_1,b_1)=a_2-b_1 \] which is a negative number. We encounter the same problem in the second zero overlap case:

Now \[ \min(a_2,b_2)-\max(a_1,b_1)=b_2-a_1 \] which is also a negative number. We can correct this deficiency by noting that $\max(x,0)=0$ when $x< 0$. So if we modify the formula to \[ \max\qty(\min(a_2,b_2)-\max(a_1,b_1),0) \] we arrive at the correct solution.

6. Which values of $k$ give a maximum at $x=-1$ for \[ f(x)=(k+1)x^4 - (3k+2) x^2 - 2kx. \]

First note that \[ f'(x)=4(k+1)x^3-2(3k+2)x-2k. \] For $f(x)$ to have a maximum or a minimum at $x=-1$ we must have $f'(1)=0$. We can write \[ f'(1)=4(k+1)-2(3k+2)-2k=0. \] It is easy to check that this equation holds for all values of $k$ since the r.h.s. is zero. Since \[ f''(x)=12(k+1)x^2-2(3k+2) \] for $f(x)$ to have a maximum at $x=-1$ we nust have \[ f''(-1)=12(k+1)-2(3k+2)< 0 \] or $k < -4/3$.

7. The Taylor expansion of $\ln(1+x)$ is defined as \[ \ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\cdots . \] Expand $\ln\qty(\frac{1-x}{1+x^2})$ up to and including the 4th power of $x$.

Since \[ \ln\qty(\frac{a}{b})=\ln a - \ln b \] we can write \[ \ln\qty(\frac{1-x}{1+x^2})=\ln(1-x)-\ln(1+x^2). \] Using the formula for the Taylor expansion we can write \begin{align*} \ln(1-x) & = -x-\frac{x^2}{2}-\frac{x^3}{3}-\frac{x^4}{4}-\cdots \\ \ln(1+x^2) & = x^2-\frac{x^4}{2}+\frac{x^6}{3}-\cdots . \end{align*} If we only use the terms in each expansion up to the 4th power we obtain \begin{align*} \ln\qty(\frac{1-x}{1+x^2}) & = -x-\frac{x^2}{2}-\frac{x^3}{3}-\frac{x^4}{4}-\qty(x^2-\frac{x^4}{2})+ \cdots \\ & = -x -\frac{3x^2}{2}-\frac{x^3}{3}+\frac{x^4}{4}+ \cdots. \end{align*}

8. Given a grid of $4 \times 4$ points, how many triangles with their vertices on the grid can be drawn?

If we ignore the geometry there is a simple solution using combinatorics. There are 16 distinct points. Each point can be combined with 15 other points and then given this pair of points we can choose 14 other points for the third vertex of the triangle. There are therefore $16\times 15\times 14$ triangles that can be drawn. However note that there are $3!$ ways in which three different points can be combined. So the number of combinations of three points is \[ \frac{16\times 15 \times 14}{3 \times 2 \times 1}= \frac{16!}{3!13!}=560. \] This is not the correct answer; we have ignored the geometry which means that any three colinear points are included in the 560 number. For example, this grid contains the following four horizontal and vertical lines:

In each case we have $4!/(3!1!)=4$ combinations of 3 points that are colinear.

We also have to consider the following major and minor diagonals:

The 2 major diagonals, like the horizontal and vertical lines, contain 4 points from each of which we can obtain $4!/(3!1!)=4$ combinations. Therefore from the $8+2=10$ horizontal, vertical and major diagonal lines we obtain a total of 40 combinations. Finally, from the 4 minor diagonals we have 3 points that each give rise to $1$ additional combination. Therefore these minor diagonals add an additional 4 combinations and the total number of 3-point combinations of colinear points is 44. $560-44=516$ which is the number of triangles we can draw on this $4 \times 4$ grid.

Section B

9. Player A rolls one die. Player B rolls two dice. If A rolls a number greater or equal to the largest number rolled by B, then A wins, otherwise B wins. What is the probability that B wins?

The table of possible outcomes for player A together with the corresponding probabilities is shown below: \[ \begin{array}{|c|c|c|c|c|c|} \hline \text{roll} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \text{probability} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \\ \hline \end{array} \] The table of possible outcomes for player B together with the corresponding probabilities is shown below: \[ \def\r#1{\color{red}{#1}} \def\b#1{\color{blue}{#1}} \begin{array}{|c|c|c|c|c|c|c|} \hline & \b{1} & \b{2} & \b{3} & \b{4} & \b{5} & \b{6} \\ \hline \r{1} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{2} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{3} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{4} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{5} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{6} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \end{array} \] In order for player B to win, the largest of the two numbers he rolls must be greater than the single number player A rolls. Looking at the table above, the probability that his largest roll is 1 is $\frac{1}{36}$. To calculate the probability that his largest roll is 2 we can note that \[ \begin{array}{|c|c|c|c|c|c|c|} \hline & \b{1} & \b{2} & \b{3} & \b{4} & \b{5} & \b{6} \\ \hline \r{1} & \frac{1}{36} & \cellcolor{lightgray}{\frac{1}{36}} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{2} & \cellcolor{lightgray}\frac{1}{36} & \cellcolor{lightgray}{\frac{1}{36}} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{3} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{4} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{5} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \r{6} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} & \frac{1}{36} \\ \hline \end{array} \] there are 3 such events with a total probability of $\frac{3}{36}$. Following this line of thinking we find that \[ b_n = \frac{2n-1}{36} \] where $b_n$ s the probability that the largest number B rolls is $n$. For A the calculation is much simpler; the probability that A rolls a number greater or equal than $n$ is \[ a_n = \frac{7-n}{6}. \] A will win if the number she rolls is greater or equal than B. Therefore \begin{align*} \def\p{\mathbb{P}} \p\qty(\text{A wins}) & =a_1 b_1 + a_2b_2 + a_3b_3 + a_4b_4 + a_5b_5 + a_6b_6 \\ & = \frac{6}{6} \frac{1}{36} + \frac{5}{6} \frac{3}{36} + \frac{4}{6} \frac{5}{36} + \frac{3}{6} \frac{7}{36} + \frac{2}{6} \frac{9}{36} + \frac{1}{6} \frac{11}{36} \\ & = \frac{6+15+20+21+18+11}{6 \cdot 36} = \frac{91}{216} \end{align*} and \[ \p\qty(\text{B wins})=1-\p\qty(\text{A wins})=\frac{216-91}{216}=\frac{125}{216}. \]

10. A circle of radius $r$ is tangent at two points on the parabola $y = x^2$ such that the angle between the two radii at the tangent points is $2\theta$, where $0 < 2\theta < \pi$. Find $r$ as a function of $\theta$.

Since the parabola is centered around $x=0$ the only way for the circle to be tangent at two point is for the center of the circle to lie on the $y$-axis. We can therefore simplify the derivations by writing the equation of the circle as \[ C: \quad x^2+(y-y_0)^2=r^2. \]

Differentiating both sides of the equation for $C$ we obtain \[ 2x+2(y-y_0)\dv{y}{x}=0 \Rightarrow \dv{y}{x}=-\frac{x}{y-y_0}. \] Since for the parabola \[ \dv{y}{x}=2x \] at the points where the circle is tangent to the parabola we must have \[ 2x = -\frac{x}{y-y_0} \] or \[ x^2 = y_0 - \frac{1}{2} \] using the fact that at the tangency point $y=x^2$. As long as $y_0 > \frac{1}{2}$, $x_{1,2}=\pm \sqrt{\qty(y_0-\frac{1}{2})}$ and $y_{1,2}=y_0-\frac{1}{2}$. Given the configuration shown in the diagram above, the two tangent points and $(0,y_0)$ form an isosceles triangle. We have defined the angle subtended by the two radii as $2\theta$. Since the $y$-coordinate of the tangent points is $y_0-\frac{1}{2}$ and the $x$-coordinate is $\pm \sqrt{\qty(y_0-\frac{1}{2})}$ we have \[ \cos\theta=\frac{y_0-\qty(y_0-\frac{1}{2})}{r}=\frac{1}{2r}, \quad \sin\theta=\frac{\sqrt{\qty(y_0-\frac{1}{2})}}{r}. \] Using the trigonometric identity \[ \cos 2\theta = \cos^2\theta-\sin^2\theta \] we can write \[ \cos 2 \theta = \frac{1}{4r^2} - \frac{y_0-\frac{1}{2}}{r^2}. \] The triangle highlighted in grey has a hypotenuse of length $r$, one vertical side of length $y_0-\qty(y_0-\frac{1}{2})=\frac{1}{2}$ and another vertical side of length $x_1=\sqrt{\qty(y_0-\frac{1}{2})}$. From the Pythagorean theorem \[ r^2 = \qty(y_0-\frac{1}{2}) + \frac{1}{4}; \] hence we can rewrite the last equation as \begin{align*} \cos 2 \theta & = \frac{1}{4r^2} - \frac{r^2-\frac{1}{4}}{r^2} \\ r^2 \cos 2 \theta & =\frac{1}{2}-r^2 \end{align*} which is the same as \[ r = \frac{1}{\sqrt{2(1+\cos 2\theta)}}. \] To check this note that for $\theta=0$, $r=\frac{1}{2}$; $y_0=\frac{1}{2}$ and $x_{1,2}=y_{1,2}=0$. There is a single tangency point at the origin.

The restriction $\abs{2\theta}< \pi$ makes sense since for $2\theta=\pi$, $\cos 2 \theta =-1$.

11. An organism is born on day $k = 1$ with 1 cells. During day $k = 2,3,\ldots$ the organism produces $\frac{k^2}{k-1}$ times more new cells than it produced on day $k - 1$. Give a simplified expression for the total of all its cells after $n$ days. Hint: This is different to the number of new cells produced during day $n$.

There is a bit of linquistic uncertainty in the phrasing of the question. If someone writes “$x$ is $a$ times more than $y$” it could be taken to mean that $x=(1+a)y$; I assume that if $a>1$, “$x$ is $a$ times more than $y$” means $x=ay$. $\frac{k^2}{k-1}=k\frac{k}{k-1}> k >1$ for $k=2,3,\ldots$ and so this interpretation is valid.

Denote the number of cells produced on day $k$ as $p_k$; then based on the information given \[ p_k=\frac{k^2}{k-1}p_{k-1} \] where $p_k=1$. The total number of cells after $n$ days is \[ s_n = \sum_{k=1}^n p_k. \] To evaluate this sum note that \begin{align*} p_k & = \frac{k^2}{k-1}p_{k-1}=\frac{k^2}{k-1}\frac{(k-1)^2}{k-2}\cdots \frac{3^2}{2} \frac{2^2}{1} \\ & = \frac{k^2}{1} \frac{k-1}{1}\frac{k-2}{1}\cdots \frac{3}{1}\frac{2}{1}=k(k!). \end{align*} To reduce the expression \[ s_n = \sum_{k=1}^n k(k!) \] rewrite $k$ as $(k+1)-1$. Then \begin{align*} s_n & = \sum_{k=1}^n (k+1)! - \sum_{k=1}^n k! \\ & = \sum_{k=2}^{n+1} k! - \sum_{k=1}^n k! = (n+1)! -1 . \end{align*}

12. Let $n < 10$ be a non-negative integer. How many integers from 0 to 999 inclusive have the sum of their digits equal to $n$? Give your answer in terms of $n$. Hint: Try first for integers from 0 to 99.

The long way: We can represent all numbers from 0 to 999 using three digits $d_0 d_1 d_2$ some of which can be zero including the first one. For $n=9$ if any of the digits is equal to 9 the other two must be equal to 0. There are 3 numbers with this property (009,090,900); if one of the digits is equal to 8 the other two must add to 1. So one digit must be equal to 1 and the other equal to 0. Digits 0-1-8 can be arranged in 6 different ways. Following this logic we can construct the following table: \[ \begin{array}{cccc} \fbox{$9$}\\ \hline 9 & \ldots & 0-0 & 3 \text{ ways} \\ 8 & \ldots & 1-0 & 6 \text{ ways} \\ 7 & \ldots & 2-0 & 6 \text{ ways} & 1-1 & 3 \text{ ways} \\ 6 & \ldots & 3-0 & 6 \text{ ways} & 2-1 & 6 \text{ ways} \\ 5 & \ldots & 4-0 & 6 \text{ ways} & 3-1 & 6 \text{ ways} & 2-2 & 3 \text{ ways} \\ 4 & \ldots & 5-0 & - & 4-1 & 3 \text{ ways} & 3-2 & 6 \text{ ways} \\ 3 & \ldots & 6-0 & - & 5-1 & - & 4-3 & - & 3-3 & 1 \text{ way} \\ 2 & \ldots & 7-0 & - & 6-1 & - & 5-2 & - & 4-3 & - \\ 1 & \ldots & 8-0 & - & 7-1 & - & 6-2 & - & 5-3 & - & 4-4 & - \\ \hline \colorbox{lightgray}{55}& & & 27 \text{ ways} & & 18 \text{ ways} & & 9 \text{ ways} & & 1 \text{ way} \end{array} \] Where you see a $-$ it means this combination is already accounted for. This happens when one of the numbers in the combination is larger than the integer in the first column. So there are 55 numbers whose digits add up to 9.

Next we have \[ \begin{array}{cccc} \fbox{$8$}\\ \hline 8 & \ldots & 0-0 & 3 \text{ ways} \\ 7 & \ldots & 1-0 & 6 \text{ ways} \\ 6 & \ldots & 2-0 & 6 \text{ ways} & 1-1 & 3 \text{ ways} \\ 5 & \ldots & 3-0 & 6 \text{ ways} & 2-1 & 6 \text{ ways} \\ 4 & \ldots & 4-0 & 3 \text{ ways} & 3-1 & 6 \text{ ways} & 2-2 & 3 \text{ ways} \\ 3 & \ldots & 5-0 & - & 4-1 & - & 3-2 & 3 \text{ ways} \\ 2 & \ldots & 6-0 & - & 5-1 & - & 4-3 & - & 3-3 & - \\ 1 & \ldots & 7-0 & - & 6-1 & - & 5-2 & - & 4-3 & - \\ \hline \colorbox{lightgray}{45}& & & 24 \text{ ways} & & 15 \text{ ways} & & 6 \text{ ways} & & \end{array} \] There are 45 numbers whose digits add up to 8.

As we progress each case requires fewer lines: \begin{align*} & \begin{array}{cccc} \fbox{$7$}\\ \hline 7 & \ldots & 0-0 & 3 \text{ ways} \\ 6 & \ldots & 1-0 & 6 \text{ ways} \\ 5 & \ldots & 2-0 & 6 \text{ ways} & 1-1 & 3 \text{ ways} \\ 4 & \ldots & 3-0 & 6 \text{ ways} & 2-1 & 6 \text{ ways} \\ 3 & \ldots & 4-0 & - & 3-1 & 3 \text{ ways} & 2-2 & 3 \text{ ways} \\ 2 & \ldots & 5-0 & - & 4-1 & - & 3-2 & - \\ 1 & \ldots & 6-0 & - & 5-1 & - & 4-3 & - & 3-3 & - \\ \hline \colorbox{lightgray}{36}& & & 21 \text{ ways} & & 12 \text{ ways} & & 3 \text{ ways} & & \end{array} \\ & \begin{array}{cccc} \fbox{$6$}\\ \hline 6 & \ldots & 0-0 & 3 \text{ ways} \\ 5 & \ldots & 1-0 & 6 \text{ ways} \\ 4 & \ldots & 2-0 & 6 \text{ ways} & 1-1 & 3 \text{ ways} \\ 3 & \ldots & 3-0 & 3 \text{ ways} & 2-1 & 6 \text{ ways} \\ 2 & \ldots & 4-0 & - & 3-1 & - & 2-2 & 1 \text{ way} \\ 1 & \ldots & 5-0 & - & 4-1 & - & 3-2 & - \\ \hline \colorbox{lightgray}{28}& & & 18 \text{ ways} & & 9 \text{ ways} & & 1 \text{ way} & & \end{array} \\ & \begin{array}{cccc} \fbox{$5$}\\ \hline 5 & \ldots & 0-0 & 3 \text{ ways} \\ 4 & \ldots & 1-0 & 6 \text{ ways} \\ 3 & \ldots & 2-0 & 6 \text{ ways} & 1-1 & 3 \text{ ways} \\ 2 & \ldots & 3-0 & - & 2-1 & 3 \text{ ways} \\ 1 & \ldots & 4-0 & - & 3-1 & - & 2-2 & - \\ \hline \colorbox{lightgray}{21}& & & 15 \text{ ways} & & 6 \text{ ways} & & & & \end{array} \\ & \begin{array}{cccc} \fbox{$4$}\\ \hline 4 & \ldots & 0-0 & 3 \text{ ways} \\ 3 & \ldots & 1-0 & 6 \text{ ways} \\ 2 & \ldots & 2-0 & 3 \text{ ways} & 1-1 & 3 \text{ ways} \\ 1 & \ldots & 3-0 & - & 2-1 & - \\ \hline \colorbox{lightgray}{15}& & & 12 \text{ ways} & & 3 \text{ ways} & & & & \end{array} \\ & \begin{array}{cccc} \fbox{$3$}\\ \hline 3 & \ldots & 0-0 & 3 \text{ ways} \\ 2 & \ldots & 1-0 & 6 \text{ ways} \\ 1 & \ldots & 2-0 & - & 1-1 & 1 \text{ way} \\ \hline \colorbox{lightgray}{10}& & & 9 \text{ ways} & & 1 \text{ way} & & & & \end{array} \\ & \begin{array}{cccc} \fbox{$2$}\\ \hline 2 & \ldots & 0-0 & 3 \text{ ways} \\ 1 & \ldots & 1-0 & 3 \text{ ways} \\ \hline \colorbox{lightgray}{6}& & & 6 \text{ ways} & & & & & & \end{array} \\ & \begin{array}{cccc} \fbox{$1$}\\ \hline 1 & \ldots & 0-0 & 3 \text{ ways} \\ \hline \colorbox{lightgray}{3}& & & 3 \text{ ways} & & & & & & \end{array} \\ \end{align*}

We can summarize the results in the following table: \[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n= & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \text{#ways}= & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 & 55 \\ \hline \end{array} \] To try to recover a pattern write the difference between the number of ways for successive integers: \[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n= & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \text{#ways}= & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 & 55 \\ \hline \text{diff}= & - & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \end{array} \] Therefore we can write \[ \text{#ways}(n)=\text{#ways}(n-1)+(n+1). \] If we unroll this recursive relation and use the condition $\text{#ways}(0)=1$ we obtain \[ \text{#ways}(n)=\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}. \]

The short way: Given the first digit $d_0$, the sum of the digits of a number between 0 and 999 is equal to $n$ only if the second digit has the property $0\leq d_1 \leq n-d_0$. If the first and second digits have been selected then $d_2=n-d_0-d_1$ which is a unique value. Therefore using $d_0=0,…,n$ and the corresponding $n-d_0+1$ choices for $d_1$ we have \begin{align*} \text{#ways}(n)& =\sum_{d_0=0}^n (n-d_0+1)=(n+1)^2-\sum_{d_0=0}^n d_0 \\ & = (n+1)^2 - \frac{n(n+1)}{2} = (n+1) \qty(n+1 - \frac{n}{2}) \\ & =(n+1)\qty(\frac{n}{2}+1)=\frac{(n+1)(n+2)}{2}. \end{align*}

13. On a grid of $m \times n$ squares, how many ways exist to get from the top-left corner to the bottom-right corner if you can only move right or down on an edge?

Denote the coordinate of the top-left corner as $(0,m)$ and the coordinate of the bottom-right corner as $(n,0)$. A right move adds 1 to the x-coordinate while a down move subtracts 1 from the y-coordinate. To move from $(0,m)$ to $(n,0)$ we must have $n$ +1s and $m$ -1s. The problem of arranging $n$ +1 items and $m$ -1 items is a standard combination problem. We know that there are \[ \binom{n+m}{n} = \binom{n+m}{m} \] combinations.

14. You must slice a square of side length $b$ into 6 pieces with equal areas, using 3 lines that intersect each other inside the square, one of which is a diagonal. Where on the sides of the square, with respect to the nearest corner, should the other two lines cut? Give your answer in terms of $b$.

Before going into the formulas certain features of the solution may be obvious. We are told that one of the 3 lines is a diagonal. The other two lines must intersect it in such a way that all 6 pieces have the same area. Then we can immediately deduce that the two line must be parallel otherwise we encounter situations like the one below.

Looking at the same picture we observe that, since we have drawn a line that is not perpendicular to the main diagonal, the areas of $A$ and $F$ are not equal. The geometry of the problem requires that both the blue and the green line must have a slope equal to -1 in order for $A=F$ and $C=D$.

Lets denote the equation of the blue line as \[ l_1: \quad y=m_1 x + b_1. \] This line intersects the diagonal at a point with $x$-coordinate $x_1=b_1/(1-m_1)$. $l_1$ intersects the $x$-axis at $x=-b_1/m_1$; the area under $l_1$ from $0$ to $-b_1/m_1$ is equal to the sum of the areas of segments $A$ and $F$. So we can write \[ A+ F = \int_0^{-\frac{b_1}{m_1}} (m_1 x + b_1) dx = \frac{1}{2}m_1 \frac{b_1^2}{m_1^2}-b_1\frac{b_1}{m_1}=-\frac{b_1^2}{2m_1}. \]

Note that if $m_1\geq 0$ we do not have a solution. Area $F$ is given by \begin{align*} F & = \int_0^{\frac{b_1}{1-m_1}} (m_1x+b_1) dx - \int_0^{\frac{b_1}{1-m_1}} x dx \\ & = \int_0^{\frac{b_1}{1-m_1}} \qty((m_1-1)x+b_1) dx \\ & = \frac{1}{2}\frac{b_1^2}{1-m_1}. \end{align*} Since $A=F$ we must have $A=-\frac{b_1^2}{4m_1}$; then using the last expression for $F$ we have \[ \frac{1}{2}\frac{b_1^2}{1-m_1} = -\frac{b_1^2}{4m_1} \Rightarrow m_1=-1 \] as we originally postulated. Also, as instructed, $A=F=b^2/6$; therefore we must have $b_1=b\sqrt{\frac{2}{3}}$. Line $l_1$ intersects the $x$-axis and the $y$-axis at at $b\sqrt{\frac{2}{3}}$.

The grey strip between $l_1$ and the diagonal (shown in a dashed line) with equation $y=-x$ has an area equal to \[ \frac{b^2}{2}-(A+F)=\frac{b^2}{2}-2\frac{b^2}{6}=\frac{b^2}{6}. \] By symmetry, the area of this strip is also equal to the areas of segments $B$ and $E$. Line $l_2$, shown in green has equation \[ l_2: \quad y=-x+b_2. \] It intersects diagonal $y=x$ at $x=b_2/2$; therefore the area of segment $C$ is \[ C=\int_{\frac{b_2}{2}}^b x dx - \int_{\frac{b_2}{2}}^b (-x+b_2) d = \int_{\frac{b_2}{2}}^b(2x-b_2)dx=b^2+\frac{b_2^2}{4}-b_2b. \] Since $C=b^2/6$ we must have \[ b^2+\frac{b_2^2}{4}-b_2b=\frac{b^2}{6} \] which gives the following quadratic equation for $b_2$: \[ \frac{b_2^2}{4}-bb_2+\frac{5b^2}{6}=0. \] This has the following two solutions \[ b_2 = \frac{b \pm \sqrt{b^2-\frac{5b^2}{6}}}{2 \frac{1}{4}}=b \qty(2\pm\sqrt{\frac{2}{3}}). \] Given $b_2$, $l_2$ intersects $y=b$ at $b_2-b$; if $b_2=2b+b\sqrt{\frac{2}{3}}$ then $x=b+b\sqrt{\frac{2}{3}}$ which lies outside the rectangle. Therefore we must have $b_2=b \qty(2-\sqrt{\frac{2}{3}})$ in which case $l_2$ intercepts $y=b$ at $x=b(1-\sqrt{\frac{2}{3}})$. $l_2$ intercepts $x=b$ at $y=b(1-\sqrt{\frac{2}{3}})$.

15. Does 30 divide $n^5-n$ for all positive integers $n$?

Note that \[ n^5-n=n(n^4-1)=n(n^2+1)(n^2-1)=n(n^2+1)(n+1)(n-1). \] Integers $n-1,n,n+1$ are consecutive; lets assume that none of these numbers is divisible by 5. Examples are $(11,12,13)$, $(12,13,14)$, $(16,17,18)$ or $(17,18,19)$; note that for these cases $n^2+1=145,170,190,325$ which are all divisible by 5. The key here is that in order for none of the numbers in the sequence to be divisible by 5, $n$ must have a last digit equal to 2,3,7 or 8. Since \[ \mod{2^2+1}{10}=\mod{3^2+1}{10}=\mod{7^2+1}{10}=\mod{8^2+1}{10}=0 \] $n^2+1$ will be divisible by 5 if none of the three integers $n-1,n,n+1$ is divisible by 5.

2 will divide at least one of the integers $n-1,n,n+1$; now assume none of these three integers is divisible by 3. This means $n-1=3a+b$, $n=3c+d$ and $n+1=3e+f$; by definition $0<b,d,f<3$. Then we have $n=3a+b+1$ and so $d=b+1$; but we must also have $d=f-1$. This means that $f=b+2$; this is not possible since even when $b=1$ (the smallest possible value if we assume $n-1$ is not divisible by 3) then $f=3$ which is not possible (we have assumed that $n+1$ is not divisible by 3). We have reached a contradiction and so at least one of the integers $n-1,n,n+1$ will be divisible by 3. Hence we conclude that $n^5-n$ is divisible by 30 for all $n\geq 0$.

16. Dividing $x$ by a small annual $r$-percent cumulative interest rate approximates the number of years needed to double your investment with a bank. Find $x$. Hint: The definition from 7 may come in handy, and the keyword “small” may be important.

The assertion is that $x/r\approx N$ where $N$ is the number of years needed to double an investment. Note that with annual compounding the value of one dollar invested after $N$ years is $(1+r)^N$ so doubling an investment is equivalent to $(1+r)^N=2$. Following the hint we take the log of both sides: \[ N \ln (1+r)= \ln 2. \] The Taylor expansion of $\ln(1+r)$ is \[ \ln (1+r)=r-\frac{r^2}{2}+\frac{r^3}{3}-\cdots \] and if $r$ is sufficiently small we can write $\ln(1+r)\approx r$; using this approximation we have \[ Nr \approx \ln 2 \Rightarrow N \approx \frac{\ln 2}{r}. \] Therefore $x=\ln 2$.

17. Given a sequence of zeros and ones of length $n$, let $L_n$ be the number of sequences that have no adjacent zeros. Give a recursive formula for $L_n$.

We take as given that we have constructed sequences of $n$ digits and in none of these $L_n$ sequences we have adjacent zeros (admissible sequences). $L_n (1)$ of these admissible sequences start with a 1 and $L_n (0)$ start with a zero.

We are now going to construct admissible sequences of length $n+1$; the strategy we follow is straightforward. If we are given a sequence like \[ \underbrace{ \begin{array}{|c|c|c|c|} \hline \textbf{1} & d_1 & \cdots & d_{n-1} \\ \hline \end{array}}_{\text{$n$ digits}} \] we can add a 1 or 0 to the left. In both cases we obtain an admissible sequence. However, if we are given a sequence like \[ \underbrace{ \begin{array}{|c|c|c|c|} \hline \textbf{0} & d_1 & \cdots & d_{n-1} \\ \hline \end{array}}_{\text{$n$ digits}} \] we can only add a 1 to the left. This means that \[ L_{n+1}(0)=L_n(1) \] while \[ L_{n+1}(1)=L_n. \tag{A} \] Since $L_{n+1}=L_{n+1}(0)+L_{n+1}(1)$ we have \[ L_{n+1}=L_n(1)+L_n. \] Note that in $(\text{A})$ we have written that $L_{n+1}(1)=L_n$; it is also the case that $L_n(1)=L_{n-1}$; therefore we can rewrite the last equation as \[ L_{n+1}=L_{n-1}+L_n \] or \[ L_n = L_{n-2}+L_{n-1}. \]

18. You travel on Earth’s surface south $n$ miles, then east $n$ miles, then north $n$ miles and find yourself back where you started, without visiting any point more than twice. What is the closest you could have been to the south pole when you started? Assume Earth is a sphere with radius $R > n$.

First a quick review of spherical coordinates. As we can see from the diagram any point on a sphere with radius $R$ has $z$-coordinate equal to $R\cos\phi$. The dashed green line is a line of constant latitude. As we go north or south of the equator (the circle shown in a dashed black line) the circles of constant latitude get progressively smaller reaching a point at the north and south pole. In terms of the angle $\phi$, we reach the equator when $\phi=90^\circ$ and we are at the north (resp. south) pole when $\phi=0^\circ$ (resp. $180^\circ$).

The dashed blue line is a line of constant longitude. All longitudinal lines are great circles, meaning circles of radius $R$. Going south from a point, means that we follow a line of constant $\theta$ while increasing $\phi$. Going east means that we keep $\phi$ constant while we increase $\theta$.

Lets say we have started at a point below the equator; we move south $n$ miles. We reach a latitude where the radius is $r$; we want this circle to have a circumference equal to $n$ so that travelling this distance is a round trip. Then going north $n$ miles brings us back where we started. For a latitude to have this property \[ 2\pi r = n \Rightarrow 2\pi R\sin \phi = n \Rightarrow \sin\phi = \frac{n}{2\pi R} \Rightarrow \phi=\arcsin \qty(\frac{n}{2\pi R}). \]

Since $\sin(\pi - a)=\sin a$, this value of $\phi$ can also be used to tell us how far north of the south pole we are. So if we add the distance we travelled to get to this latitude, then we are \[ R\arcsin \qty(\frac{n}{2\pi R})+n \] miles north of the south pole.

If we start at a latitude given by $\phi$ we can find how far south we can move in terms of an angle $\nu$ so that \[ 2\pi \sin(\phi+\nu)=\nu, \] i.e. the round trip at a latitude $\phi+\nu$ ($2\pi R \sin(\phi+\nu)$) is equal to the trip south ($R \nu$). The graph below shows (black lines) \[ f(\nu)=2\pi \sin(\phi+\nu)-\nu \] as a function of $\nu$ for values of $\phi=0^\circ,10^\circ,\ldots,180^\circ$; the red line shows $\nu^*$, the solution of $f(\nu)=0$ for different values of $\phi$.

19. Let $f$ be the recursive function \begin{align*} f(n) & =f(n-1)-1 & \text{if $n$ is divisible by 2 or 3} \\ f(n) & = f(n-2)+2 & \text{otherwise} \\ \end{align*} with $f(1)=f(0)=0$. What is the value of $f(1337)$?

Although the recursive relation uses this mysterious function, all conditions are a function of $n$. If we express all integers modulo 6 then $n$ is not divisible by 2 or 3 if $\mod{n}{6}=1$ or $5$. If we started with such an integer we would obtain the following sequence of operations: \[ \def\red#1{\color{red}{#1}} \begin{array}{|c|c|c|c|} \hline {\tiny -2} & +1 & {\tiny -2} & +5 \\ \hline {\tiny -2} & -1 & {\tiny -1} & \red{+3} \\ \hline {\tiny -1} & \red{-3} & {\tiny -1} & \red{+2} \\ \hline {\tiny -1} & \red{-4} & {\tiny -2} & {+1} \\ \hline {\tiny -2} & {-5} & {\tiny -2} & {-1} \\ \hline {\tiny -2} & {-1} & {\tiny -1} & \red{-3} \\ \hline {\tiny -1} & \red{-3} & {\tiny -1} & \red{-4} \\ \hline {\tiny -1} & \red{-4} & {\tiny -2} & {-5} \\ \hline \end{array} \] (remember that all operations are expressed modulo 6 and so $-5-2$ is written as $-1$). So even for the case when we start with a number $n$ with $\mod{n}{6}=5$ we soon settle into a cycle where (modulo 6) $n=-1,-3,-4,-5$.

Which part of the cycle are we starting with 1337? $\mod{1337}{6}=5$ so the last column is relevant. The first action is to change $n$ by $-2$; we then add $-1$, $-1$ and $-2$. So at the end of the cycle we have reduced $n$ by 6. Conveniently since $\mod{1337}{6}=5$ we can repeat this until we reach $f(5)$. There we can write \[ f(5)=f(3)+2=f(2)-1+2=f(1)-1-1+2=0. \] While we adjust $n$ we must not forget the numbers we add or subtract to $f$. For the sequence $-2,-1,-1,-2$ we apply to $n$, we apply $2,-1,-1,2$ to $f$. Before reaching $f(5)$ we have repeated this cycle $(1337-5)/6=1332/6=222$ times adding $222\times2=444$. Therefore \[ f(1337)=f(5)+444=444. \]

20. Evaluate \[ \lim_{n \to \infty} \qty(\frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n}). \]

First a check whether such a limit exists; for $m=1,\ldots,n$ \[ \frac{1}{n+m} \geq \frac{1}{n+n}. \] Therefore, \[ \frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n} \geq \frac{1}{n+n} + \frac{1}{n+n} + \cdots + \frac{1}{n+n} = \frac{n}{n+n} = \frac{1}{2}. \] It is also the case that \[ \frac{1}{n+m} \leq \frac{1}{n+1} \] and so \[ \frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n} \leq \frac{1}{n+1} + \frac{1}{n+1} + \cdots + \frac{1}{n+1} = \frac{n}{n+1} . \] Since \[ \frac{1}{2}\leq \frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n} \leq \frac{n}{n+1} \] we have \[ \lim_{n \to \infty} \frac{1}{2}\leq \lim_{n \to \infty}\qty( \frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n} )\leq \lim_{n \to \infty} \frac{n}{n+1}. \] This can be simplified to \[ \frac{1}{2}\leq \lim_{n \to \infty} \qty(\frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n}) \leq 1 \] so the limit is finite and somewhere in this interval.

Next lets make a trivial change by writing \[ \frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n} \] as \[ \frac{n}{n+1}\frac{1}{n}+\frac{n}{n+2}\frac{1}{n}+ \cdots + \frac{n}{n+n}\frac{1}{n}. \] Another way of writing this last expression is as \[ \frac{1}{1+\frac{1}{n}}\frac{1}{n}+\frac{1}{1+2\frac{1}{n}}\frac{1}{n}+ \cdots + \frac{1}{1+n\frac{1}{n}}\frac{1}{n} = \sum_{k=1}^n \frac{1}{1+k\frac{1}{n}}\frac{1}{n}. \] If we are given the function $f(x)=\frac{1}{1+x}$ we can approximate $\int_0^1f(x)dx$ by dividing the $[0,1]$ interval into $n$ segments of width $1/n$ and writing \[ \int_0^1f(x)dx \approx \sum_{k=1}^n f(x_k) \frac{1}{n} \] where $x_k=k/n$. Note that \[ \sum_{k=1}^n f(x_k) \frac{1}{n} = \sum_{k=1}^n \frac{1}{1+k\frac{1}{n}} \frac{1}{n} \] which is identical to \[ \frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n}. \] From the definition of an integral \[ \int_0^1f(x)dx =\lim_{n\to \infty} \sum_{k=1}^n f(x_k) \frac{1}{n} . \] Since \[ \int_0^1\frac{1}{1+x}dx = \lim_{n\to \infty} \sum_{k=1}^n \frac{1}{1+k\frac{1}{n}} \frac{1}{n} = \lim_{n \to \infty} \qty(\frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n}) \] and \[ \int_0^1\frac{1}{1+x}dx = \eval{\ln(1+x)}_0^1=\ln 2 \] we conclude that \[ \lim_{n \to \infty} \qty(\frac{1}{n+1}+\frac{1}{n+2}+ \cdots + \frac{1}{n+n}) = \ln 2. \] Note that since $e=2.71828\ldots$ \[ e^{\frac{1}{2}} < 4^{\frac{1}{2}}=2 < e ; \] therefore \[ \ln e^{\frac{1}{2}} < \ln 2 < \ln e \iff \frac{1}{2} < \ln 2 < 1 \] as required.