Found problems: 46
2017 USA TSTST, 2
Ana and Banana are playing a game. First Ana picks a word, which is defined to be a nonempty sequence of capital English letters. (The word does not need to be a valid English word.) Then Banana picks a nonnegative integer $k$ and challenges Ana to supply a word with exactly $k$ subsequences which are equal to Ana's word. Ana wins if she is able to supply such a word, otherwise she loses.
For example, if Ana picks the word "TST", and Banana chooses $k=4$, then Ana can supply the word "TSTST" which has 4 subsequences which are equal to Ana's word.
Which words can Ana pick so that she wins no matter what value of $k$ Banana chooses?
(The subsequences of a string of length $n$ are the $2^n$ strings which are formed by deleting some of its characters, possibly all or none, while preserving the order of the remaining characters.)
[i]Proposed by Kevin Sun
2021 USA TSTST, 5
Let $T$ be a tree on $n$ vertices with exactly $k$ leaves. Suppose that there exists a subset of at least $\frac{n+k-1}{2}$ vertices of $T$, no two of which are adjacent. Show that the longest path in $T$ contains an even number of edges. [hide=*]A tree is a connected graph with no cycles. A leaf is a vertex of degree 1[/hide]
[i]Vincent Huang[/i]
2021 USA TSTST, 2
Let $a_1<a_2<a_3<a_4<\cdots$ be an infinite sequence of real numbers in the interval $(0,1)$. Show that there exists a number that occurs exactly once in the sequence
\[ \frac{a_1}{1},\frac{a_2}{2},\frac{a_3}{3},\frac{a_4}{4},\ldots.\]
[i]Merlijn Staps[/i]
2018 USA TSTST, 8
For which positive integers $b > 2$ do there exist infinitely many positive integers $n$ such that $n^2$ divides $b^n+1$?
[i]Evan Chen and Ankan Bhattacharya[/i]
2023 USA TSTST, 4
Let $n\ge 3$ be an integer and let $K_n$ be the complete graph on $n$ vertices. Each edge of $K_n$ is colored either red, green, or blue. Let $A$ denote the number of triangles in $K_n$ with all edges of the same color, and let $B$ denote the number of triangles in $K_n$ with all edges of different colors. Prove
\[ B\le 2A+\frac{n(n-1)}{3}.\]
(The [i]complete graph[/i] on $n$ vertices is the graph on $n$ vertices with $\tbinom n2$ edges, with exactly one edge joining every pair of vertices. A [i]triangle[/i] consists of the set of $\tbinom 32=3$ edges between $3$ of these $n$ vertices.)
[i]Proposed by Ankan Bhattacharya[/i]
2022 USA TSTST, 4
Let $\mathbb N$ denote the set of positive integers. A function $f\colon\mathbb N\to\mathbb N$ has the property that for all positive integers $m$ and $n$, exactly one of the $f(n)$ numbers
\[f(m+1),f(m+2),\ldots,f(m+f(n))\]
is divisible by $n$. Prove that $f(n)=n$ for infinitely many positive integers $n$.
2023 USA TSTST, 8
Let $ABC$ be an equilateral triangle with side length $1$. Points $A_1$ and $A_2$ are chosen on side $BC$, points $B_1$ and $B_2$ are chosen on side $CA$, and points $C_1$ and $C_2$ are chosen on side $AB$ such that $BA_1<BA_2$, $CB_1<CB_2$, and $AC_1<AC_2$.
Suppose that the three line segments $B_1C_2$, $C_1A_2$, $A_1B_2$ are concurrent, and the perimeters of triangles $AB_2C_1$, $BC_2A_1$, and $CA_2B_1$ are all equal. Find all possible values of this common perimeter.
[i]Ankan Bhattacharya[/i]
2024 USA TSTST, 2
Let $p$ be an odd prime number. Suppose $P$ and $Q$ are polynomials with integer coefficients such that $P(0)=Q(0)=1$, there is no nonconstant polynomial dividing both $P$ and $Q$, and
\[
1 + \cfrac{x}{1 + \cfrac{2x}{1 + \cfrac{\ddots}{1 +
(p-1)x}}}=\frac{P(x)}{Q(x)}.
\]
Show that all coefficients of $P$ except for the constant coefficient are divisible by $p$, and all coefficients of $Q$ are [i]not[/i] divisible by $p$.
[i]Andrew Gu[/i]
2012 USA TSTST, 6
Positive real numbers $x, y, z$ satisfy $xyz+xy+yz+zx = x+y+z+1$. Prove that \[ \frac{1}{3} \left( \sqrt{\frac{1+x^2}{1+x}} + \sqrt{\frac{1+y^2}{1+y}} + \sqrt{\frac{1+z^2}{1+z}} \right) \le \left( \frac{x+y+z}{3} \right)^{5/8} . \]
2024 USA TSTST, 5
For a positive integer $k$, let $s(k)$ denote the number of $1$s in the binary representation of $k$. Prove that for any positive integer $n$,
\[\sum_{i=1}^{n}(-1)^{s(3i)} > 0.\]
[i]Holden Mui[/i]
2022 USA TSTST, 5
Let $A_1$, $\ldots$, $A_{2022}$ be the vertices of a regular $2022$-gon in the plane. Alice and Bob play a game. Alice secretly chooses a line and colors all points in the plane on one side of the line blue, and all points on the other side of the line red. Points on the line are colored blue, so every point in the plane is either red or blue. (Bob cannot see the colors of the points.)
In each round, Bob chooses a point in the plane (not necessarily among $A_1, \ldots, A_{2022}$) and Alice responds truthfully with the color of that point. What is the smallest number $Q$ for which Bob has a strategy to always determine the colors of points $A_1, \ldots, A_{2022}$ in $Q$ rounds?
2023 USA TSTST, 9
For every integer $m\ge 1$, let $\mathbb{Z}/m\mathbb{Z}$ denote the set of integers modulo $m$. Let $p$ be a fixed prime and let $a\ge 2$ and $e\ge 1$ be fixed integers. Given a function $f\colon \mathbb{Z}/a\mathbb{Z}\to \mathbb{Z}/p^e\mathbb{Z}$ and an integer $k\ge 0$, the $k$[i]th finite difference[/i], denoted $\Delta^k f$, is the function from $\mathbb{Z}/a\mathbb{Z}$ to $\mathbb{Z}/p^e\mathbb{Z}$ defined recursively by
\begin{align*}
\Delta^0 f(n)&=f(n)\\
\Delta^k f(n)&=\Delta^{k-1}f(n+1)-\Delta^{k-1}f(n) & \text{for } k=1,2,\dots.
\end{align*}
Determine the number of functions $f$ such that there exists some $k\ge 1$ for which $\Delta^kf=f$.
[i]Holden Mui[/i]
2024 USA TSTST, 7
An infinite sequence $a_1$, $a_2$, $a_3$, $\ldots$ of real numbers satisfies
\[
a_{2n-1} + a_{2n} > a_{2n+1} + a_{2n+2} \qquad \mbox{and} \qquad a_{2n} + a_{2n+1} < a_{2n+2} + a_{2n+3}
\]
for every positive integer $n$. Prove that there exists a real number $C$ such that $a_{n} a_{n+1} < C$ for every positive integer $n$.
[i]Merlijn Staps[/i]
2024 USA TSTST, 1
For every ordered pair of integers $(i,j)$, not necessarily positive, we wish to select a point $P_{i,j}$ in the Cartesian plane whose coordinates lie inside the unit square defined by
\[ i < x < i+1, \qquad j < y < j+1. \]
Find all real numbers $c > 0$ for which it's possible to choose these points such that for all integers $i$ and $j$, the (possibly concave or degenerate) quadrilateral $P_{i,j} P_{i+1,j} P_{i+1,j+1} P_{i,j+1}$ has perimeter strictly less than $c$.
[i]Karthik Vedula[/i]
2019 USA TSTST, 9
Let $ABC$ be a triangle with incenter $I$. Points $K$ and $L$ are chosen on segment $BC$ such that the incircles of $\triangle ABK$ and $\triangle ABL$ are tangent at $P$, and the incircles of $\triangle ACK$ and $\triangle ACL$ are tangent at $Q$. Prove that $IP=IQ$.
[i]Ankan Bhattacharya[/i]
2023 USA TSTST, 5
Suppose $a,\,b,$ and $c$ are three complex numbers with product $1$. Assume that none of $a,\,b,$ and $c$ are real or have absolute value $1$. Define
\begin{tabular}{c c c}
$p=(a+b+c)+\left(\dfrac 1a+\dfrac 1b+\dfrac 1c\right)$ & \text{and} & $q=\dfrac ab+\dfrac bc+\dfrac ca$.
\end{tabular}
Given that both $p$ and $q$ are real numbers, find all possible values of the ordered pair $(p,q)$.
[i]David Altizio[/i]
2024 USA TSTST, 4
Let $ABCD$ be a quadrilateral inscribed in a circle with center $O$ and $E$ be the intersection of segments $AC$ and $BD$. Let $\omega_1$ be the circumcircle of $ADE$ and $\omega_2$ be the circumcircle of $BCE$. The tangent to $\omega_1$ at $A$ and the tangent to $\omega_2$ at $C$ meet at $P$. The tangent to $\omega_1$ at $D$ and the tangent to $\omega_2$ at $B$ meet at $Q$. Show that $OP=OQ$.
[i]Merlijn Staps[/i]
2022 USA TSTST, 8
Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f \colon \mathbb{N} \to \mathbb{Z}$ such that \[\left\lfloor \frac{f(mn)}{n} \right\rfloor=f(m)\] for all positive integers $m,n$.
[i]Merlijn Staps[/i]
2011 USA TSTST, 3
Prove that there exists a real constant $c$ such that for any pair $(x,y)$ of real numbers, there exist relatively prime integers $m$ and $n$ satisfying the relation
\[
\sqrt{(x-m)^2 + (y-n)^2} < c\log (x^2 + y^2 + 2).
\]
2021 USA TSTST, 1
Let $ABCD$ be a quadrilateral inscribed in a circle with center $O$. Points $X$ and $Y$ lie on sides $AB$ and $CD$, respectively. Suppose the circumcircles of $ADX$ and $BCY$ meet line $XY$ again at $P$ and $Q$, respectively. Show that $OP=OQ$.
[i]Holden Mui[/i]
2021 USA TSTST, 4
Let $a$ and $b$ be positive integers. Suppose that there are infinitely many pairs of positive integers $(m,n)$ for which $m^2+an+b$ and $n^2+am+b$ are both perfect squares. Prove that $a$ divides $2b$.
[i]Holden Mui[/i]
2022 USA TSTST, 7
Let $ABCD$ be a parallelogram. Point $E$ lies on segment $CD$ such that \[2\angle AEB=\angle ADB+\angle ACB,\] and point $F$ lies on segment $BC$ such that \[2\angle DFA=\angle DCA+\angle DBA.\] Let $K$ be the circumcenter of triangle $ABD$. Prove that $KE=KF$.
[i]Merlijn Staps[/i]
2023 USA TSTST, 2
Let $n\ge m\ge 1$ be integers. Prove that
\[\sum_{k=m}^n \left (\frac 1{k^2}+\frac 1{k^3}\right) \ge m\cdot \left(\sum_{k=m}^n \frac 1{k^2}\right)^2.\]
[i]Raymond Feng and Luke Robitaille[/i]
2024 USA TSTST, 3
Let $A = \{a_1, \dots, a_{2024}\}$ be a set of $2024$ pairwise distinct real numbers. Assume that there exist positive integers $b_1, b_2,\dotsc,b_{2024}$ such that \[ a_1b_1 + a_2b_2 + \dots + a_{2024}b_{2024} = 0. \]
Prove that one can choose $a_{2025}, a_{2026}, a_{2027}, \dots$ such that $a_k \in A$ for all $k \ge 2025$ and, for every positive integer $d$, there exist infinitely many positive integers $n$ satisfying
\[ \sum_{k=1}^n a_k k^d = 0. \]
[i]Daniel Zhu[/i]
2021 USA TSTST, 6
Triangles $ABC$ and $DEF$ share circumcircle $\Omega$ and incircle $\omega$ so that points $A,F,B,D,C,$ and $E$ occur in this order along $\Omega$. Let $\Delta_A$ be the triangle formed by lines $AB,AC,$ and $EF,$ and define triangles $\Delta_B, \Delta_C, \ldots, \Delta_F$ similarly. Furthermore, let $\Omega_A$ and $\omega_A$ be the circumcircle and incircle of triangle $\Delta_A$, respectively, and define circles $\Omega_B, \omega_B, \ldots, \Omega_F, \omega_F$ similarly.
(a) Prove that the two common external tangents to circles $\Omega_A$ and $\Omega_D$ and the two common external tangents to $\omega_A$ and $\omega_D$ are either concurrent or pairwise parallel.
(b) Suppose that these four lines meet at point $T_A$, and define points $T_B$ and $T_C$ similarly. Prove that points $T_A,T_B$, and $T_C$ are collinear.
[i]Nikolai Beluhov[/i]