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

The absence of positivity makes an inequality approach awkward. Instead we express all symmetric information through $q=xy+yz+zx$ and $r=xyz$. The factorisation

$$(t-x)(t-y)(t-z)=t^3-3t^2+qt-r$$

shows that each of $x,y,z$ satisfies $t^3=3t^2-qt+r$. Let $p_j=x^j+y^j+z^j$. We know $p_1=p_3=p_5=3$, and squaring the sum gives $p_2=9-2q$.

Sum the cubic relation at the three numbers:

$$p_3=3p_2-qp_1+3r.$$

Substituting yields $3=27-9q+3r$, hence $r=3q-8$. Next multiply the cubic relation by $t$ and by $t^2$, respectively, before summing. This gives

$$p_4=3p_3-qp_2+rp_1=9-q(9-2q)+3(3q-8)=2q^2-15,$$$$p_5=3p_4-qp_3+rp_2=3(2q^2-15)-3q+(3q-8)(9-2q)=40q-117.$$

Since $p_5=3$, we obtain $q=3$, then $r=1$. Thus

$$(t-x)(t-y)(t-z)=t^3-3t^2+3t-1=(t-1)^3.$$

Substituting $t=x,y,z$ in this equality shows that each is 1. Conversely, three ones satisfy all three equations, so the conclusion is both forced and possible.

Conclusion: $x=y=z=1$.

Review the idea: Symmetric polynomials · Algebraic identities · Polynomial functions

Choose $rL$ distinct primes and divide them into $L$ groups of $r$ primes. There are enough primes: if only finitely many existed, their product plus 1 would have a prime divisor outside the list. Let $Q_i$ be the product in group $i$, for $1\le i\le L$. These products are pairwise coprime because the groups share no prime.

We want $Q_i\mid N+i$ for every $i$. Here is an explicit simultaneous construction. Set

$$\begin{gathered}M=Q_1Q_2\cdots Q_L,\\ M_i=M/Q_i.\end{gathered}$$

Since $M_i$ and $Q_i$ are coprime, Bézout’s identity gives integers $u_i,v_i$ with $u_iM_i+v_iQ_i=1$. In particular $u_iM_i\equiv1\pmod{Q_i}$. Define

$$N_0=-\sum_{i=1}^L i\,u_iM_i.$$

Fix an index $j$. For each $i\ne j$, the number $M_i$ contains $Q_j$ as a factor, so that summand vanishes modulo $Q_j$. The remaining term is $-j u_jM_j\equiv-j\pmod{Q_j}$. Thus $Q_j\mid N_0+j$.

Choose an integer $t$ large enough that $N=N_0+tM\ge0$. Adding $tM$ preserves every congruence. Hence $N+1,\ldots,N+L$ are positive consecutive integers, and $N+i$ is divisible by the product $Q_i$ of $r$ distinct primes. This proves the claim with a construction valid for every $L,r$.

Conclusion: Choose pairwise disjoint groups of primes and solve $N\equiv-i\pmod{Q_i}$ by the explicit Bézout construction.

Review the idea: Greatest common divisor · Prime numbers · Remainders

Choose a tree inside the graph. Start with one vertex and repeatedly add an edge joining the vertices already reached to a new vertex. Such an edge exists until all vertices are reached, because the graph is connected. Each added edge introduces exactly one new vertex and cannot make a cycle. The result is a connected subgraph containing every vertex and exactly $v-1$ edges, called a spanning tree.

Select any subset of the $e-v+1$ edges outside this tree. There are $2^{e-v+1}$ possible choices. We prove that each has exactly one completion using tree edges that makes all selected degrees even.

Choose one tree vertex as the root. Each other vertex has a unique route to the root: two different routes would make a cycle. Its first edge on that route is its parent edge. Process vertices furthest from the root first, leaving the root until last. At a vertex being processed, all incident non-tree edges were already chosen, and every incident tree edge going away from the root has already been decided at a more distant vertex. Only its parent edge remains undecided.

If the number of currently selected incident edges is odd, select the parent edge; if it is even, leave that edge unselected. This is the unique decision that makes the current vertex’s degree even. Continuing reaches every vertex except the root.

The root automatically has even degree. Indeed, summing degrees over all vertices counts each selected edge twice, so the total is even. Every other vertex now has even degree, forcing the root’s degree even as well. This proves existence. The forced decision at each processed vertex also proves uniqueness.

Thus the freely chosen non-tree subsets correspond one-to-one with the allowed selections, giving the stated count. For $v=1$, a connected simple graph has $e=0$; the single empty selection agrees with $2^0=1$.

Conclusion: Exactly $2^{e-v+1}$ selections.

Review the idea: Parity · Counting with bijections · Proof methods

Use coordinates with $P=(0,0)$, the secant as horizontal axis, and $X=(x,0),Y=(y,0)$, where $0<x<y$. Here $x=PX,y=PY$.

A circle has an equation $u^2+v^2+du+kv+c=0$, obtained by expanding $(u-h)^2+(v-l)^2=R^2$. On the horizontal axis its two intersections are $x,y$, so its equation there is $(u-x)(u-y)=0$. Comparing coefficients gives the full circle equation

$$u^2+v^2-(x+y)u+kv+xy=0$$

for some real $k$.

The tangent–secant power theorem gives $PA^2=PB^2=PX\cdot PY=xy$. Thus at each tangent point, $u^2+v^2=xy$. Subtracting this relation from the circle equation shows that both $A,B$ lie on

$$(x+y)u-kv=2xy.$$

They are distinct, so this is exactly their joining line. Since $x+y>0$, it meets the horizontal axis at the unique point

$$Q=\left(\frac{2xy}{x+y},0\right).$$

Its position follows from the positive differences

$$\begin{gathered}PQ-x=\frac{x(y-x)}{x+y}>0,\\ y-PQ=\frac{y(y-x)}{x+y}>0.\end{gathered}$$

Hence $X,Q,Y$ occur in that order, and the required intersection is inside the segment. Dividing these differences gives

$$\frac{QX}{QY}=\frac{x(y-x)/(x+y)}{y(y-x)/(x+y)}=\frac xy=\frac{PX}{PY}.$$

The coordinate for $Q$ already gives the other required formula.

Conclusion: $X,Q,Y$ occur in this order, $PQ=2PX\cdot PY/(PX+PY)$, and $QX/QY=PX/PY$.

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