[Solutions] United States of America Team Selection Test 2018

1. Let $n \ge 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.
2. Find all functions $f: \mathbb{Z}^2 \to [0, 1]$ such that for any integers $x$ and $y$, $f(x, y) = \frac{f(x - 1, y) + f(x, y - 1)}{2}.$
3. 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?
4. 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, \dots, x_{2k + 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, \dots,x_{2k + 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 $2k + 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$.
5. Let $ABCD$ 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{BC}$ and $\overline{CD}$. Rays $MH$ and $NH$ meet $\overline{AD}$ and $\overline{AB}$ at $S$ and $T$, respectively. Prove that there exists a point $E$, lying outside quadrilateral $ABCD$, such that ray $EH$ bisects both angles $\angle BES$, $\angle TED$, and $\angle BEN = \angle MED$.
6. 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 determine the set $S$. Prove that if Alice picks $S$ to be of the form $S = \{(x, y) \in \mathbb{Z}^2 \mid m \le x^2 + y^2 \le n\}$ for some positive integers $m$ and $n$, then Bob can win. (Bob does not know in advance that $S$ is of this form.)
 MOlympiad.NET là dự án thu thập và phát hành các đề thi tuyển sinh và học sinh giỏi toán. Quý bạn đọc muốn giúp chúng tôi chỉnh sửa đề thi này, xin hãy để lại bình luận facebook (có thể đính kèm hình ảnh) hoặc google (có thể sử dụng $\LaTeX$) bên dưới. BBT rất mong bạn đọc ủng hộ UPLOAD đề thi và đáp án mới hoặc liên hệbbt.molympiad@gmail.comChúng tôi nhận tất cả các định dạng của tài liệu: $\TeX$, PDF, WORD, IMG,...