Practice (Difficult)

back to index  |  new

Consider all $1000$-element subsets of the set $\{1, 2, 3, ... , 2015\}$. From each such subset choose the least element. Find the arithmetic mean of all of these least elements.


Call a permutation $a_1, a_2, \ldots, a_n$ of the integers $1, 2, \ldots, n$ quasi-increasing if $a_k \leq a_{k+1} + 2$ for each $1 \leq k \leq n-1$. For example, $53421$ and $14253$ are quasi-increasing permutations of the integers $1$, $2$, $3$, $4$, $5$, but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1$, $2$, $\ldots$, $7$.

A token starts at the point $(0,0)$ of an $xy$-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. Find the probability the token ends at a point on the graph of $|y|=|x|$.


Let $A={1,2,3,4}$, and $f$ and $g$ be randomly chosen (not necessarily distinct) functions from $A$ to $A$. Find the probability that the range of $f$ and the range of $g$ are disjoint.

Suppose that the angles of $\triangle ABC$ satisfy $cos(3A)+cos(3B)+cos(3C)=1.$ Two sides of the triangle have lengths $10$ and $13$. There is a positive integer $m$ so that the maximum possible length for the remaining side of $\triangle ABC$ is $\sqrt{m}$. Find $m$.


Find all prime number $p$ such that both $(4p^2+1)$ and $(6p^2+1)$ are prime numbers.

Find $n$ different positive integers such that any two of them are relatively prime, but the sum of any $k$ ($k < n$) of them is a composite number.


Ms. Math's kindergarten class has $16$ registered students. The classroom has a very large number, $N$, of play blocks which satisfies the conditions:

  • If $16$, $15$, or $14$ students are present in the class, then in each case all the blocks can be distributed in equal numbers to each student, and
  • There are three integers $0 < x < y < z < 14$ such that when $x$, $y$, or $z$ students are present and the blocks are distributed in equal numbers to each student, there are exactly three blocks left over.

Find the sum of the distinct prime divisors of the least possible value of $N$ satisfying the above conditions.


For $\pi \le \theta < 2\pi$, let\begin{align*} P &= \frac12\cos\theta - \frac14\sin 2\theta - \frac18\cos 3\theta + \frac{1}{16}\sin 4\theta + \frac{1}{32} \cos 5\theta - \frac{1}{64} \sin 6\theta - \frac{1}{128} \cos 7\theta + \cdots \end{align*} and \begin{align*} Q &= 1 - \frac12\sin\theta -\frac14\cos 2\theta + \frac18 \sin 3\theta + \frac{1}{16}\cos 4\theta - \frac{1}{32}\sin 5\theta - \frac{1}{64}\cos 6\theta +\frac{1}{128}\sin 7\theta + \cdots \end{align*} so that $\frac{P}{Q} = \frac{2\sqrt2}{7}$. Then $\sin\theta = -\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$.


Let $N$ be the number of ordered triples $(A,B,C)$ of integers satisfying the conditions:

  • $0\le A < B < C \le 99$,
  • there exist integers $a$, $b$, and $c$, and prime $p$ where $0\le b < a < c < p$,
  • $p$ divides $(A-a)$, $(B-b)$, and $(C-c)$, and
  • each ordered triple $(A,B,C)$ and each ordered triple $(b,a,c)$ form arithmetic sequences.

Find $N$.


A $7\times 1$ board is completely covered by $m\times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let $N$ be the number of tilings of the $7\times 1$ board in which all three colors are used at least once. For example, a $1\times 1$ red tile followed by a $2\times 1$ green tile, a $1\times 1$ green tile, a $2\times 1$ blue tile, and a $1\times 1$ green tile is a valid tiling. Note that if the $2\times 1$ blue tile is replaced by two $1\times 1$ blue tiles, this results in a different tiling. Find $N$.

Let $A,B,C$ be angles of an acute triangle with $$ \cos^2 A + \cos^2 B + 2 \sin A \sin B \cos C = \frac{15}{8}$$ and $$\cos^2 B + \cos^2 C + 2 \sin B \sin C \cos A = \frac{14}{9}$$ There are positive integers $p$, $q$, $r$, and $s$ for which \[\cos^2 C + \cos^2 A + 2 \sin C \sin A \cos B = \frac{p-q\sqrt{r}}{s},\] where $p+q$ and $s$ are relatively prime and $r$ is not divisible by the square of any prime. Find $p+q+r+s$.


Let $\mathcal{S}$ be the set of all perfect squares whose rightmost three digits in base $10$ are $256$. Let $\mathcal{T}$ be the set of all numbers of the form $\frac{x-256}{1000}$, where $x$ is in $\mathcal{S}$. In other words, $\mathcal{T}$ is the set of numbers when the last three digits of each number in $\mathcal{S}$ are truncated. Find the remainder when the tenth smallest element of $\mathcal{T}$ is divided by $1000$.


Let $x$ and $y$ be real numbers such that $\frac{\sin x}{\sin y} = 3$ and $\frac{\cos x}{\cos y} = \frac12$. The value of $\frac{\sin 2x}{\sin 2y} + \frac{\cos 2x}{\cos 2y}$ can be expressed in the form $\frac pq$, where $p$ and $q$ are relatively prime positive integers. Find $p+q$.


For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is $\{ 3, 4, 5, 6, 7, 13, 14, 15, 16, 17, 23, \ldots\}$. Find the number of positive integers less than or equal to $10,000$ which are simultaneously $7$-safe, $11$-safe, and $13$-safe.

  • In a group of nine people each person shakes hands with exactly two of the other people from the group. Let $N$ be the number of ways this handshaking can occur. Consider two handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. Find $N$.

Let $R$ be the set of all possible remainders when a number of the form $2^n$, where $n$ is a non-negative integer, is divided by $1000$. Let $S$ be the sum of the elements in $R$. Find the remainder when $S$ is divided by $1000$.

Six men and some number of women stand in a line in random order. Let $p$ be the probability that a group of at least four men stand together in the line, given that every man stands next to at least one other man. Find the least number of women in the line such that $p$ does not exceed $1$ percent.

Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Find the probability that each delegate sits next to at least one delegate from another country.


In a small pond there are eleven lily pads in a row labeled $0$ through $10$. A frog is sitting on pad $1$. When the frog is on pad $N$, $0 < N < 10$, it will jump to pad $(N-1)$ with probability $\frac{N}{10}$ and to pad $(N+1)$ with probability $1-\frac{N}{10}$. Each jump is independent of the previous jumps. If the frog reaches pad $0$ it will be eaten by a patiently waiting snake. If the frog reaches pad $10$ it will exit the pond, never to return. What is the probability that the frog will escape without being eaten by the snake?

The number $2017$ is prime. Let $S = \sum \limits_{k=0}^{62} \dbinom{2014}{k}$. What is the remainder when $S$ is divided by $2017$?

Define the function $f_1$ on the positive integers by setting $f_1(1)=1$ and if $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is the prime factorization of $n>1$, then \[f_1(n)=(p_1+1)^{e_1-1}(p_2+1)^{e_2-1}\cdots (p_k+1)^{e_k-1}.\] For every $m\ge 2$, let $f_m(n)=f_1(f_{m-1}(n))$. For how many $N$ in the range $1\le N\le 400$ is the sequence $(f_1(N),f_2(N),f_3(N),\dots )$ unbounded? Note: A sequence of positive numbers is unbounded if for every integer $B$, there is a member of the sequence greater than $B$.


A parking lot has $16$ spaces in a row. Twelve cars arrive, each of which requires one parking space, and their drivers chose spaces at random from among the available spaces. Auntie Em then arrives in her SUV, which requires $2$ adjacent spaces. What is the probability that she is able to park?

Eight people are sitting around a circular table, each holding a fair coin. All eight people flip their coins and those who flip heads stand while those who flip tails remain seated. What is the probability that no two adjacent people will stand?

Let $S$ be a square of side length $1$. Two points are chosen independently at random on the sides of $S$. Find the probability that the straight-line distance between the points is at least $\dfrac{1}{2}$.