Olympiad problems

2016 USA TSTST, 1

Let $A = A(x,y)$ and $B = B(x,y)$ be two-variable polynomials with real coefficients. Suppose that $A(x,y)/B(x,y)$ is a polynomial in $x$ for infinitely many values of $y$, and a polynomial in $y$ for infinitely many values of $x$. Prove that $B$ divides $A$, meaning there exists a third polynomial $C$ with real coefficients such that $A = B \cdot C$. [i]Proposed by Victor Wang[/i]

2016 USA TSTST, 5

Tags: combinatorics , Tstst , TSTSt 2016

In the coordinate plane are finitely many [i]walls[/i]; which are disjoint line segments, none of which are parallel to either axis. A bulldozer starts at an arbitrary point and moves in the $+x$ direction. Every time it hits a wall, it turns at a right angle to its path, away from the wall, and continues moving. (Thus the bulldozer always moves parallel to the axes.) Prove that it is impossible for the bulldozer to hit both sides of every wall. [i]Proposed by Linus Hamilton and David Stoner[/i]

2016 USA TSTST, 3

Tags: polynomial , number theory , Tstst , TSTSt 2016

Decide whether or not there exists a nonconstant polynomial $Q(x)$ with integer coefficients with the following property: for every positive integer $n > 2$, the numbers \[ Q(0), \; Q(1), Q(2), \; \dots, \; Q(n-1) \] produce at most $0.499n$ distinct residues when taken modulo $n$. [i]Proposed by Yang Liu[/i]

2016 USA TSTST, 4

Tags: Euler , number theory , Tstst , TSTSt 2016 , totient function , function

Suppose that $n$ and $k$ are positive integers such that \[ 1 = \underbrace{\varphi( \varphi( \dots \varphi(}_{k\ \text{times}} n) \dots )). \] Prove that $n \le 3^k$. Here $\varphi(n)$ denotes Euler's totient function, i.e. $\varphi(n)$ denotes the number of elements of $\{1, \dots, n\}$ which are relatively prime to $n$. In particular, $\varphi(1) = 1$. [i]Proposed by Linus Hamilton[/i]