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

Reduce to the first block. Applying the equation at $f(n)$ and also applying $f$ to the equation at $n$ gives

$$f(f(f(n)))=f(n)+k=f(n+k).$$

Consequently $f(i+qk)=f(i)+qk$ for $1\le i\le k$ and every nonnegative integer $q$. Every positive integer has a unique such form.

Let $\pi(i)$ be the representative in $\{1,\ldots,k\}$ of the residue of $f(i)$ modulo $k$. Positivity permits writing $f(i)=\pi(i)+t_i k$, with $t_i\ge0$. The composition condition modulo $k$ says $\pi(\pi(i))=i$. Thus $\pi$ is a permutation consisting of fixed points or pairs.

A fixed point is impossible: if $f(i)=i+tk$, the shift rule gives $f(f(i))=i+2tk$, which cannot equal $i+k$ for integer $t$. Therefore the $k$ residue classes must split into disjoint pairs, so $k$ must be even.

Describe every allowed pair. For a pair $i,j$, write $f(i)=j+tk$ and $f(j)=i+sk$, with $s,t\ge0$. Then $f(f(i))=i+(s+t)k$, so $s+t=1$. Exactly two choices remain:

$$(f(i),f(j))=(j,i+k)\quad\text{or}\quad(j+k,i).$$

Conversely, choose any pairing, choose either of these two orientations for each pair, and extend by $f(i+qk)=f(i)+qk$. All values are positive, and direct substitution gives $f(f(i+qk))=i+(q+1)k$. Hence every construction works.

Count. For even $k=2m$, there are $k!/(2^m m!)$ pairings: arrange the labels, group consecutive labels in pairs, then divide by the two orders within each pair and by the $m!$ orders of the pairs. Each pair has two independent orientations. Thus the total is $k!/m!$. Different choices change the first $k$ values, so they give different functions. For odd $k$, there are none.

Conclusion: For odd $k$, none. For even $k=2m$, pair the residue classes and orient each pair as described; there are $k!/m!$ functions.

Review the idea: Functions inverses and composition · Complete and reduced residue systems · Dividing objects into fixed size groups

Because $a,b$ are coprime, the numbers $ax$, for $x=0,\ldots,b-1$, give distinct remainders modulo $b$. Equal remainders would imply $b\mid a(x_1-x_2)$, hence $b\mid x_1-x_2$, forcing equality in this range. Thus some $x$ in that range has $ax\equiv N\pmod b$.

For that $x$, the integer $N-ax$ is a multiple of $b$, and

$$N-ax\ge(a-1)(b-1)-a(b-1)=1-b>-b.$$

The negative multiple of $b$ closest to zero is $-b$; every other negative multiple is even smaller. Hence $N-ax\ge0$, so $y=(N-ax)/b$ is a nonnegative integer. This constructs the required representation.

Now suppose $ab-a-b=ax+by$ with $x,y\ge0$. Rearranging gives

$$a(x+1)+b(y+1)=ab.$$

Reduction modulo $b$ and coprimality imply $b\mid x+1$. Since $x+1$ is positive, $x+1\ge b$, so the first term on the left is at least $ab$. The second term is strictly positive, contradicting the equality. Thus the stated bound cannot be lowered by 1.

Conclusion: Every $N\ge ab-a-b+1$ is representable; $ab-a-b$ is not.

Review the idea: Greatest common divisor · Complete and reduced residue systems

Let $S$ be the sum of all entries in the current array. If a selected row or column has sum $t<0$, flipping it changes that line’s contribution from $t$ to $-t$, while all other entries stay unchanged. Hence the new total is $S-2t>S$. Every permitted move strictly increases the total.

Despite the entries being arbitrary real numbers, there are only finitely many configurations. An entry is multiplied by $-1$ each time its row or its column is flipped. Its final sign therefore depends only on whether the number of flips of that row and column is even or odd. There are at most $2^{m+n}$ choices of these parities, so at most that many resulting arrays.

A process with strictly increasing total can never revisit an array. Including the starting array, it visits at most $2^{m+n}$ different arrays, so it makes at most $2^{m+n}-1$ moves. When it stops, no negative-sum row or column is left, since otherwise another permitted move would exist. The bound works regardless of which negative line is chosen at each step, and it proves the requested existence as well.

Conclusion: Flipping any negative-sum line always terminates within $2^{m+n}-1$ moves, with all line sums nonnegative.

Review the idea: Parity · Proof methods

We introduce coordinate arrows only to keep track of the four quarter-turns. Write each point as its coordinate pair. Pairs are added and subtracted component by component; for example, $B-A$ is the arrow from $A$ to $B$. Define

$$J(u,v)=(-v,u).$$

This turns an arrow $90^\circ$ counterclockwise. It preserves its length, and $J(J(u,v))=-(u,v)$. Also $J(U+V)=J(U)+J(V)$, by checking the two coordinates.

For a counterclockwise quadrilateral, the outside of each directed side is to its right. The centre of the square on $AB$ is its midpoint plus half the clockwise-turned side arrow. Therefore

$$2P=A+B-J(B-A).$$

The same rule gives

$$\begin{gathered}2Q=B+C-J(C-B),\\ 2R=C+D-J(D-C),\\ 2S=D+A-J(A-D).\end{gathered}$$

Set $U=C-A$ and $V=D-B$. Subtracting the formulas and using the componentwise rules yields

$$2(R-P)=U+V+J(U)-J(V),$$$$2(S-Q)=V-U+J(U)+J(V).$$

Applying $J$ to the first right-hand side gives $J(U)+J(V)-U+V$, exactly the second right-hand side. Thus $S-Q=J(R-P)$: the second segment’s arrow is a quarter-turn of the first. Since $P\ne R$, both arrows are nonzero. A quarter-turn preserves their lengths and makes them perpendicular, proving both claims.

Conclusion: $PR=QS$ and the two nonzero segments are perpendicular.

Review the idea: Quadrilaterals and their diagonals · Pythagoras and stewart