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

A constant $P=c$ would give $c^2=c^2-1$, impossible. Suppose first that $P$ has degree $n\ge2$, and write its three highest terms as

$$\begin{gathered}P(x)=cx^n+dx^{n-1}+ex^{n-2}+\text{terms of lower degree},\\ c\ne0.\end{gathered}$$

The binomial theorem gives the three highest coefficients of the shifts:

$$P(x\pm1)=cx^n+(d\pm nc)x^{n-1}+\left(e\pm(n-1)d+\frac{n(n-1)}2c\right)x^{n-2}+\cdots.$$

In the product of these shifts, the coefficients of $x^{2n}$ and $x^{2n-1}$ are $c^2$ and $2cd$, the same as in $P(x)^2$. The coefficient of $x^{2n-2}$ in the product is

$$c\left(2e+n(n-1)c\right)+(d+nc)(d-nc)=2ce+d^2-nc^2.$$

In $P(x)^2$, that coefficient is $2ce+d^2$. Thus their difference has nonzero leading coefficient $-nc^2$ and degree $2n-2\ge2$. It cannot equal the constant $-1$. Hence $P$ must have degree 1.

Write $P(x)=cx+d$. Direct multiplication gives

$$P(x+1)P(x-1)=(cx+d+c)(cx+d-c)=P(x)^2-c^2.$$

The required identity is therefore equivalent to $c^2=1$. Both signs work for every real $d$, so the full answer is $P(x)=x+d$ or $P(x)=-x+d$.

Conclusion: $P(x)=x+d$ or $P(x)=-x+d$, with arbitrary real $d$.

Review the idea: Binomial expansions and generating functions · Polynomial functions

Let $p$ be a prime divisor of $N$, and write $N=p^a m$, where $p\nmid m$. The numbers $x=1+mt$, for $t=0,\ldots,p-1$, run through every residue modulo $p$, because $m$ is invertible modulo $p$. Each is coprime to $m$. For every nonzero residue modulo $p$, the corresponding $x$ is also coprime to $p$, hence to $N$.

The assumption then says that all $p-1$ nonzero residues satisfy $x^2\equiv1\pmod p$. Since $p$ is prime, $p\mid(x-1)(x+1)$ forces $x\equiv1$ or $-1\pmod p$. There are at most two such residues, so $p-1\le2$, giving $p=2$ or 3.

Thus $N$ has no prime factors other than 2 and 3, so 5 is coprime to $N$. Applying the hypothesis to 5 gives $N\mid25-1=24$. This includes the possibility $N=1$, which has no prime divisors.

Conversely, let $N\mid24$, and let $x$ be coprime to $N$. If $N$ has a factor 2, then $x$ is odd. The consecutive even numbers $x-1,x+1$ include a multiple of 4, so $8\mid x^2-1$, enough for any power of 2 in $N$. If $3\mid N$, then $x\equiv\pm1\pmod3$, so $3\mid x^2-1$. The required factors 2 and 3 are coprime, so their product divides $x^2-1$. Therefore every divisor of 24 works; modulo 1 the assertion is automatic.

Conclusion: $N\in\{1,2,3,4,6,8,12,24\}$.

Review the idea: Complete and reduced residue systems · Unique prime factorisation

Use the following greedy construction. Among the intervals still uncovered, choose one with smallest right endpoint, call that endpoint $r$, and mark $r$. Remove every interval containing $r$, and repeat until no intervals remain. Finiteness ensures that the procedure stops.

Why are the intervals chosen at successive steps disjoint? At the moment $r$ is selected, every remaining interval has right endpoint at least $r$. If an interval does not contain $r$, its left endpoint must therefore be strictly greater than $r$. Thus all intervals remaining for later choices lie entirely to the right of the interval that supplied $r$. Repeating this argument proves pairwise disjointness of the chosen intervals.

Suppose the procedure chooses $k$ points. They cover every interval by construction, so $k$ points suffice. But the $k$ chosen intervals are pairwise disjoint, so no one point can cover two of them. Any covering therefore needs at least $k$ points. The minimum covering number is exactly $k$.

Moreover, any pairwise disjoint family contains at most $k$ intervals, because the constructed $k$-point cover must supply a different point for each member. The chosen intervals already give a disjoint family of size $k$. Hence the maximum disjoint-family size is also $k$, proving the equality.

Conclusion: The two optimum numbers are equal; choosing successive smallest right endpoints constructs both witnesses.

Review the idea: Proof methods · Counting with bijections

We will obtain the desired circle by halving a known circle about $H$. Map each point $T$ to the midpoint of $HT$. By the midpoint theorem, the distance between the images of two points is half their original distance. The image of $O$ is $K$, so the image of its circle of radius $R$ is a circle of centre $K$ and radius $R/2$. It remains to place the six points on that image.

The altitude feet. Reflect $H$ in line $BC$, calling the image $H_a$. Since $AH\perp BC$, the midpoint of $HH_a$ is $D$. We show that $H_a$ is on the circumcircle.

In an acute triangle $H$ lies inside. In quadrilateral $AEHF$, the angles at $E,F$ are right angles, so $\angle EHF=180^\circ-\angle BAC$. The rays $HB,HC$ are opposite to $HE,HF$, respectively, giving $\angle BHC=180^\circ-\angle BAC$. Reflection fixes $B,C$, so the angle $BH_aC$ has this same value. As $H_a$ lies on the opposite side of $BC$ from $A$, the opposite angles of quadrilateral $ABH_aC$ add to $180^\circ$. The cyclic-quadrilateral criterion puts $H_a$ on the circumcircle. Its midpoint image is $D$, as required. Reflecting $H$ in $CA$ and $AB$ uses exactly the same argument with the vertex names cycled; their midpoint images are $E,F$.

The side midpoints. Let $A^\prime$ be the other end of the diameter starting at $A$. An angle subtending a diameter is right, so $CA^\prime\perp AC$ and $BA^\prime\perp AB$. The altitudes give $BH\perp AC$ and $CH\perp AB$. Hence $BH\parallel CA^\prime$ and $CH\parallel BA^\prime$. The quadrilateral $BHCA^\prime$ is a parallelogram, whose diagonals $BC$ and $HA^\prime$ bisect each other. Thus their common midpoint $M$ is the midpoint of $HA^\prime$, the image of the circumcircle point $A^\prime$. The opposite ends of the diameters from $B,C$ have images $N,P$.

All six points therefore lie on the image circle, with precisely the stated centre and radius.

Conclusion: $D,E,F,M,N,P$ lie on the circle of centre $K=(O+H)/2$ and radius $R/2$.

Review the idea: The midpoint theorem · Cyclic and tangential quadrilaterals · Concurrency and collinearity