Found problems: 42
2021 SG Originals, Q2
Let $n$ be a positive integer. Alice writes $n$ real numbers $a_1, a_2,\dots, a_n$ in a line (in that order). Every move, she picks one number and replaces it with the average of itself and its neighbors ($a_n$ is not a neighbor of $a_1$, nor vice versa). A number [i]changes sign[/i] if it changes from being nonnegative to negative or vice versa. In terms of $n$, determine the maximum number of times that $a_1$ can change sign, across all possible values of $a_1,a_2,\dots, a_n$ and all possible sequences of moves Alice may make.
2024 HMIC, 3
Let $S$ be a set of nonnegative integers such that
[list]
[*] there exist two elements $a$ and $b$ in $S$ such that $a,b>1$ and $\gcd(a,b)=1$; and
[*] for any (not necessarily distinct) element $x$ and nonzero element $y$ in $S$, both $xy$ and the remainder when $x$ is divided by $y$ are in $S$.
[/list]
Prove that $S$ contains every nonnegative integer.
[i]Jacob Paltrowitz[/i]
2016 HMIC, 2
Let $ABC$ be an acute triangle with circumcenter $O$, orthocenter $H$, and circumcircle $\Omega$. Let $M$ be the midpoint of $AH$ and $N$ the midpoint of $BH$. Assume the points $M$, $N$, $O$, $H$ are distinct and lie on a circle $\omega$. Prove that the circles $\omega$ and $\Omega$ are internally tangent to each other.
[i]Dhroova Aiylam and Evan Chen[/i]
2020 HMIC, 3
Let $P_1P_2P_3P_4$ be a tetrahedron in $\mathbb{R}^3$ and let $O$ be a point equidistant from each of its vertices. Suppose there exists a point $H$ such that for each $i$, the line $P_iH$ is perpendicular to the plane through the other three vertices. Line $P_1H$ intersects the plane through $P_2, P_3, P_4$ at $A$, and contains a point $B\neq P_1$ such that $OP_1=OB$. Show that $HB=3HA$.
[i]Michael Ren[/i]
2020 HMIC, 2
Some bishops and knights are placed on an infinite chessboard, where each square has side length $1$ unit. Suppose that the following conditions hold:
[list]
[*] For each bishop, there exists a knight on the same diagonal as that bishop (there may be another piece between the bishop and the knight).
[*] For each knight, there exists a bishop that is exactly $\sqrt{5}$ units away from it.
[*] If any piece is removed from the board, then at least one of the above conditions is no longer satisfied.
[/list]
If $n$ is the total number of pieces on the board, find all possible values of $n$.
[i]Sheldon Kieren Tan[/i]
2017 HMIC, 1
Kevin and Yang are playing a game. Yang has $2017 + \tbinom{2017}{2}$ cards with their front sides face down on the table. The cards are constructed as follows: [list] [*] For each $1 \le n \le 2017$, there is a blue card with $n$ written on the back, and a fraction $\tfrac{a_n}{b_n}$ written on the front, where $\gcd(a_n, b_n) = 1$ and $a_n, b_n > 0$. [*] For each $1 \le i < j \le 2017$, there is a red card with $(i, j)$ written on the back, and a fraction $\tfrac{a_i+a_j}{b_i+b_j}$ written on the front. [/list] 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.
2024 HMIC, 5
Let $ABC$ be an acute, scalene triangle with circumcenter $O$ and symmedian point $K$. Let $X$ be the point on the circumcircle of triangle $BOC$ such that $\angle AXO = 90^\circ$. Assume that $X\neq K$. The hyperbola passing through $B$, $C$, $O$, $K$, and $X$ intersects the circumcircle of triangle $ABC$ at points $U$ and $V$, distinct from $B$ and $C$. Prove that $UV$ is the perpendicular bisector of $AX$.
[i]The symmedian point of triangle $ABC$ is the intersection of the reflections of $B$-median and $C$-median across the angle bisectors of $\angle ABC$ and $\angle ACB$, respectively.[/i]
[i]Pitchayut Saengrungkongka[/i]
2017 HMIC, 3
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 \le i \le m$ and $w \cdot v_i \le 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 (at most) $C$ rounds. The constant $C$ may depend on the vectors $v_1, \ldots, v_m$.
2015 HMIC, 5
Let $\omega = e^{2\pi i /5}$ be a primitive fifth root of unity. Prove that there do not exist integers $a, b, c, d, k$ with $k > 1$ such that \[(a + b \omega + c \omega^2 + d \omega^3)^{k}=1+\omega.\]
[i]Carl Lian[/i]
2020 HMIC, 4
Let $C_k=\frac{1}{k+1}\binom{2k}{k}$ denote the $k^{\text{th}}$ Catalan number and $p$ be an odd prime. Prove that exactly half of the numbers in the set
\[\left\{\sum_{k=1}^{p-1}C_kn^k\,\middle\vert\, n\in\{1,2,\ldots,p-1\}\right\}\]
are divisible by $p$.
[i]Tristan Shin[/i]
2019 HMIC, 4
A [i]cactus[/i] is a finite simple connected graph where no two cycles share an edge. Show that in a nonempty cactus, there must exist a vertex which is part of at most one cycle.
[i]Kevin Yang[/i]
2018 HMIC, 3
A polygon in the plane (with no self-intersections) is called $\emph{equitable}$ if every line passing through the origin divides the polygon into two (possibly disconnected) regions of equal area.
Does there exist an equitable polygon which is not centrally symmetric about the origin?
(A polygon is centrally symmetric about the origin if a $180$-degree rotation about the origin sends the polygon to itself.)
2023 HMIC, P1
Let $\mathbb{Q}^{+}$ denote the set of positive rational numbers. Find, with proof, all functions $f:\mathbb{Q}^+ \to \mathbb{Q}^+$ such that, for all positive rational numbers $x$ and $y,$ we have \[f(x)=f(x+y)+f(x+x^2f(y)).\]
2018 HMIC, 4
Find all functions $f: \mathbb{R}^+\to\mathbb{R}^+$ such that
\[f(x+f(y+xy))=(y+1)f(x+1)-1\]for all $x,y\in\mathbb{R}^+$.
($\mathbb{R}^+$ denotes the set of positive real numbers.)
2023 HMIC, P5
Let $a_1, a_2, \dots$ be an infinite sequence of positive integers such that, for all positive integers $m$ and $n,$ we have that $a_{m+n}$ divides $a_ma_n-1.$ Prove that there exists an integer $C$ such that, for all positive integers $k>C,$ we have $a_k=1.$
2019 HMIC, 2
Annie has a permutation $(a_1, a_2, \dots ,a_{2019})$ of $S=\{1,2,\dots,2019\}$, and Yannick wants to guess her permutation. With each guess Yannick gives Annie an $n$-tuple $(y_1, y_2, \dots, y_{2019})$ of integers in $S$, and then Annie gives the number of indices $i\in S$ such that $a_i=y_i$.
(a) Show that Yannick can always guess Annie's permutation with at most $1200000$ guesses.
(b) Show that Yannick can always guess Annie's permutation with at most $24000$ guesses.
[i]Yannick Yao[/i]
2017 HMIC, 4
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 [i]weight.[/i] 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'$ be the graph with vertex set $A \cup B$, and (which) 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'$ have the same weight.