Found problems: 42
2021 HMIC, 5
In an $n \times n$ square grid, $n$ squares are marked so that every rectangle composed of exactly $n$ grid squares contains at least one marked square. Determine all possible values of $n$.
2021 HMIC, 2
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.
2023 HMIC, P3
Triangle $ABC$ has incircle $\omega$ and $A$-excircle $\omega_A.$ Circle $\gamma_B$ passes through $B$ and is externally tangent to $\omega$ and $\omega_A.$ Circle $\gamma_C$ passes through $C$ and is externally tangent to $\omega$ and $\omega_A.$ If $\gamma_B$ intersects line $BC$ again at $D,$ and $\gamma_C$ intersects line $BC$ again at $E,$ prove that $BD=EC.$
2018 HMIC, 2
Consider a finite set of points $T\in\mathbb{R}^n$ contained in the $n$-dimensional unit ball centered at the origin, and let $X$ be the convex hull of $T$. Prove that for all positive integers $k$ and all points $x\in X$, there exist points $t_1, t_2, \dots, t_k\in T$, not necessarily distinct, such that their centroid
\[\frac{t_1+t_2+\dots+t_k}{k}\]has Euclidean distance at most $\frac{1}{\sqrt{k}}$ from $x$.
(The $n$-dimensional unit ball centered at the origin is the set of points in $\mathbb{R}^n$ with Euclidean distance at most $1$ from the origin. The convex hull of a set of points $T\in\mathbb{R}^n$ is the smallest set of points $X$ containing $T$ such that each line segment between two points in $X$ lies completely inside $X$.)
2021 HMIC, 1
$2021$ people are sitting around a circular table. In one move, you may swap the positions of two people sitting next to each other. Determine the minimum number of moves necessary to make each person end up $1000$ positions to the left of their original position.
2018 HMIC, 1
Let $m>1$ be a fixed positive integer. For a nonempty string of base-ten digits $S$, let $c(S)$ be the number of ways to split $S$ into contiguous nonempty strings of digits such that the base-ten number represented by each string is divisible by $m$. These strings are allowed to have leading zeroes.
In terms of $m$, what are the possible values that $c(S)$ can take?
For example, if $m=2$, then $c(1234)=2$ as the splits $1234$ and $12|34$ are valid, while the other six splits are invalid.
2023 HMIC, P2
A prime number $p$ is mundane if there exist positive integers $a$ and $b$ less than $\tfrac{p}{2}$ such that $\tfrac{ab-1}{p}$ is a positive integer. Find, with proof, all prime numbers that are not mundane.
2019 HMIC, 5
Let $p = 2017$ be a prime and $\mathbb{F}_p$ be the integers modulo $p$. A function $f: \mathbb{Z}\rightarrow\mathbb{F}_p$ is called [i]good[/i] if there is $\alpha\in\mathbb{F}_p$ with $\alpha\not\equiv 0\pmod{p}$ such that
\[f(x)f(y) = f(x + y) + \alpha^y f(x - y)\pmod{p}\]
for all $x, y\in\mathbb{Z}$. How many good functions are there that are periodic with minimal period $2016$?
[i]Ashwin Sah[/i]
2021 HMIC, 4
Let $A_1A_2A_3A_4$, $B_1B_2B_3B_4$, and $C_1C_2C_3C_4$ be three regular tetrahedra in $3$-dimensional space, no two of which are congruent. Suppose that, for each $i\in \{1,2,3,4\}$, $C_i$ is the midpoint of the line segment $A_iB_i$. Determine whether the four lines $A_1B_1$, $A_2B_2$, $A_3B_3$, and $A_4B_4$ must concur.
2020 HMIC, 1
Sir Alex is coaching a soccer team of $n$ players of distinct heights. He wants to line them up so that for each player $P$, the total number of players that are either to the left of $P$ and taller than $P$ or to the right of $P$ and shorter than $P$ is even. In terms of $n$, how many possible orders are there?
[i]Michael Ren[/i]
2016 HMIC, 5
Let $S = \{a_1, \ldots, a_n \}$ be a finite set of positive integers of size $n \ge 1$, and let $T$ be the set of all positive integers that can be expressed as sums of perfect powers (including $1$) of distinct numbers in $S$, meaning
\[ T = \left\{ \sum_{i=1}^n a_i^{e_i} \mid e_1, e_2, \dots, e_n \ge 0 \right\}. \]
Show that there is a positive integer $N$ (only depending on $n$) such that $T$ contains no arithmetic progression of length $N$.
[i]Yang Liu[/i]
2017 HMIC, 5
Let $S$ be the set $\{-1, 1\}^n$, that is, $n$-tuples such that each coordinate is either $-1$ or $1$. For \[s = (s_1, s_2, \ldots, s_n), t = (t_1, t_2, \ldots, t_n) \in \{-1, 1\}^n,\] define $s \odot t = (s_1t_1, s_2t_2, \ldots, s_nt_n)$.
Let $c$ be a positive constant, let $f : S \to \{-1, 1\}$ be a function such that there are at least $(1-c) \cdot 2^{2n}$ pairs $(s, t)$ with $s, t \in S$ such that $f(s \odot t) = f(s)f(t)$. Show that there exists a function $f'$ such that $f'(s \odot t) = f'(s)f'(t)$ for all $s, t \in S$ and $f(s) = f'(s)$ for at least $(1-10c) \cdot 2^n$ values of $s \in S$.
2016 HMIC, 3
Denote by $\mathbb{N}$ the positive integers. Let $f:\mathbb{N} \rightarrow \mathbb{N}$ be a function such that, for any $w,x,y,z \in \mathbb{N}$, \[ f(f(f(z)))f(wxf(yf(z)))=z^{2}f(xf(y))f(w). \] Show that $f(n!) \ge n!$ for every positive integer $n$.
[i]Pakawut Jiradilok[/i]
2021 HMIC, 3
Let $A$ be a set of $n\ge2$ positive integers, and let $\textstyle f(x)=\sum_{a\in A}x^a$. Prove that there exists a complex number $z$ with $\lvert z\rvert=1$ and $\lvert f(z)\rvert=\sqrt{n-2}$.
2019 HMIC, 3
Do there exist four points $P_i = (x_i, y_i) \in \mathbb{R}^2\ (1\leq i \leq 4)$ on the plane such that:
[list]
[*] for all $i = 1,2,3,4$, the inequality $x_i^4 + y_i^4 \le x_i^3+ y_i^3$ holds, and
[*] for all $i \neq j$, the distance between $P_i$ and $P_j$ is greater than $1$?
[/list]
[i]Pakawut Jiradilok[/i]
2016 HMIC, 1
Theseus starts at the point $(0, 0)$ in the plane. If Theseus is standing at the point $(x, y)$ in the plane, he can step one unit to the north to point $(x, y+1)$, one unit to the west to point $(x-1, y)$, one unit to the south to point $(x, y-1)$, or one unit to the east to point $(x+1, y)$. After a sequence of more than two such moves, starting with a step one unit to the south (to point $(0, -1)$), Theseus finds himself back at the point $(0, 0)$. He never visited any point other than $(0, 0)$ more than once, and never visited the point $(0, 0)$ except at the start and end of this sequence of moves.
Let $X$ be the number of times that Theseus took a step one unit to the north, and then a step one unit to the west immediately afterward. Let $Y$ be the number of times that Theseus took a step one unit to the west, and then a step one unit to the north immediately afterward. Prove that $|X - Y| = 1$.
[i]Mitchell Lee[/i]
2020 HMIC, 5
A triangle and a circle are in the same plane. Show that the area of the intersection of the triangle and the circle is at most one third of the area of the triangle plus one half of the area of the circle.
[i]Krit Boonsiriseth[/i]
2015 HMIC, 2
Let $m,n$ be positive integers with $m \ge n$. Let $S$ be the set of pairs $(a,b)$ of relatively prime positive integers such that $a,b \le m$ and $a+b > m$.
For each pair $(a,b)\in S$, consider the nonnegative integer solution $(u,v)$ to the equation $au - bv = n$ chosen with $v \ge 0$ minimal, and let $I(a,b)$ denote the (open) interval $(v/a, u/b)$.
Prove that $I(a,b) \subseteq (0,1)$ for every $(a,b)\in S$, and that any fixed irrational number $\alpha\in(0,1)$ lies in $I(a,b)$ for exactly $n$ distinct pairs $(a,b)\in S$.
[i]Victor Wang, inspired by 2013 ISL N7[/i]
2019 HMIC, 1
Let $ABC$ be an acute scalene triangle with incenter $I$. Show that the circumcircle of $BIC$ intersects the Euler line of $ABC$ in two distinct points.
(Recall that the [i]Euler line[/i] of a scalene triangle is the line that passes through its circumcenter, centroid, orthocenter, and the nine-point center.)
[i]Andrew Gu[/i]
2016 HMIC, 4
Let $P$ be an odd-degree integer-coefficient polynomial. Suppose that $xP(x)=yP(y)$ for infinitely many pairs $x,y$ of integers with $x\ne y$. Prove that the equation $P(x)=0$ has an integer root.
[i]Victor Wang[/i]
2015 HMIC, 1
Let $S$ be the set of positive integers $n$ such that the inequality
\[
\phi(n) \cdot \tau(n) \geq \sqrt{\frac{n^3}{3}}
\]
holds, where $\phi(n)$ is the number of positive integers $k \le n$ that are relatively prime to $n$, and $\tau(n)$ is the number of positive divisors of $n$. Prove that $S$ is finite.
2023 HMIC, P4
Let $n>1$ be a positive integer. Claire writes $n$ distinct positive real numbers $x_1, x_2, \dots, x_n$ in a row on a blackboard. In a $\textit{move},$ William can erase a number $x$ and replace it with either $\tfrac{1}{x}$ or $x+1$ at the same location. His goal is to perform a sequence of moves such that after he is done, the number are strictly increasing from left to right.
[list]
[*]Prove that there exists a positive constant $A,$ independent of $n,$ such that William can always reach his goal in at most $An \log n$ moves.
[*]Prove that there exists a positive constant $B,$ independent of $n,$ such that Claire can choose the initial numbers such that William cannot attain his goal in less than $Bn \log n$ moves.
[/list]
2017 HMIC, 2
Let $S = \{1, 2, \ldots, n\}$ for some positive integer $n$, and let $A$ be an $n$-by-$n$ matrix having as entries only ones and zeroes. Define an infinite sequence $\{x_i\}_{i \ge 0}$ to be [i]strange[/i] if: [list] [*] $x_i \in S$ for all $i$, [*] $a_{x_kx_{k+1}} = 1$ for all $k$, where $a_{ij}$ denotes the element in the $i^{\text{th}}$ row and $j^{\text{th}}$ column of $A$. [/list] Prove that the set of strange sequences is empty if and only if $A$ is nilpotent, i.e. $A^m = 0$ for some integer $m$.
2015 HMIC, 3
Let $M$ be a $2014\times 2014$ invertible matrix, and let $\mathcal{F}(M)$ denote the set of matrices whose rows are a permutation of the rows of $M$. Find the number of matrices $F\in\mathcal{F}(M)$ such that $\det(M + F) \ne 0$.
2018 HMIC, 5
Let $G$ be an undirected simple graph. Let $f(G)$ be the number of ways to orient all of the edges of $G$ in one of the two possible directions so that the resulting directed graph has no directed cycles. Show that $f(G)$ is a multiple of $3$ if and only if $G$ has a cycle of odd length.