SIMON-MARAIS 2020

There are 1001 points in the plane such that no three are collinear. The points are joined by 1001 line segments such that each point is an endpoint of exactly two of the line segments.

Prove that there does not exist a straight line in the plane that intersects each of the 1001 line segments in an interior point.

An interior point of a line segment is a point of the line segment that is not one of the two endpoints.

Fiona has a deck of cards labelled 1 to $n$, laid out in a row on the table in order from 1 to $n$ from left to right. Her goal is to arrange them into a single pile, through a series of steps of the following form:

If at some stage the cards are in $m$ piles, she chooses $1 \leq k < m$ and arranges the cards into $k$ piles by picking up pile $k+1$ and putting it on pile 1; picking up pile $k+2$ and putting it on pile 2; and so on, working from left to right and cycling back through as necessary.

She repeats this process until the cards are all in a single pile, and then stops. So for example, if $n=7$ and she chooses $k=3$ at the first step she will have the following three piles:

$$\begin{array}{c c c c} 7 & & & \\ 4 & 5 & 6 \\ 1 & 2 & 3 \end{array}$$

If she then chooses $k=1$ at the second step, she finishes with the cards in a single pile with the cards ordered 6352741 from top to bottom.

How many different final piles can Fiona end up with?

Determine the set of all real numbers $\alpha$ that can be expressed in the form

$$\alpha = \sum_{n=0}^{\infty} \frac{x_{n+1}}{x_n^3},$$

where $x_0, x_1, x_2, \ldots$ is an increasing sequence of real numbers with $x_0=1$.

A regular spatial pentagon consists of five points $P_1, P_2, P_3, P_4, P_5$ in $\mathbb{R}^3$ such that $|P_iP_{i+1}| = |P_jP_{j+1}|$ and $\angle P_{i-1}P_iP_{i+1} = \angle P_{j-1}P_jP_{j+1}$ for all $1 \leq i,j \leq 5$, where $P_0 = P_5$ and $P_6 = P_1$. A regular spatial pentagon is planar if there is a plane passing through all five points $P_1, P_2, P_3, P_4, P_5$.

Show that every regular spatial pentagon is planar.

Let $M$ be the set of $5 \times 5$ real matrices of rank 3. Given a matrix $A$ in $M$, the set of columns of $A$ has $2^5 - 1 = 31$ nonempty subsets. Let $k_A$ be the number of these subsets that are linearly independent.

Determine the maximum and minimum values of $k_A$, as $A$ varies over $M$.

The rank of a matrix is the dimension of the span of its columns.

For each positive integer $k$, let $S_k$ be the set of real numbers that can be expressed in the form

$$\frac{1}{n_1} + \frac{1}{n_2} + \cdots + \frac{1}{n_k},$$

where $n_1, n_2, \ldots, n_k$ are positive integers.

Prove that $S_k$ does not contain an infinite strictly increasing sequence.

A cat is trying to catch a mouse in the nonnegative quadrant

$$N = \{(x_1, x_2) \in \mathbb{R}^2 : x_1, x_2 \geq 0\}.$$

At time $t = 0$ the cat is at $(1, 1)$ and the mouse is at $(0, 0)$. The cat moves with speed $\sqrt{2}$ such that its position $c(t) = (c_1(t), c_2(t))$ is continuous, and differentiable except at finitely many points; while the mouse moves with speed 1 such that its position $m(t) = (m_1(t), m_2(t))$ is also continuous, and differentiable except at finitely many points. Thus

$$c(0) = (1, 1), \quad m(0) = (0, 0);$$

$c(t)$ and $m(t)$ are continuous functions of $t$ such that $c(t), m(t) \in N$ for all $t \geq 0$; the derivatives $c'(t) = (c'_1(t), c'_2(t))$ and $m'(t) = (m'_1(t), m'_2(t))$ each exist for all but finitely many $t$; and

$$(c'_1(t))^2 + (c'_2(t))^2 = 2, \quad (m'_1(t))^2 + (m'_2(t))^2 = 1,$$

whenever the respective derivative exists.

At each time $t$ the cat knows both the mouse’s position $m(t)$ and velocity $m'(t)$. Show that, no matter how the mouse moves, the cat can catch it by time $t = 1$; that is, show that the cat can move such that $c(\tau) = m(\tau)$ for some $\tau \in [0, 1]$.

The following problem is open in the sense that no solution is currently known to part (b). A proof of part (a) will be awarded 3 points.

Let $n \geq 2$ be an integer, and let $P_n$ be a regular polygon with $n^2 - n + 1$ vertices. We say that $n$ is taut if it is possible to choose $n$ of the vertices of $P_n$ such that the pairwise distances between the chosen vertices are all distinct.

(a) Show that if $n - 1$ is prime then $n$ is taut.

(b) Which integers $n \geq 2$ are taut?