MathNet 1977 — Part 01

If $f(x) = x^{2} + x$, prove that the equation $4 f(a) = f(b)$ has no solutions in positive integers $a$ and $b$.

Let
$$
p(x) = a_{n} x^{n} + a_{n-1} x^{n-1} + \cdots + a_{1} x + a_{0}
$$
and
$$
q(x) = b_{m} x^{m} + b_{m-1} x^{m-1} + \cdots + b_{1} x + b_{0}
$$
be two polynomials with integer coefficients. Suppose that all the coefficients of the product $p(x) \cdot q(x)$ are even but not all of them are divisible by $4$. Show that one of $p(x)$ and $q(x)$ has all even coefficients and the other has at least one odd coefficient.

$N$ is an integer whose representation in base $b$ is $777$. Find the smallest positive integer $b$ for which $N$ is the fourth power of an integer.

A rectangular city is exactly $m$ blocks long and $n$ blocks wide (see diagram). A woman lives in the southwest corner of the city and works in the northeast corner. She walks to work each day but, on any given trip, she makes sure that her path does not include any intersection twice. Show that the number $f(m, n)$ of different paths she can take to work satisfies $f(m, n) \leq 2^{m n}$.

A right circular cone of base radius $1$ cm and slant height $3$ cm is given. $P$ is a point on the circumference of the base and the shortest path from $P$ around the cone and back to $P$ is drawn (see diagram). What is the minimum distance from the vertex $V$ to this path?

Let $O$ be the centre of a circle and $A$ a fixed interior point of the circle different from $O$. Determine all points $P$ on the circumference of the circle such that the angle $OPA$ is a maximum.

Given 1000 square plates in the plane with their sides parallel to the coordinate axes (but possibly overlapping and possibly of different sizes). Let $S$ be the set of points covered by the plates. Show that you can choose a subset $T$ of plates such that every point of $S$ is covered by at least one and at most four plates in $T$.

Each vertex of a convex polyhedron has three edges. Each face is a cyclic polygon. Show that its vertices all lie on a sphere.

The positive integers $a_1$, $a_2$, ..., $a_m$, $b_1$, $b_2$, ..., $b_n$ satisfy: $a_1 + a_2 + \ldots + a_m = b_1 + b_2 + \ldots + b_n \lt mn$. Show that we can delete some (but not all) of the numbers so that the sum of the remaining $a$'s equals the sum of the remaining $b$'s.

Given a polynomial $x^{10} + a_9 x^9 + \ldots + a_1 x + 1$. Two players alternately choose one of the coefficients $a_1$ to $a_9$ (which has not been chosen before) and assign a real value to it. The first player wins iff the resulting polynomial has no real roots. Who wins?

Seven elves sit at a table. Each elf has a cup. In total the cups contain $3$ liters of milk. Each elf in turn gives all his milk to the others in equal shares. At the end of the process each elf has the same amount of milk as at the start. What was that?

$n$ points lie in the plane, not all on a single line. A real number is assigned to each point. The sum of the numbers is zero for all the points lying on any line. Show that all the assigned numbers must be zero.

There are direct routes between every two cities in a country. The fare between each pair of cities is the same in both directions. Two travellers decide to visit all the cities. The first traveller starts at a city and travels to the city with the most expensive fare (or if there are several such, any one of them). He then repeats this process, never visiting a city twice, until he has been to all the cities (so he ends up in a different city from the one he starts from). The second traveller has a similar plan, except that he always chooses the cheapest fare, and does not necessarily start at the same city. Show that the first traveller spends at least as much on fares as the second.

Given a sequence $a_1$, $a_2$, ..., $a_n$ of positive integers. Let $S$ be the set of all sums of one or more members of the sequence. Show that $S$ can be divided into $n$ subsets such that the smallest member of each subset is at least half the largest member.

You are given a set of scales and a set of $n$ different weights. $R$ represents the state in which the right pan is heavier, $L$ represents the state in which the left pan is heavier and $B$ represents the state in which the pans balance. Show that given any $n$-letter string of $R$s and $L$s you can put the weights onto the scales one at a time so that the string represents the successive states of the scales. For example, if the weights were $1$, $2$ and $3$ and the string was $LRL$, then you would place $1$ in the left pan, then $2$ in the right pan, then $3$ in the left pan.

(1) The triangle $ABC$ is inscribed in a circle. $D$ is the midpoint of the arc $BC$ (not containing $A$), similarly $E$ and $F$. Show that the hexagon formed by the intersection of $ABC$ and $DEF$ has its main diagonals parallel to the sides of $ABC$ and intersecting in a single point.

(2) $EF$ meets $AB$ at $X$ and $AC$ at $Y$. Prove that $AXIY$ is a rhombus, where $I$ is the center of the circle inscribed in $ABC$.

Given a $100 \times 100$ square divided into unit squares. Several paths are drawn. Each path is drawn along the sides of the unit squares. Each path has its endpoints on the sides of the big square, but does not contain any other points which are vertices of unit squares and lie on the big square sides. No path intersects itself or any other path. Show that there is a vertex apart from the four corners of the big square that is not on any path.

A polynomial is monic if its leading coefficient is $1$. Two polynomials $p(x)$ and $q(x)$ commute if $p(q(x)) = q(p(x))$.

(1) Find all monic polynomials of degree $3$ or less which commute with $x^2 - k$.

(2) Given a monic polynomial $p(x)$, show that there is at most one monic polynomial of degree $n$ which commutes with $p(x)^2$.

(3) Find the polynomials described in (2) for $n = 4$ and $n = 8$.

(4) If $q(x)$ and $r(x)$ are monic polynomials which both commute with $p(x)^2$, show that $q(x)$ and $r(x)$ commute.

(5) Show that there is a sequence of polynomials $p_2(x), p_3(x), \ldots$ such that $p_2(x) = x^2 - 2$, $p_n(x)$ has degree $n$ and all polynomials in the sequence commute.

$P$ is a polygon. Its sides do not intersect except at its vertices, and no three vertices lie on a line. The pair of sides $AB$, $PQ$ is called special if (1) $AB$ and $PQ$ do not share a vertex and (2) either the line $AB$ intersects the segment $PQ$ or the line $PQ$ intersects the segment $AB$. Show that the number of special pairs is even.

Black and white tokens are placed around a circle. First all the black tokens with one or two white neighbors are removed. Then all white tokens with one or two black neighbors are removed. Then all black tokens with one or two white neighbors and so on until all the tokens have the same color. Is it possible to arrange 40 tokens so that only one remains after 4 moves? What is the minimum possible number of moves to go from 1000 tokens to one?