Let $X_1, X_2, \ldots$ be independent random variables of the same distribution such that their joint distribution is discrete and is concentrated on infinitely many different values. Let $a_n$ denote the probability that $X_1,\ldots, X_{n+1}$ are all different on the condition that $X_1,\ldots, X_n$ are all different ($n\ge 1$). Show that (a) $a_n$ is strictly decreasing and tends to $0$ as $n\to \infty$; and (b) for any sequence $1\le f(1)\le f(2) < \ldots$ of positive integers the joint distribution of $X_1, X_2, \ldots$ can be chosen such that $$\limsup_{n\to\infty}\frac{a_{f(n)}}{a_n}=1$$ holds.

Bob writes a random string of $5$ letters, where each letter is either $A, B, C,$ or $D$. The letter in each position is independently chosen, and each of the letters $A, B, C, D$ is chosen with equal probability. Given that there are at least two $A's$ in the string, find the probability that there are at least three $A's$ in the string.

A $3\times3$ square is partitioned into $9$ unit squares. Each unit square is painted either white or black with each color being equally likely, chosen independently and at random. The square is the rotated $90^\circ$ clockwise about its center, and every white square in a position formerly occupied by a black square is painted black. The colors of all other squares are left unchanged. What is the probability that the grid is now entirely black? $ \textbf{(A)}\ \dfrac{49}{512} \qquad\textbf{(B)}\ \dfrac{7}{64} \qquad\textbf{(C)}\ \dfrac{121}{1024} \qquad\textbf{(D)}\ \dfrac{81}{512} \qquad\textbf{(E)}\ \dfrac{9}{32} $

Joe, who is already feared by all bandits in the Wild West, would like to officially become a sheriff. To do that, he has to take a special exam where he has to demonstrate his talent in three different areas: tracking, shooting and lasso throwing. He successfully completes each task with a given probability, independently of each other. He passes the exam if he can complete at least two of the tasks successfully. Joe calculated that in case he starts with tracking and completes it successfully, his chance of passing the exam is $32\%$. If he starts with successful shooting, the chance of passing is $49\%$, whereas if he starts with successful lasso throwing, he passes with probability $52\%$. The overall probability of passing (calculated before the start of the exam) is $X/1000$ . What is the value of $X$?

The wheel shown is spun twice, and the randomly determined numbers opposite the pointer are recorded. The first number is divided by $ 4$, and the second number is divided by $ 5$. The first remainder designates a column, and the second remainder designates a row on the checkerboard shown. What is the probability that the pair of numbers designates a shaded square? [asy]unitsize(1.5cm); defaultpen(linewidth(.8pt)+fontsize(15pt)); draw(Circle(origin,1)); for(int i = 0;i < 6; ++i) { draw(origin--dir(60i+30)); } label("$7$",midpoint(origin--(dir(0))),E); label("$1$",midpoint(origin--(dir(60))),NE); label("$6$",midpoint(origin--(dir(120))),NW); label("$3$",midpoint(origin--(dir(180))),W); label("$9$",midpoint(origin--(dir(240))),SW); label("$2$",midpoint(origin--(dir(300))),SE); draw((2,0)--(3.5,0)--(3.5,1)--(2,1)--cycle); draw((2,0)--(3.5,0)--(3.5,-1)--(2,-1)--cycle); pair[] V = {(2.5,0.5),(2,0),(3,0),(2.5,-0.5),(2,-1),(3,-1)}; for(int i = 0; i <= 5; ++i) { pair A = V[i]; path p = A--(A.x,A.y + 0.5)--(A.x + 0.5,A.y + 0.5)--(A.x + 0.5, A.y)--cycle; fill(p,mediumgray); draw(p); } path pointer = (-2.5,-0.125)--(-2.5,0.125)--(-1.2,0.125)--(-1.05,0)--(-1.2,-0.125)--cycle; fill(pointer,mediumgray); draw(pointer); label("Pointer",(-1.85,0),fontsize(10pt)); label("$4$",(2,0.5),2N + 2W); label("$3$",(2,0),2N + 2W); label("$2$",(2,-0.5),2N + 2W); label("$1$",(2,-1),2N + 2W); label("$1$",(2,-1),2S + 2E); label("$2$",(2.5,-1),2S + 2E); label("$3$",(3,-1),2S + 2E);[/asy]$ \textbf{(A)}\ \frac {1}{3}\qquad \textbf{(B)}\ \frac {4}{9}\qquad \textbf{(C)}\ \frac {1}{2}\qquad \textbf{(D)}\ \frac {5}{9}\qquad \textbf{(E)}\ \frac {2}{3}$

A bug starts at one vertex of a cube and moves along the edges of the cube according to the following rule. At each vertex the bug will choose to travel along one of the three edges emanating from that vertex. Each edge has equal probability of being chosen, and all choices are independent. What is the probability that after seven moves the bug will have visited every vertex exactly once? $ \textbf{(A) } \frac {1}{2187} \qquad \textbf{(B) } \frac {1}{729} \qquad \textbf{(C) } \frac {2}{243} \qquad \textbf{(D) } \frac {1}{81} \qquad \textbf{(E) } \frac {5}{243}$

Suppose that $X\sim\operatorname{Uniform}(0,1)$ and $Y\sim\operatorname{Bernoulli}\left(\frac14\right)$, independently of each other. Let $Z=X+Y$. Then which of the following is true? $\textbf{(A)}~\text{The distribution of }Z\text{ is symmetric about }1$ $\textbf{(B)}~Z\text{ has a probability density function}$ $\textbf{(C)}~E(Z)=\frac54$ $\textbf{(D)}~P(Z\le1)=\frac14$

Steve stands in the middle of a field of an infinitely large chessboard, all of which are fields square and one square meter. Every second it randomly wanders into the middle one of the four neighboring fields, each of which has the same probability. How high is the probability that after $2015$ steps, he will have taken exactly five meters way from his starting square?

Three fair dice are tossed at random (i.e., all faces have the same probability of coming up). What is the probability that the three numbers turned up can be arranged to form an arithmetic progression with common difference one? $\textbf{(A) }\frac{1}{6}\qquad\textbf{(B) }\frac{1}{9}\qquad\textbf{(C) }\frac{1}{27}\qquad\textbf{(D) }\frac{1}{54}\qquad \textbf{(E) }\frac{7}{36}$

Let $n$ be a positive integer. Prove that the number of lines which go through the origin and precisely one other point with integer coordinates $(x,y),0\le x,y\le n$, is at least $\frac{n^2}{4}$.

Two teams are in a best-two-out-of-three playoff: the teams will play at most $3$ games, and the winner of the playoff is the first team to win $2$ games. The first game is played on Team A's home field, and the remaining games are played on Team B's home field. Team A has a $\frac{2}{3}$ chance of winning at home, and its probability of winning when playing away from home is $p$. Outcomes of the games are independent. The probability that Team A wins the playoff is $\frac{1}{2}$. Then $p$ can be written in the form $\frac{1}{2}(m - \sqrt{n})$, where $m$ and $n$ are positive integers. What is $m + n$? $\textbf{(A) } 10 \qquad \textbf{(B) } 11 \qquad \textbf{(C) } 12 \qquad \textbf{(D) } 13 \qquad \textbf{(E) } 14$

Rice University and Stanford University write questions and corresponding solutions for a high school math tournament. The Rice group writes 10 questions every hour but make a mistake in calculating their solutions 10% of the time. The Stanford group writes 20 problems every hour and makes solution mistakes 20% of the time. Each school works for 10 hours and then sends all problems to Smartie to be checked. However, Smartie isn’t really so smart, and only 75% of the problems she thinks are wrong are actually incorrect. Smartie thinks 20% of questions from Rice have incorrect solutions, and that 10% of questions from Stanford have incorrect solutions. This problem was definitely written and solved correctly. What is the probability that Smartie thinks its solution is wrong?

The [i]liar's guessing game[/i] is a game played between two players $A$ and $B$. The rules of the game depend on two positive integers $k$ and $n$ which are known to both players. At the start of the game $A$ chooses integers $x$ and $N$ with $1 \le x \le N.$ Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$. Player $B$ now tries to obtain information about $x$ by asking player $A$ questions as follows: each question consists of $B$ specifying an arbitrary set $S$ of positive integers (possibly one specified in some previous question), and asking $A$ whether $x$ belongs to $S$. Player $B$ may ask as many questions as he wishes. After each question, player $A$ must immediately answer it with [i]yes[/i] or [i]no[/i], but is allowed to lie as many times as she wants; the only restriction is that, among any $k+1$ consecutive answers, at least one answer must be truthful. After $B$ has asked as many questions as he wants, he must specify a set $X$ of at most $n$ positive integers. If $x$ belongs to $X$, then $B$ wins; otherwise, he loses. Prove that: 1. If $n \ge 2^k,$ then $B$ can guarantee a win. 2. For all sufficiently large $k$, there exists an integer $n \ge (1.99)^k$ such that $B$ cannot guarantee a win. [i]Proposed by David Arthur, Canada[/i]

Suppose that n numbers $x_1, x_2, . . . , x_n$ are chosen randomly from the set $\{1, 2, 3, 4, 5\}$. Prove that the probability that $x_1^2+ x_2^2 +\cdots+ x_n^2 \equiv 0 \pmod 5$ is at least $\frac 15.$

Given integers \( m, n \geq 2 \), the points \( A_1, A_2, \dots, A_n \) are chosen independently and uniformly at random on a circle of circumference \( 1 \). That is, for each \( i = 1, \dots, n \), for any \( x \in (0,1) \), and for any arc \( \mathcal{C} \) of length \( x \) on the circle, we have $\mathbb{P}(A_i \in \mathcal{C}) = x$. What is the probability that there exists an arc of length \( \frac{1}{m} \) on the circle that contains all the points \( A_1, A_2, \dots, A_n \)?

Let $A$, $B$, $C$, and $D$ be the vertices of a regular tetrahedron, each of whose edges measures 1 meter. A bug, starting from vertex $A$, observes the following rule: at each vertex it chooses one of the three edges meeting at that vertex, each edge being equally likely to be chosen, and crawls along that edge to the vertex at its opposite end. Let $p = n/729$ be the probability that the bug is at vertex $A$ when it has crawled exactly 7 meters. Find the value of $n$.

The figure shows a network of roads bounding $12$ blocks. Person $P$ goes from $A$ to $B,$ and person $Q$ goes from $B$ to $A,$ each going by a shortest path (along roads). The persons start simultaneously and go at the same constant speed. At each point with two possible directions to take, both have the same probability. Find the probability that the persons meet. [asy] import graph; size(150); real lsf = 0.5; pen dp = linewidth(0.7) + fontsize(10); defaultpen(dp); pen ds = black; draw((0,3)--(4,3),linewidth(1.2pt)); draw((4,3)--(4,0),linewidth(1.2pt)); draw((4,0)--(0,0),linewidth(1.2pt)); draw((0,0)--(0,3),linewidth(1.2pt)); draw((1,3)--(1,0),linewidth(1.2pt)); draw((2,3)--(2,0),linewidth(1.2pt)); draw((3,3)--(3,0),linewidth(1.2pt)); draw((0,1)--(4,1),linewidth(1.2pt)); draw((4,2)--(0,2),linewidth(1.2pt)); dot((0,0),ds); label("$A$", (-0.3,-0.36),NE*lsf); dot((4,3),ds); label("$B$", (4.16,3.1),NE*lsf); clip((-4.3,-10.94)--(-4.3,6.3)--(16.18,6.3)--(16.18,-10.94)--cycle); [/asy]

A particle moves from $(0, 0)$ to $(n, n)$ directed by a fair coin. For each head it moves one step east and for each tail it moves one step north. At $(n, y), y < n$, it stays there if a head comes up and at $(x, n), x < n$, it stays there if a tail comes up. Let$ k$ be a fixed positive integer. Find the probability that the particle needs exactly $2n+k$ tosses to reach $(n, n).$

Let $n,k$ be given positive integers with $n>k$. Prove that: \[ \frac{1}{n+1} \cdot \frac{n^n}{k^k (n-k)^{n-k}} < \frac{n!}{k! (n-k)!} < \frac{n^n}{k^k(n-k)^{n-k}} \]

There is a test for the dangerous bifurcation virus that is $ 99\%$ accurate. In other words, if someone has the virus, there is a $ 99\%$ chance that the test will be positive, and if someone does not have it, then there is a $ 99\%$ chance the test will be negative. Assume that exactly $ 1\%$ of the general population has the virus. Given an individual that has tested positive from this test, what is the probability that he or she actually has the disease? Express your answer as a percentage.

Two standard six-sided dice are tossed. What is the probability that the sum of the numbers is greater than $7$? $\text{(A) }1\qquad\text{(B) }\frac{5}{12}\qquad\text{(C) }\frac{2}{3}\qquad\text{(D) }\frac{4}{9}\qquad\text{(E) }\frac{7}{36}$

Amelia has $27$ unit cubes. She selects one and paints one of its faces. She then randomly glues all $27$ cubes together to form a $3 \times 3 \times 3$ cube (with all possible arrangements of the unit cubes being equally likely). Compute the probability that the resulting cube appears unpainted.

A coastal battery sights an enemy cruiser lying one kilometer off the coast and opens fire on it at the rate of one round per minute. After the first shot, the cruiser begins to move away at a speed of $ 60$ kilometers an hour. Let the probability of a hit be $ 0.75x^{ \minus{} 2}$, where $ x$ denotes the distance (in kilometers) between the cruiser and the coast ($ x\geq 1$), and suppose that the battery goes on firing till the cruiser either sinks or disappears. Further, let the probability of the cruiser sinking after $ n$ hits be $ 1 \minus{} \frac {1}{4^n}$ ($ n \equal{} 0,1,...$). Show that the probability of the cruiser escaping is $ \frac {2\sqrt {2}}{3\pi}$

A square is drawn in the Cartesian coordinate plane with vertices at $(2,2)$, $(-2,2)$, $(-2,-2)$, and $(2,-2)$. A particle starts at $(0,0)$. Every second it moves with equal probability to one of the eight lattice points (points with integer coordinates) closest to its current position, independently of its previous moves. In other words, the probability is $\frac{1}{8}$ that the particle will move from $(x,y)$ to each of $(x,y+1)$, $(x+1,y+1)$, $(x+1,y)$, $(x+1,y-1)$, $(x,y-1)$, $(x-1,y-1)$, $(x-1,y)$, $(x-1,y+1)$. The particle will eventually hit the square for the first time, either at one of the $4$ corners of the square or one of the $12$ lattice points in the interior of one of the sides of the square. The probability that it will hit at a corner rather than at an interior point of a side is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. What is $m+n$? $\textbf{(A)}\ 4\qquad\textbf{(B)}\ 5\qquad\textbf{(C)}\ 7\qquad\textbf{(D)}\ 15\qquad\textbf{(E)}\ 39$

A Vandal and a Moderator are editing a Wikipedia article. The article originally is error-free. Each day, the Vandal introduces one new error into the Wikipedia article. At the end of the day, the moderator checks the article and has a $ 2/3$ chance of catching each individual error still in the article. After $ 3$ days, what is the probability that the article is error-free?