HMIC 2017

Kevin and Yang are playing a game. Yang has $2017+\binom{2017}{2}$ cards with their front sides face down on the table. The cards are constructed as follows:

• For each $1 \leq n \leq 2017$, there is a blue card with $n$ written on the back, and a fraction $\frac{a_{n}}{b_{n}}$ written on the front, where $\operatorname{gcd}\left(a_{n}, b_{n}\right)=1$ and $a_{n}, b_{n}>0$.
• For each $1 \leq i<j \leq 2017$, there is a red card with $(i, j)$ written on the back, and a fraction $\frac{a_{i}+a_{j}}{b_{i}+b_{j}}$ written on the front.

It is given no two cards have equal fractions. In a turn Kevin can pick any two cards and Yang tells Kevin which card has the larger fraction on the front. Show that, in fewer than 10000 turns, Kevin can determine which red card has the largest fraction out of all of the red cards.

Let $S=\{1,2 \ldots, n\}$ for some positive integer $n$, and let $A$ be an $n$-by- $n$ matrix having as entries only ones and zeros. Define an infinite sequence $\left\{x_{i}\right\}_{i \geq 0}$ to be strange if:

• $x_{i} \in S$ for all $i$,
• $a_{x_{k} x_{k+1}}=1$ for all $k$, where $a_{i j}$ denotes the element in the $i^{\text {th }}$ row and $j^{\text {th }}$ column of $A$.

Prove that the set of strange sequences is empty if and only if $A$ is nilpotent, i.e. $A^{m}=0$ for some integer $m$.

Let $v_{1}, v_{2}, \ldots, v_{m}$ be vectors in $\mathbb{R}^{n}$, such that each has a strictly positive first coordinate. Consider the following process. Start with the zero vector $w=(0,0, \ldots, 0) \in \mathbb{R}^{n}$. Every round, choose an $i$ such that $1 \leq i \leq m$ and $w \cdot v_{i} \leq 0$, and then replace $w$ with $w+v_{i}$.

Show that there exists a constant $C$ such that regardless of your choice of $i$ at each step, the process is guaranteed to terminate in $C$ rounds. The constant $C$ may depend on the vectors $v_{1}, \ldots, v_{m}$.

Let $G$ be a weighted bipartite graph $A \cup B$, with $|A|=|B|=n$. In other words, each edge in the graph is assigned a positive integer value, called its weight. Also, define the weight of a perfect matching in $G$ to be the sum of the weights of the edges in the matching. Let $G^{\prime}$ be the graph with vertex set $A \cup B$, and contains the edge $e$ if and only if $e$ is part of some minimum weight perfect matching in $G$. Show that all perfect matchings in $G^{\prime}$ have the same weight.

Let $S$ be the set $\{-1,1\}^{n}$, that is, $n$-tuples such that each coordinate is either -1 or 1 . For

$$s=\left(s_{1}, s_{2}, \ldots, s_{n}\right), t=\left(t_{1}, t_{2}, \ldots, t_{n}\right) \in\{-1,1\}^{n}$$

define $s \odot t=\left(s_{1} t_{1}, s_{2} t_{2}, \ldots, s_{n} t_{n}\right)$. Let $c$ be a positive constant, and let $f: S \rightarrow\{-1,1\}$ be a function such that there are at least $(1-c) \cdot 2^{2 n}$ pairs $(s, t)$ with $s, t \in S$ such that $f(s \odot t)=f(s) f(t)$. Show that there exists a function $f^{\prime}$ such that $f^{\prime}(s \odot t)=f^{\prime}(s) f^{\prime}(t)$ for all $s, t \in S$ and $f(s)=f^{\prime}(s)$ for at least $(1-10 c) \cdot 2^{n}$ values of $s \in S$.