BWM Runde 1 Mock Paper 2: Questions, Hints and Solutions

A positive term gives a positive numerator and denominator for the next term. Induction therefore shows that every term exists and is positive.

The number 1 is unchanged by the recurrence. Measuring each term relative to 1 in a suitable ratio removes the fraction:

$$\begin{aligned}\frac{a_{n+1}-1}{a_{n+1}+1}&=\frac{(a_n-1)/(a_n+2)}{3(a_n+1)/(a_n+2)}\\&=\frac13\frac{a_n-1}{a_n+1}.\end{aligned}$$

Repeatedly applying this equality gives

$$\frac{a_n-1}{a_n+1}=\frac{x-1}{3^{n-1}(x+1)}.$$

Solving for $a_n$ yields

$$a_n=\frac{3^{n-1}(x+1)+x-1}{3^{n-1}(x+1)-x+1}.$$

The denominator is positive because $|x-1|<x+1$ and $3^{n-1}\ge1$. This formula also gives $a_1=x$.

For the direction of change, the recurrence itself gives

$$\begin{gathered}a_{n+1}-1=\frac{a_n-1}{a_n+2},\\ a_{n+1}-a_n=\frac{1-a_n^2}{a_n+2}.\end{gathered}$$

The first equality preserves which side of 1 the term lies on. The second is negative above 1, positive between 0 and 1, and zero at 1. These facts prove all three claims.

Conclusion: $a_n=\dfrac{3^{n-1}(x+1)+x-1}{3^{n-1}(x+1)-x+1}$, with the stated strict monotonicity unless $x=1$.

Review the idea: Recursive sequences · First order linear recurrences

If $m$ is divisible by 2 or 5, each multiple of $m$ is also divisible by that prime. A number ending in 7 is divisible by neither, so the stated coprimality is necessary.

Conversely, suppose $\gcd(m,10)=1$. Let $R_j$ be the number consisting of $j$ sevens, and put $R_0=0$. The $m+1$ numbers $R_0,R_1,\ldots,R_m$ have only $m$ possible remainders modulo $m$. Hence $R_i\equiv R_j\pmod m$ for some $0\le j<i\le m$. Their difference is

$$R_i-R_j=10^jR_{i-j}.$$

Since $10^j$ is coprime to $m$, divisibility of this product by $m$ implies $m\mid R_{i-j}$. To justify this cancellation, Bézout’s identity provides integers $u,v$ with $u10^j+vm=1$; multiply by $R_{i-j}$. Both terms on the left are divisible by $m$.

The number $R_{i-j}$ is positive, consists entirely of sevens, and has between 1 and $m$ digits. The argument includes $m=1$.

Conclusion: Such a multiple exists exactly when $\gcd(m,10)=1$; at most $m$ digits suffice.

Review the idea: Pigeonhole principle · Greatest common divisor · Number bases and digit problems

There is one tiling of the empty board and one of a $2\times1$ board, so $T_0=T_1=1$. For $n\ge2$, a tiling begins in one of two ways.

• If the top-left cell belongs to a vertical domino, that domino fills the first column. The rest can be tiled in $T_{n-1}$ ways.
• If it belongs to a horizontal domino, the bottom-left cell must also belong to a horizontal domino: it cannot go left or vertically into the occupied top-left cell. These two dominoes fill the first two columns, leaving $T_{n-2}$ choices.

The cases are disjoint and exhaustive, so $T_n=T_{n-1}+T_{n-2}$. Consequently, for every $n\ge0$,

$$T_{n+3}=T_{n+2}+T_{n+1}=2T_{n+1}+T_n.$$

Thus $T_{n+3}$ and $T_n$ have the same parity. The first three terms have parities $1,1,0$, because $T_2=2$. Repeatedly subtracting 3 from an index reduces it to 0, 1, or 2 without changing parity. This proves the claim for every nonnegative $n$.

Conclusion: $T_n$ is odd precisely for $n\equiv0,1\pmod3$.

Review the idea: Counting with recurrences · Parity

A rotation preserves lengths and angles. Rotate through $90^\circ$ about $A$ in the direction taking $B$ to $D$, and call the image of $E$ point $E^\prime$. Because $BE$ is perpendicular to $AB$, its image is perpendicular to $AD$ and extends from $D$ away from $C$. Thus $E^\prime,D,F,C$ occur in that order on one line, and $DE^\prime=BE$.

The ray $AF$ lies between $AE$ and $AE^\prime$. The whole angle $EAE^\prime$ is $90^\circ$, so $\angle FAE^\prime=90^\circ-45^\circ=45^\circ=\angle EAF$. Also $AE=AE^\prime$ by rotation, and $AF$ is common. The side–angle–side congruence rule gives

$$EF=E^\prime F=E^\prime D+DF=BE+DF.$$

The extra point turns the required sum of two lengths into a single segment, which is why the rotation helps.

Conclusion: $EF=BE+DF$.

Review the idea: Triangle congruence · Angles