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

Every generated pair works. Sign changes preserve the squares. Direct expansion shows

$$(xP+(x^2-1)Q)^2-(x^2-1)(P+xQ)^2=P^2-(x^2-1)Q^2.$$

Since $(1,0)$ satisfies the identity, so does every generated pair.

Reduce an arbitrary solution. If $Q=0$, then $P^2=1$, so $P=1$ or $-1$; these are already allowed. Otherwise let $Q$ have degree $m\ge0$ and leading coefficient $q\ne0$. Cancellation of the highest terms in the identity forces $P$ to have degree $m+1$ and leading coefficient $q$ or $-q$. If necessary change the sign of $P$, so the leading coefficients agree.

For $m\ge1$, write the two highest coefficients as $Q=qx^m+dx^{m-1}+\cdots$ and $P=qx^{m+1}+bx^m+\cdots$. The coefficient of $x^{2m+1}$ in $P^2-(x^2-1)Q^2$ is $2q(b-d)$, which must be zero. Hence $b=d$. For $m=0$, write $Q=q$, $P=qx+b$. The coefficient of $x$ is $2qb$, so $b=0$.

Now define

$$\begin{gathered}P^\prime=xP-(x^2-1)Q,\\ Q^\prime=xQ-P.\end{gathered}$$

Expansion, with the same cancellation as before, gives $(P^\prime)^2-(x^2-1)(Q^\prime)^2=1$. If $m\ge1$, the coefficients of $x^{m+1}$ and $x^m$ cancel in $Q^\prime$, so its degree is at most $m-1$, unless it is zero. For $m=0$, the calculation $b=0$ gives $Q^\prime=0$. Thus each reduction strictly lowers the nonnegative degree of $Q$, until $Q=0$.

Reverse the reductions. Direct substitution gives

$$\begin{gathered}xP^\prime+(x^2-1)Q^\prime=P,\\ P^\prime+xQ^\prime=Q.\end{gathered}$$

So each reduction is reversed by the permitted second operation. Any sign changes used along the way are also permitted and reversible. Reversing the finite sequence, and choosing the base sign of $P$, generates the original pair from $(1,0)$. This proves completeness, not just a list of examples.

Conclusion: Exactly the pairs generated by the two stated operations; the degree descent proves that none are omitted.

Review the idea: Polynomial functions · Algebraic identities · Proof methods

Every pair $a=b$ works. The equation is symmetric, so suppose $a<b$; reversed unequal pairs can be added at the end. If $a=1$, the equation would give $b=1$, a contradiction. Hence $a\ge2$.

Write $a=gu,b=gv$, where $g=\gcd(a,b)$, $u<v$, and $u,v$ are coprime. Taking the positive $g$-th root of the original equation gives $a^v=b^u$.

For any prime, let $\alpha,\beta$ be its exponents in $a,b$. Then $v\alpha=u\beta$. Coprimality forces $\alpha=ut$, $\beta=vt$ for a nonnegative integer $t$. Doing this for every prime gives one integer $c\ge2$ such that $a=c^u$, $b=c^v$.

On the other hand, $b/a=v/u$. Therefore

$$c^{v-u}=\frac vu.$$

The left side is an integer. Thus $u\mid v$; since $u,v$ are coprime, $u=1$. The last equation becomes $v=c^{v-1}$. If $v\ge3$, then $c^{v-1}\ge2^{v-1}>v$: the strict inequality holds at $v=3$, and doubling a number greater than $v$ makes it greater than $v+1$. This is impossible. Hence $v=2$, and then $c=2$.

Thus $a=2,b=4$ in the ordered case $a<b$. Directly $2^4=4^2=16$. The full list is all equal pairs and the two unequal pairs $(2,4),(4,2)$.

Conclusion: All $(a,a)$ with $a\ge1$, together with $(2,4)$ and $(4,2)$.

Review the idea: Unique prime factorisation · Greatest common divisor

For position $i$, let $I_i$ be the largest length of an increasing subsequence ending at that position, and let $D_i$ be the corresponding decreasing length. These maxima exist because the sequence is finite, and each is at least 1.

Suppose neither desired subsequence exists. Then

$$\begin{gathered}1\le I_i\le r-1,\\1\le D_i\le s-1.\end{gathered}$$

There are only $(r-1)(s-1)$ possible ordered pairs $(I_i,D_i)$. Yet pairs at different positions are distinct. To see why, take $i<j$. If the term at $i$ is smaller than that at $j$, append the latter to a longest increasing subsequence ending at $i$; hence $I_j\ge I_i+1$. If it is larger, the same argument for a decreasing subsequence gives $D_j\ge D_i+1$. Equality of terms is excluded by the hypothesis. In either case the pairs differ.

The given number of positions exceeds the number of available pairs, contradicting the pigeonhole principle. This proves the guarantee.

Sharpness. Use $r-1$ consecutive blocks, each of length $s-1$. Within each block list its entries in decreasing order, while all entries in a later block are larger than all entries in an earlier one. For example, the first two blocks are

$$\begin{gathered}s-1,s-2,\ldots,1;\\2(s-1),2(s-1)-1,\ldots,s.\end{gathered}$$

Continue with the next unused integers for each block. An increasing subsequence uses at most one entry from each block, so has length at most $r-1$. A decreasing subsequence cannot move to a later block, where every entry is larger, so it stays in one block and has length at most $s-1$. This sequence has $(r-1)(s-1)$ terms and avoids both targets, proving optimality.

Conclusion: The sharp sufficient length is $(r-1)(s-1)+1$.

Review the idea: Pigeonhole principle · Sequences and sums

For a point inside a circle, the chord form of power of a point says that the product of the distances to the two chord endpoints is $R^2$ minus the square of the distance to the centre. Applying this along the three sides gives

$$OD^2=OE^2=OF^2=R^2-k.$$

Thus the three points lie on a circle centred at $O$, provided the radius is positive. On a side of length $l$, write the distances as $t,l-t$, with $0<t<l$. Then

$$k=t(l-t)=\frac{l^2}{4}-\left(t-\frac l2\right)^2\le\frac{l^2}{4}.$$

Let $l_0$ be the shortest side. We must have $k\le l_0^2/4$. Also $l_0<2R$: every side is a chord of length at most the diameter, and the shortest of three distinct sides cannot itself be a diameter. Hence $R^2-k>0$.

The points $D,E,F$ are not collinear. A line not equal to a side meets the boundary of a convex triangle at at most two points; a line equal to one side cannot contain points strictly inside both other sides. Thus their circumcircle is uniquely determined and has centre $O$ and radius $\sqrt{R^2-k}$.

Attainment and counting. The quadratic $t(l-t)=k$ has two distinct roots strictly between 0 and $l$ when $0<k<l^2/4$; one root, the midpoint, when $k=l^2/4$; and none when $k>l^2/4$. The choices on the three sides are independent.

Therefore the largest possible value is $k=l_0^2/4$. The shortest side is unique, so it contributes one point, and each longer side contributes two. This gives $1\cdot2\cdot2=4$ ordered triples. At any fixed $0<k<l_0^2/4$, all three sides contribute two choices, giving $2^3=8$ triples. Each counted triple meets the product condition, so these counts are attained.

Conclusion: Radius $\sqrt{R^2-k}$; maximum $k=l_0^2/4$, where $l_0$ is the shortest side. There are 4 triples at the maximum and 8 at each smaller positive value.

Review the idea: Circles and power of a point · Equations and quadratics · Counting