Found problems: 89
2016 CMIMC, 2
Six people each flip a fair coin. Everyone who flipped tails then flips their coin again. Given that the probability that all the coins are now heads can be expressed as simplified fraction $\tfrac{m}{n}$, compute $m+n$.
2016 CMIMC, 5
Recall that in any row of Pascal's Triangle, the first and last elements of the row are $1$ and each other element in the row is the sum of the two elements above it from the previous row. With this in mind, define the $\textit{Pascal Squared Triangle}$ as follows:
[list]
[*] In the $n^{\text{th}}$ row, where $n\geq 1$, the first and last elements of the row equal $n^2$;
[*] Each other element is the sum of the two elements directly above it.
[/list]
The first few rows of the Pascal Squared Triangle are shown below.
\[\begin{array}{c@{\hspace{7em}}
c@{\hspace{2pt}}c@{\hspace{2pt}}c@{\hspace{4pt}}c@{\hspace{2pt}}
c@{\hspace{2pt}}c@{\hspace{2pt}}c@{\hspace{2pt}}c@{\hspace{3pt}}c@{\hspace{2pt}}
c@{\hspace{2pt}}c} \vspace{4pt}
\text{Row 1: } & & & & & & 1 & & & & & \\\vspace{4pt}
\text{Row 2: } & & & & & 4 & & 4 & & & & \\\vspace{4pt}
\text{Row 3: } & & & & 9 & & 8 & & 9 & & & \\\vspace{4pt}
\text{Row 4: } & & &16& &17& &17& & 16& & \\\vspace{4pt}
\text{Row 5: } & &25 & &33& &34 & &33 & &25 &
\end{array}\]
Let $S_n$ denote the sum of the entries in the $n^{\text{th}}$ row. For how many integers $1\leq n\leq 10^6$ is $S_n$ divisible by $13$?
2016 CMIMC, 8
Let $N$ be the number of triples of positive integers $(a,b,c)$ with $a\leq b\leq c\leq 100$ such that the polynomial \[P(x)=x^2+(a^2+4b^2+c^2+1)x+(4ab+4bc-2ca)\] has integer roots in $x$. Find the last three digits of $N$.
2016 CMIMC, 5
We define the $\emph{weight}$ of a path to be the sum of the numbers written on each edge of the path. Find the minimum weight among all paths in the graph below that visit each vertex precisely once:
[center][img]http://i.imgur.com/V99Eg9j.png[/img][/center]
2016 CMIMC, 1
Let $\triangle ABC$ be an equilateral triangle and $P$ a point on $\overline{BC}$. If $PB=50$ and $PC=30$, compute $PA$.
2016 CMIMC, 4
For some integer $n > 0$, a square paper of side length $2^{n}$ is repeatedly folded in half, right-to-left then bottom-to-top, until a square of side length 1 is formed. A hole is then drilled into the square at a point $\tfrac{3}{16}$ from the top and left edges, and then the paper is completely unfolded. The holes in the unfolded paper form a rectangular array of unevenly spaced points; when connected with horizontal and vertical line segments, these points form a grid of squares and rectangles. Let $P$ be a point chosen randomly from \textit{inside} this grid. Suppose the largest $L$ such that, for all $n$, the probability that the four segments $P$ is bounded by form a square is at least $L$ can be written in the form $\tfrac mn$ where $m$ and $n$ are positive relatively prime integers. Find $m+n$.
2016 CMIMC, 1
For how many distinct ordered triples $(a,b,c)$ of boolean variables does the expression $a \lor (b \land c)$ evaluate to true?
2016 CMIMC, 10
Let $\mathcal{P}$ be the unique parabola in the $xy$-plane which is tangent to the $x$-axis at $(5,0)$ and to the $y$-axis at $(0,12)$. We say a line $\ell$ is $\mathcal{P}$-friendly if the $x$-axis, $y$-axis, and $\mathcal{P}$ divide $\ell$ into three segments, each of which has equal length. If the sum of the slopes of all $\mathcal{P}$-friendly lines can be written in the form $-\tfrac mn$ for $m$ and $n$ positive relatively prime integers, find $m+n$.
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.
2016 CMIMC, 8
Suppose $ABCD$ is a convex quadrilateral satisfying $AB=BC$, $AC=BD$, $\angle ABD = 80^\circ$, and $\angle CBD = 20^\circ$. What is $\angle BCD$ in degrees?
2016 CMIMC, 8
Brice is eating bowls of rice. He takes a random amount of time $t_1 \in (0,1)$ minutes to consume his first bowl, and every bowl thereafter takes $t_n = t_{n-1} + r_n$ minutes, where $t_{n-1}$ is the time it took him to eat his previous bowl and $r_n \in (0,1)$ is chosen uniformly and randomly. The probability that it takes Brice at least 12 minutes to eat 5 bowls of rice can be expressed as simplified fraction $\tfrac{m}{n}$. Compute $m+n$.
2016 CMIMC, 3
Sophia writes an algorithm to solve the graph isomorphism problem. Given a graph $G=(V,E)$, her algorithm iterates through all permutations of the set $\{v_1, \dots, v_{|V|}\}$, each time examining all ordered pairs $(v_i,v_j)\in V\times V$ to see if an edge exists. When $|V|=8$, her algorithm makes $N$ such examinations. What is the largest power of two that divides $N$?
2016 CMIMC, 2
For each integer $n\geq 1$, let $S_n$ be the set of integers $k > n$ such that $k$ divides $30n-1$. How many elements of the set \[\mathcal{S} = \bigcup_{i\geq 1}S_i = S_1\cup S_2\cup S_3\cup\ldots\] are less than $2016$?
2024 CMIMC Theoretical Computer Science, 3
In this problem, we explore a variant of the Monty Hall Problem.
There are $n$ doors numbered $1, \dots, n$. A single gold coin is placed randomly behind one of the doors, with the probability it is placed behind door $i$ equalling $p_i.$ There are $r$ "rounds" in which we may make at most $k$ "turns" each, defined as follows:
During a "turn", you pick two doors and send them to the game host. Then, the host picks one of the two doors in the following manner:
[list]
[*]If neither door contains the coin, the host randomly picks one with equal probability.
[*] If one of the doors contains the coin, the host picks the door which does not have the coin.
[/list]
The host reveals that the picked door does not contain the coin, and opens it.
A "round" consists of Alice performing at least 1 and at most $k$ turns. After all the turns in round $j$ are complete, suppose there are $d_j$ doors remaining. Bob will compute the probability of each individual door containing the coin. Let $m_j$ be the minimum of these probabilities computed during the $j$th round. Then, Bob awards Alice $d_jm_j$ points. Note that Bob will pay Alice $r$ times, and Alice's total payout is the sum of the $r$ individual payouts. Note that opened doors remain revealed between rounds.
Suppose $S$ is some strategy that determines which doors Alice sends to the host. Let $F(S, n,k,r,(p_1, \dots, p_n))$ be the minimum possible amount Alice could earn with strategy $S$ for parameters $(n,k,r,(p_1, \dots, p_n))$, and let \[G(n,k,r,(p_1, \dots, p_n))= \max\limits _S F(S, n,k,r,(p_1, \dots, p_n)).\]
Find all tuples $(n,k,r,(p_1, \dots, p_n))$ for which $G(n,k,r,(p_1, \dots, p_n))=r.$ You may find it useful to consider lists where each element of a list is at most double the prior element.
[i]Proposed by Hari Desikan[/i]
2016 CMIMC, 8
Let $r_1$, $r_2$, $\ldots$, $r_{20}$ be the roots of the polynomial $x^{20}-7x^3+1$. If \[\dfrac{1}{r_1^2+1}+\dfrac{1}{r_2^2+1}+\cdots+\dfrac{1}{r_{20}^2+1}\] can be written in the form $\tfrac mn$ where $m$ and $n$ are positive coprime integers, find $m+n$.
2016 CMIMC, 4
Given a list $A$, let $f(A) = [A[0] + A[1], A[0] - A[1]]$. Alef makes two programs to compute $f(f(...(f(A))))$, where the function is composed $n$ times:
\begin{tabular}{l|l}
1: \textbf{FUNCTION} $T_1(A, n)$ & 1: \textbf{FUNCTION} $T_2(A, n)$ \\
2: $\quad$ \textbf{IF} $n = 0$ & 2: $\quad$ \textbf{IF} $n = 0$ \\
3: $\quad$ $\quad$ \textbf{RETURN} $A$ & 3: $\quad$ $\quad$ \textbf{RETURN} $A$ \\
4: $\quad$ \textbf{ELSE} & 4: $\quad$ \textbf{ELSE} \\
5: $\quad$ $\quad$ \textbf{RETURN} $[T_1(A, n - 1)[0] + T_1(A, n - 1)[1],$ & 5: $\quad$ $\quad$ $B \leftarrow T_2(A, n - 1)$ \\
$\quad$ $\quad$ $\quad$ $T_1(A, n - 1)[0] - T_1(A, n - 1)[1]]$ & 6: $\quad$ $\quad$ \textbf{RETURN} $[B[0] + B[1], B[0] - B[1]]$ \\
\end{tabular}
Each time $T_1$ or $T_2$ is called, Alef has to pay one dollar. How much money does he save by calling $T_2([13, 37], 4)$ instead of $T_1([13, 37], 4)$?
2016 CMIMC, 5
Let $\mathcal{P}$ be a parallelepiped with side lengths $x$, $y$, and $z$. Suppose that the four space diagonals of $\mathcal{P}$ have lengths $15$, $17$, $21$, and $23$. Compute $x^2+y^2+z^2$.
2016 CMIMC, 2
Identical spherical tennis balls of radius 1 are placed inside a cylindrical container of radius 2 and height 19. Compute the maximum number of tennis balls that can fit entirely inside this container.
2016 CMIMC, 6
Define a $\textit{tasty residue}$ of $n$ to be an integer $1<a<n$ such that there exists an integer $m>1$ satisfying \[a^m\equiv a\pmod n.\] Find the number of tasty residues of $2016$.
2016 CMIMC, 1
In a race, people rode either bicycles with blue wheels or tricycles with tan wheels. Given that 15 more people rode bicycles than tricycles and there were 15 more tan wheels than blue wheels, what is the total number of people who rode in the race?
2016 CMIMC, 10
Let $\triangle ABC$ be a triangle with circumcircle $\Omega$ and let $N$ be the midpoint of the major arc $\widehat{BC}$. The incircle $\omega$ of $\triangle ABC$ is tangent to $AC$ and $AB$ at points $E$ and $F$ respectively. Suppose point $X$ is placed on the same side of $EF$ as $A$ such that $\triangle XEF\sim\triangle ABC$. Let $NX$ intersect $BC$ at a point $P$. Given that $AB=15$, $BC=16$, and $CA=17$, compute $\tfrac{PX}{XN}$.
2021 CMIMC Integration Bee, 2
$$\int\frac{\ln^2(x)}{x}\,dx$$
[i]Proposed by Connor Gordon[/i]
2016 CMIMC, 2
In concurrent computing, two processes may have their steps interwoven in an unknown order, as long as the steps of each process occur in order. Consider the following two processes:
\begin{tabular}{c|cc}
Process & $A$ & $B$\\
\hline
Step 1 & $x\leftarrow x-4$ & $x\leftarrow x-5$\\
Step 2 & $x\leftarrow x\cdot3$ & $x\leftarrow x\cdot4$\\
Step 3 & $x\leftarrow x-4$ & $x\leftarrow x-5$\\
Step 4 & $x\leftarrow x\cdot3$ & $x\leftarrow x\cdot4$
\end{tabular}
One such interweaving is $A1$, $B1$, $A2$, $B2$, $A3$, $B3$, $B4$, $A4$, but $A1$, $A3$, $A2$, $A4$, $B1$, $B2$, $B3$, $B4$ is not since the steps of $A$ do not occur in order. We run $A$ and $B$ concurrently with $x$ initially valued at $6$. Find the minimal possible value of $x$ among all interweavings.
2016 CMIMC, 7
Let $ABC$ be a triangle with incenter $I$ and incircle $\omega$. It is given that there exist points $X$ and $Y$ on the circumference of $\omega$ such that $\angle BXC=\angle BYC=90^\circ$. Suppose further that $X$, $I$, and $Y$ are collinear. If $AB=80$ and $AC=97$, compute the length of $BC$.
2016 CMIMC, 7
Determine the smallest positive prime $p$ which satisfies the congruence \[p+p^{-1}\equiv 25\pmod{143}.\] Here, $p^{-1}$ as usual denotes multiplicative inverse.