Putnam Archive — Probability

Consider a circle $\Omega$ with radius 9 and center at the origin $(0,0)$, and a disc $\Delta$ with radius 1 and center at $(r,0)$, where $0 \leq r \leq 8$. Two points $P$ and $Q$ are chosen independently and uniformly at random on $\Omega$. Which value(s) of $r$ minimize the probability that the chord $\overline{PQ}$ intersects $\Delta$?

Let $n$ be a positive integer. Set $a_{n,0} = 1$. For $k \geq 0$, choose an integer $m_{n,k}$ uniformly at random from the set $\{1,\dots,n\}$, and let $$a_{n,k+1} = \begin{cases} a_{n,k} + 1, & \mbox{if $m_{n,k} > a_{n,k};$} \\ a_{n,k}, & \mbox{if $m_{n,k} = a_{n,k}$;} \\ a_{n,k}-1, & \mbox{if $m_{n,k} < a_{n,k}$.} \end{cases}$$ Let $E(n)$ be the expected value of $a_{n,n}$. Determine $\lim_{n\to \infty} E(n)/n$.

A sequence $y_1,y_2,\dots,y_k$ of real numbers is called zigzag if $k=1$, or if $y_2-y_1, y_3-y_2, \dots, y_k-y_{k-1}$ are nonzero and alternate in sign. Let $X_1,X_2,\dots,X_n$ be chosen independently from the uniform distribution on $[0,1]$. Let $a(X_1,X_2,\dots,X_n)$ be the largest value of $k$ for which there exists an increasing sequence of integers $i_1,i_2,\dots,i_k$ such that $X_{i_1},X_{i_2},\dots,X_{i_k}$ is zigzag. Find the expected value of $a(X_1,X_2,\dots,X_n)$ for $n \geq 2$.

Suppose that $X_1, X_2, \dots$ are real numbers between 0 and 1 that are chosen independently and uniformly at random. Let $S = \sum_{i=1}^k X_i/2^i$, where $k$ is the least positive integer such that $X_k < X_{k+1}$, or $k = \infty$ if there is no such integer. Find the expected value of $S$.

For $0 \leq p \leq 1/2$, let $X_1, X_2, \dots$ be independent random variables such that $$X_i = \begin{cases} 1 & \mbox{with probability $p$,} \\ -1 & \mbox{with probability $p$,} \\ 0 & \mbox{with probability $1-2p$,} \end{cases}$$ for all $i \geq 1$. Given a positive integer $n$ and integers $b, a_1, \dots, a_n$, let $P(b, a_1, \dots, a_n)$ denote the probability that $a_1 X_1 + \cdots + a_n X_n = b$. For which values of $p$ is it the case that $$P(0, a_1, \dots, a_n) \geq P(b, a_1, \dots, a_n)$$ for all positive integers $n$ and all integers $b, a_1, \dots, a_n$?

Suppose that the plane is tiled with an infinite checkerboard of unit squares. If another unit square is dropped on the plane at random with position and orientation independent of the checkerboard tiling, what is the probability that it does not cover any of the corners of the squares of the checkerboard?

Given an ordered list of $3N$ real numbers, we can trim it to form a list of $N$ numbers as follows: We divide the list into $N$ groups of $3$ consecutive numbers, and within each group, discard the highest and lowest numbers, keeping only the median.

Consider generating a random number $X$ by the following procedure: Start with a list of $3^{2021}$ numbers, drawn independently and uniformly at random between 0 and 1. Then trim this list as defined above, leaving a list of $3^{2020}$ numbers. Then trim again repeatedly until just one number remains; let $X$ be this number. Let $\mu$ be the expected value of $|X - \frac{1}{2}|$. Show that $$\mu \geq \frac{1}{4} \left( \frac{2}{3} \right)^{2021}.$$

Consider a horizontal strip of $N+2$ squares in which the first and the last square are black and the remaining $N$ squares are all white. Choose a white square uniformly at random, choose one of its two neighbors with equal probability, and color this neighboring square black if it is not already black. Repeat this process until all the remaining white squares have only black neighbors. Let $w(N)$ be the expected number of white squares remaining. Find $$\lim_{N \to \infty} \frac{w(N)}{N}.$$

Let $x_0 = 1$, and let $\delta$ be some constant satisfying $0 < \delta < 1$. Iteratively, for $n=0,1,2,\dots$, a point $x_{n+1}$ is chosen uniformly from the interval $[0, x_n]$. Let $Z$ be the smallest value of $n$ for which $x_n < \delta$. Find the expected value of $Z$, as a function of $\delta$.

Let $n$ be a positive integer, and let $V_n$ be the set of integer $(2n+1)$-tuples $\mathbf{v} = (s_0, s_1, \cdots, s_{2n-1}, s_{2n})$ for which $s_0 = s_{2n} = 0$ and $|s_j - s_{j-1}| = 1$ for $j=1,2,\cdots,2n$. Define $$q(\mathbf{v}) = 1 + \sum_{j=1}^{2n-1} 3^{s_j},$$ and let $M(n)$ be the average of $\frac{1}{q(\mathbf{v})}$ over all $\mathbf{v} \in V_n$. Evaluate $M(2020)$.

Each of the integers from $1$ to $n$ is written on a separate card, and then the cards are combined into a deck and shuffled. Three players, $A$, $B$, and $C$, take turns in the order $A,B,C,A,\dots$ choosing one card at random from the deck. (Each card in the deck is equally likely to be chosen.) After a card is chosen, that card and all higher-numbered cards are removed from the deck, and the remaining cards are reshuffled before the next turn. Play continues until one of the three players wins the game by drawing the card numbered $1$.

Show that for each of the three players, there are arbitrarily large values of $n$ for which that player has the highest probability among the three players of winning the game.

Let $A$ be a $2n \times 2n$ matrix, with entries chosen independently at random. Every entry is chosen to be 0 or 1, each with probability $1/2$. Find the expected value of $\det(A-A^t)$ (as a function of $n$), where $A^t$ is the transpose of $A$.

Suppose $X$ is a random variable that takes on only nonnegative integer values, with $E\left[ X \right] = 1$, $E\left[ X^2 \right] = 2$, and $E \left[ X^3 \right] = 5$. (Here $E\left[ y \right]$ denotes the expectation of the random variable $Y$.) Determine the smallest possible value of the probability of the event $X=0$.

Let $G$ be an abelian group with $n$ elements, and let $$\{g_1=e,g_2,\dots,g_k\} \subsetneqq G$$ be a (not necessarily minimal) set of distinct generators of $G$. A special die, which randomly selects one of the elements $g_1,g_2,...,g_k$ with equal probability, is rolled $m$ times and the selected elements are multiplied to produce an element $g \in G$. Prove that there exists a real number $b \in (0,1)$ such that

$$\lim_{m\to\infty} \frac{1}{b^{2m}} \sum_{x\in G} \left(\mathrm{Prob}(g=x) - \frac{1}{n}\right)^2$$ is positive and finite.

Let $k$ be a positive integer. Suppose that the integers $1, 2, 3, \dots, 3k+1$ are written down in random order. What is the probability that at no time during this process, the sum of the integers that have been written up to that time is a positive integer divisible by 3? Your answer should be in closed form, but may include factorials.

Four points are chosen uniformly and independently at random in the interior of a given circle. Find the probability that they are the vertices of a convex quadrilateral.

Let $n$ be given, $n \geq 4$, and suppose that $P_1, P_2, \dots, P_n$ are $n$ randomly, independently and uniformly, chosen points on a circle. Consider the convex $n$-gon whose vertices are the $P_i$. What is the probability that at least one of the vertex angles of this polygon is acute?

An $m \times n$ checkerboard is colored randomly: each square is independently assigned red or black with probability $1/2$. We say that two squares, $p$ and $q$, are in the same connected monochromatic region if there is a sequence of squares, all of the same color, starting at $p$ and ending at $q$, in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater than $m n / 8$.

Shanille O'Keal shoots free throws on a basketball court. She hits the first and misses the second, and thereafter the probability that she hits the next shot is equal to the proportion of shots she has hit so far. What is the probability she hits exactly 50 of her first 100 shots?

An integer $n$, unknown to you, has been randomly chosen in the interval $[1, 2002]$ with uniform probability. Your objective is to select $n$ in an odd number of guesses. After each incorrect guess, you are informed whether $n$ is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than $2/3$.

You have coins $C_1,C_2,\ldots,C_n$. For each $k$, $C_k$ is biased so that, when tossed, it has probability $1/(2k+1)$ of falling heads. If the $n$ coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of $n$.

Suppose that each of $n$ people writes down the numbers 1,2,3 in random order in one column of a $3 \times n$ matrix, with all orders equally likely and with the orders for different columns independent of each other. Let the row sums $a,b,c$ of the resulting matrix be rearranged (if necessary) so that $a \leq b \leq c$. Show that for some $n \geq 1995$, it is at least four times as likely that both $b=a+1$ and $c=a+2$ as that $a=b=c$.

Consider the following game played with a deck of $2n$ cards numbered from 1 to $2n$. The deck is randomly shuffled and $n$ cards are dealt to each of two players. Beginning with $A$, the players take turns discarding one of their remaining cards and announcing its number. The game ends as soon as the sum of the numbers on the discarded cards is divisible by $2n+1$. The last person to discard wins the game. Assuming optimal strategy by both $A$ and $B$, what is the probability that $A$ wins?

Two real numbers $x$ and $y$ are chosen at random in the interval (0,1) with respect to the uniform distribution. What is the probability that the closest integer to $x/y$ is even? Express the answer in the form $r+s\pi$, where $r$ and $s$ are rational numbers.

Four points are chosen at random on the surface of a sphere. What is the probability that the center of the sphere lies inside the tetrahedron whose vertices are at the four points? (It is understood that each point is independently chosen relative to a uniform distribution on the sphere.)

If $\alpha$ is an irrational number, $0 < \alpha < 1$, is there a finite game with an honest coin such that the probability of one player winning the game is $\alpha$? (An honest coin is one for which the probability of heads and the probability of tails are both $\frac12$. A game is finite if with probability 1 it must end in a finite number of moves.)

A dart, thrown at random, hits a square target. Assuming that any two parts of the target of equal area are equally likely to be hit, find the probability that the point hit is nearer to the center than to any edge. Express your answer in the form $\displaystyle{\frac{a\sqrt{b} + c}{d}}$, where $a,\,b,\,c,\,d$ are integers.

Let $(x_1,\,x_2,\,\ldots\,x_n)$ be a point chosen at random from the $n$-dimensional region defined by $0<x_1<x_2<\cdots < x_n<1.$ Let $f$ be a continuous function on $[0,1]$ with $f(1)=0$. Set $x_0=0$ and $x_{n+1}=1$. Show that the expected value of the Riemann sum $$\sum_{i=0}^n (x_{i+1}-x_i) f(x_{i+1})$$ is $\int_0^1 f(t)P(t)\, dt$, where $P$ is a polynomial of degree $n$, independent of $f$, with $0\le P(t)\le 1$ for $0\le t \le 1$.

Let $C$ be the unit circle $x^2+y^2=1$. A point $p$ is chosen randomly on the circumference $C$ and another point $q$ is chosen randomly from the interior of $C$ (these points are chosen independently and uniformly over their domains). Let $R$ be the rectangle with sides parallel to the $x$ and $y$-axes with diagonal $pq$. What is the probability that no point of $R$ lies outside of $C$?