Found problems: 41
2017 CMIMC Individual Finals, 3
Say an integer polynomial is $\textit{primitive}$ if the greatest common divisor of its coefficients is $1$. For example, $2x^2+3x+6$ is primitive because $\gcd(2,3,6)=1$. Let $f(x)=a_2x^2+a_1x+a_0$ and $g(x) = b_2x^2+b_1x+b_0$, with $a_i,b_i\in\{1,2,3,4,5\}$ for $i=0,1,2$. If $N$ is the number of pairs of polynomials $(f(x),g(x))$ such that $h(x) = f(x)g(x)$ is primitive, find the last three digits of $N$.
2018 CMIMC Individual Finals, 3
Let $\mathcal{F}$ be a family of subsets of $\{1,2,\ldots, 2017\}$ with the following property: if $S_1$ and $S_2$ are two elements of $\mathcal{F}$ with $S_1\subsetneq S_2$, then $|S_2\setminus S_1|$ is odd. Compute the largest number of subsets $\mathcal{F}$ may contain.
2016 CMIMC, 2
The $\emph{Stooge sort}$ is a particularly inefficient recursive sorting algorithm defined as follows: given an array $A$ of size $n$, we swap the first and last elements if they are out of order; we then (if $n\ge3$) Stooge sort the first $\lceil\tfrac{2n}3\rceil$ elements, then the last $\lceil\tfrac{2n}3\rceil$, then the first $\lceil\tfrac{2n}3\rceil$ elements again. Given that this runs in $O(n^\alpha)$, where $\alpha$ is minimal, find the value of $(243/32)^\alpha$.
2016 CMIMC, 2
Determine the value of the sum \[\left|\sum_{1\leq i<j\leq 50}ij(-1)^{i+j}\right|.\]
2018 CMIMC Individual Finals, 1
How many nonnegative integers with at most $40$ digits consisting of entirely zeroes and ones are divisible by $11$?
2016 CMIMC, 3
Let $S$ be the set containing all positive integers whose decimal representations contain only 3’s and 7’s, have at most 1998 digits, and have at least one digit appear exactly 999 times. If $N$ denotes the number of elements in $S$, find the remainder when $N$ is divided by 1000.
2017 CMIMC Individual Finals, 1
Find all real numbers $x$ such that the expression
\[\log_2 |1 + \log_2 |2 + \log_2 |x| | |\]
does not have a defined value.
2016 CMIMC, 3
Let $\{x\}$ denote the fractional part of $x$. For example, $\{5.5\}=0.5$. Find the smallest prime $p$ such that the inequality \[\sum_{n=1}^{p^2}\left\{\dfrac{n^p}{p^2}\right\}>2016\] holds.
2017 CMIMC Individual Finals, 2
Kevin likes drawing. He takes a large piece of paper and draws on it every rectangle with positive integer side lengths and perimeter at most 2017, with no two rectangles overlapping. Compute the total area of the paper that is covered by a rectangle.
2016 CMIMC, 1
For all integers $n\geq 2$, let $f(n)$ denote the largest positive integer $m$ such that $\sqrt[m]{n}$ is an integer. Evaluate \[f(2)+f(3)+\cdots+f(100).\]
2018 CMIMC Individual Finals, 3
For $n\in\mathbb N$, let $x$ be the solution of $x^x=n$. Find the asymptotics of $x$, i.e., express $x=\Theta(f(n))$ for some suitable explicit function of $n$.
2016 CMIMC, 3
Let $\varepsilon$ denote the empty string. Given a pair of strings $(A,B)\in\{0,1,2\}^*\times\{0,1\}^*$, we are allowed the following operations:
\[\begin{cases}
(A,1)\to(A0,\varepsilon)\\
(A,10)\to(A00,\varepsilon)\\
(A,0B)\to(A0,B)\\
(A,11B)\to(A01,B)\\
(A,100B)\to(A0012,1B)\\
(A,101B)\to(A00122,10B)
\end{cases}\]
We perform these operations on $(A,B)$ until we can no longer perform any of them. We then iteratively delete any instance of $20$ in $A$ and replace any instance of $21$ with $1$ until there are no such substrings remaining. Among all binary strings $X$ of size $9$, how many different possible outcomes are there for this process performed on $(\varepsilon,X)$?
2018 CMIMC Individual Finals, 3
Determine the number of integers $a$ with $1\leq a\leq 1007$ and the property that both $a$ and $a+1$ are quadratic residues mod $1009$.
2017 CMIMC Individual Finals, 2
Find the smallest three-digit divisor of the number \[1\underbrace{00\ldots 0}_{100\text{ zeros}}1\underbrace{00\ldots 0}_{100\text{ zeros}}1.\]
2016 CMIMC, 1
Point $A$ lies on the circumference of a circle $\Omega$ with radius $78$. Point $B$ is placed such that $AB$ is tangent to the circle and $AB=65$, while point $C$ is located on $\Omega$ such that $BC=25$. Compute the length of $\overline{AC}$.
2016 CMIMC, 3
Triangle $ABC$ satisfies $AB=28$, $BC=32$, and $CA=36$, and $M$ and $N$ are the midpoints of $\overline{AB}$ and $\overline{AC}$ respectively. Let point $P$ be the unique point in the plane $ABC$ such that $\triangle PBM\sim\triangle PNC$. What is $AP$?
2016 CMIMC, 1
For a set $S \subseteq \mathbb{N}$, define $f(S) = \{\left\lceil \sqrt{s} \right\rceil \mid s \in S\}$. Find the number of sets $T$ such that $\vert f(T) \vert = 2$ and $f(f(T)) = \{2\}$.
2017 CMIMC Individual Finals, 3
In a certain game, the set $\{1, 2, \dots, 10\}$ is partitioned into equally-sized sets $A$ and $B$. In each of five consecutive rounds, Alice and Bob simultaneously choose an element from $A$ or $B$, respectively, that they have not yet chosen; whoever chooses the larger number receives a point, and whoever obtains three points wins the game. Determine the probability that Alice is guaranteed to win immediately after the set is initially partitioned.
2018 CMIMC Individual Finals, 2
Determine the largest number of steps for $\gcd(k,76)$ to terminate over all choices of $0 < k < 76$, using the following algorithm for gcd. Give your answer in the form $(n,k)$ where $n$ is the maximal number of steps and $k$ is the $k$ which achieves this. If multiple $k$ work, submit the smallest one.
\begin{tabular}{l}
1: \textbf{FUNCTION} $\text{gcd}(a,b)$: \\
2: $\qquad$ \textbf{IF} $a = 0$ \textbf{RETURN} $b$ \\
3: $\qquad$ \textbf{ELSE RETURN} $\text{gcd}(b \bmod a,a)$
\end{tabular}
2017 CMIMC Individual Finals, 1
Cody has an unfair coin that flips heads with probability either $\tfrac13$ or $\tfrac23$, but he doesn't know which one it is. Using this coin, what is the fewest number of independent flips needed to simulate a coin that he knows will flip heads with probability $\tfrac13$?
2018 CMIMC Individual Finals, 3
Let $ABC$ be a triangle with incircle $\omega$ and incenter $I$. The circle $\omega$ is tangent to $BC$, $CA$, and $AB$ at $D$, $E$, and $F$ respectively. Point $P$ is the foot of the angle bisector from $A$ to $BC$, and point $Q$ is the foot of the altitude from $D$ to $EF$. Suppose $AI=7$, $IP=5$, and $DQ=4$. Compute the radius of $\omega$.
2016 CMIMC, 2
Let $S = \{1,2,3,4,5,6,7\}$. Compute the number of sets of subsets $T = \{A, B, C\}$ with $A, B, C \in S$ such that $A \cup B \cup C = S$, $(A \cap C) \cup (B \cap C) = \emptyset$, and no subset contains two consecutive integers.
2018 CMIMC Individual Finals, 2
John has a standard four-sided die. Each roll, he gains points equal to the value of the roll multiplied by the number of times he has now rolled that number; for example, if his first rolls were $3,3,2,3$, he would have $3+6+2+9=20$ points. Find the expected number of points John will have after rolling the die 25 times.
2017 CMIMC Individual Finals, 3
The parabola $\mathcal P$ given by equation $y=x^2$ is rotated some acute angle $\theta$ clockwise about the origin such that it hits both the $x$ and $y$ axes at two distinct points. Suppose the length of the segment $\mathcal P$ cuts the $x$-axis is $1$. What is the length of the segment $\mathcal P$ cuts the $y$-axis?
2018 CMIMC Individual Finals, 2
Suppose $ABCD$ is a trapezoid with $AB\parallel CD$ and $AB\perp BC$. Let $X$ be a point on segment $\overline{AD}$ such that $AD$ bisects $\angle BXC$ externally, and denote $Y$ as the intersection of $AC$ and $BD$. If $AB=10$ and $CD=15$, compute the maximum possible value of $XY$.