US-TST 2018

Let $n \geq 2$ be a positive integer, and let $\sigma(n)$ denote the sum of the positive divisors of $n$. Prove that the $n^{\text {th }}$ smallest positive integer relatively prime to $n$ is at least $\sigma(n)$, and determine for which $n$ equality holds.

Find all functions $f: \mathbb{Z}^{2} \rightarrow[0,1]$ such that for any integers $x$ and $y$, $$f(x, y)=\frac{f(x-1, y)+f(x, y-1)}{2}$$

At a university dinner, there are 2017 mathematicians who each order two distinct entrées, with no two mathematicians ordering the same pair of entrées. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée (ties broken arbitrarily). Over all possible sets of orders, what is the maximum total amount the university could have paid?

Let $n$ be a positive integer and let $S \subseteq\{0,1\}^{n}$ be a set of binary strings of length $n$. Given an odd number $x_{1}, \ldots, x_{2 k+1} \in S$ of binary strings (not necessarily distinct), their majority is defined as the binary string $y \in\{0,1\}^{n}$ for which the $i^{\text {th }}$ bit of $y$ is the most common bit among the $i^{\text {th }}$ bits of $x_{1}, \ldots, x_{2 k+1}$. (For example, if $n=4$ the majority of $0000,0000,1101,1100,0101$ is 0100 .) Suppose that for some positive integer $k, S$ has the property $P_{k}$ that the majority of any $2 k+1$ binary strings in $S$ (possibly with repetition) is also in $S$. Prove that $S$ has the same property $P_{k}$ for all positive integers $k$.

Let $A B C D$ be a convex cyclic quadrilateral which is not a kite, but whose diagonals are perpendicular and meet at $H$. Denote by $M$ and $N$ the midpoints of $\overline{B C}$ and $\overline{C D}$. Rays $M H$ and $N H$ meet $\overline{A D}$ and $\overline{A B}$ at $S$ and $T$, respectively. Prove there exists a point $E$, lying outside quadrilateral $A B C D$, such that - ray $E H$ bisects both angles $\angle B E S, \angle T E D$, and - $\angle B E N=\angle M E D$.

Alice and Bob play a game. First, Alice secretly picks a finite set $S$ of lattice points in the Cartesian plane. Then, for every line $\ell$ in the plane which is horizontal, vertical, or has slope +1 or -1 , she tells Bob the number of points of $S$ that lie on $\ell$. Bob wins if he can then determine the set $S$. Prove that if Alice picks $S$ to be of the form $$S=\left\{(x, y) \in \mathbb{Z}^{2} \mid m \leq x^{2}+y^{2} \leq n\right\}$$ for some positive integers $m$ and $n$, then Bob can win. (Bob does not know in advance that $S$ is of this form.)