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

Let $X$ be a set with $n$ elements, and let $A_{1}$, $A_{2}$, ..., $A_{m}$ be subsets of $X$ such that: 1) $|A_{i}|=3$ for every $i\in\left\{1,2,...,m\right\}$; 2) $|A_{i}\cap A_{j}|\leq 1$ for all $i,j\in\left\{1,2,...,m\right\}$ such that $i \neq j$. Prove that there exists a subset $A$ of $X$ such that $A$ has at least $\left[\sqrt{2n}\right]$ elements, and for every $i\in\left\{1,2,...,m\right\}$, the set $A$ does not contain $A_{i}$. [i]Alternative formulation.[/i] Let $X$ be a finite set with $n$ elements and $A_{1},A_{2},\ldots, A_{m}$ be three-elements subsets of $X$, such that $|A_{i}\cap A_{j}|\leq 1$, for every $i\neq j$. Prove that there exists $A\subseteq X$ with $|A|\geq \lfloor \sqrt{2n}\rfloor$, such that none of $A_{i}$'s is a subset of $A$.

A knight is placed at the origin of the Cartesian plane. Each turn, the knight moves in an chess $\text{L}$-shape ($2$ units parallel to one axis and $1$ unit parallel to the other) to one of eight possible location, chosen at random. After $2016$ such turns, what is the expected value of the square of the distance of the knight from the origin?

Ranu starts with one standard die on a table. At each step, she rolls all the dice on the table: if all of them show a 6 on top, then she places one more die on the table; otherwise, she does nothing more on this step. After 2013 such steps, let $D$ be the number of dice on the table. What is the expected value (average value) of $6^D$?

For a permutation $\pi$ of $\{1,2,3,\ldots,n\}$, let $\text{Inv}(\pi)$ be the number of pairs $(i,j)$ with $1 \leq i < j \leq n$ and $\pi(i) > \pi(j)$. [list=1] [*] Given $n$, what is $\sum \text{Inv}(\pi)$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$? [*] Given $n$, what is $\sum \left(\text{Inv}(\pi)\right)^2$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$?[/list] [i]Brian Hamrick.[/i]

Rachel the unicorn lives on the numberline at the number $0$. One day, Rachel decides she’d like to travel the world and visit the numbers $1, 2, 3, \ldots, 31$. She starts off at the number $0$, with a list of the numbers she wants to visit: $1, 2, 3, \ldots , 31$. Rachel then picks one of the numbers on her list uniformly at random, crosses it off the list, and travels to that number in a straight line path. She repeats this process until she has crossed off and visited all thirty-one of the numbers from her original list. At the end of her trip, she returns to her home at $0$. What is the expected length of Rachel’s round trip?

Let $ y_0$ be chosen randomly from $ \{0, 50\}$, let $ y_1$ be chosen randomly from $ \{40, 60, 80\}$, let $ y_2$ be chosen randomly from $ \{10, 40, 70, 80\}$, and let $ y_3$ be chosen randomly from $ \{10, 30, 40, 70, 90\}$. (In each choice, the possible outcomes are equally likely to occur.) Let $ P$ be the unique polynomial of degree less than or equal to $ 3$ such that $ P(0) \equal{} y_0$, $ P(1) \equal{} y_1$, $ P(2) \equal{} y_2$, and $ P(3) \equal{} y_3$. What is the expected value of $ P(4)$?

Given are natural numbers $n>m>1$. We draw $m$ numbers from the set $\{1,2,...,n\}$ one by one without putting the drawn numbers back. Find the expected value of the difference between the largest and the smallest of the drawn numbers.

Let $S=\{1,2\dots,n\}$ for some integer $n>1.$ Say a permutation $\pi$ of $S$ has a local maximum at $k\in S$ if \[\begin{array}{ccc}\text{(i)}&\pi(k)>\pi(k+1)&\text{for }k=1\\ \text{(ii)}&\pi(k-1)<\pi(k)\text{ and }\pi(k)>\pi(k+1)&\text{for }1<k<n\\ \text{(iii)}&\pi(k-1)M\pi(k)&\text{for }k=n\end{array}\] (For example, if $n=5$ and $\pi$ takes values at $1,2,3,4,5$ of $2,1,4,5,3,$ then $\pi$ has a local maximum of $2$ as $k=1,$ and a local maximum at $k-4.$) What is the average number of local maxima of a permutation of $S,$ averaging over all permuatations of $S?$

Johann has $64$ fair coins. He flips all the coins. Any coin that lands on tails is tossed again. Coins that land on tails on the second toss are tossed a third time. What is the expected number of coins that are now heads? $\textbf{(A) } 32 \qquad\textbf{(B) } 40 \qquad\textbf{(C) } 48 \qquad\textbf{(D) } 56 \qquad\textbf{(E) } 64 $

Prove that from an $n\times n$ grid, one can find $\Omega (n^{\frac{5}{3}})$ points such that no four of them are vertices of a square with sides parallel to lines of the grid. Imagine yourself as Erdos (!) and guess what is the best exponent instead of $\frac{5}{3}$!

If two distinct integers from $1$ to $50$ inclusive are chosen at random, what is the expected value of their product? Note: The expectation is defined as the sum of the products of probability and value, i.e., the expected value of a coin flip that gives you $\$10$ if head and $\$5$ if tail is $\tfrac12\times\$10+\tfrac12\times\$5=\$7.5$.

An unbiased coin is tossed $n$ times. What is the expected value of $|H-T|$, where $H$ is the number of heads and $T$ is the number of tails?

Bhairav the Bat lives next to a town where $12.5$% of the inhabitants have Type AB blood. When Bhairav the Bat leaves his cave at night to suck of the inhabitants blood, chooses individuals at random until he bites one with type AB blood, after which he stops. What is the expected value of the number of individuals Bhairav the Bat will bite in any given night? [i]2015 CCA Math Bonanza Lightning Round #3.1[/i]

Let $ S$ be a finite set of points in the plane such that no three of them are on a line. For each convex polygon $ P$ whose vertices are in $ S$, let $ a(P)$ be the number of vertices of $ P$, and let $ b(P)$ be the number of points of $ S$ which are outside $ P$. A line segment, a point, and the empty set are considered as convex polygons of $ 2$, $ 1$, and $ 0$ vertices respectively. Prove that for every real number $ x$ \[\sum_{P}{x^{a(P)}(1 \minus{} x)^{b(P)}} \equal{} 1,\] where the sum is taken over all convex polygons with vertices in $ S$. [i]Alternative formulation[/i]: Let $ M$ be a finite point set in the plane and no three points are collinear. A subset $ A$ of $ M$ will be called round if its elements is the set of vertices of a convex $ A \minus{}$gon $ V(A).$ For each round subset let $ r(A)$ be the number of points from $ M$ which are exterior from the convex $ A \minus{}$gon $ V(A).$ Subsets with $ 0,1$ and 2 elements are always round, its corresponding polygons are the empty set, a point or a segment, respectively (for which all other points that are not vertices of the polygon are exterior). For each round subset $ A$ of $ M$ construct the polynomial \[ P_A(x) \equal{} x^{|A|}(1 \minus{} x)^{r(A)}. \] Show that the sum of polynomials for all round subsets is exactly the polynomial $ P(x) \equal{} 1.$ [i]Proposed by Federico Ardila, Colombia[/i]

You roll three fair six-sided dice. Given that the highest number you rolled is a $5$, the expected value of the sum of the three dice can be written as $\tfrac ab$ in simplest form. Find $a+b$.

Katie begins juggling five balls. After every second elapses, there is a chance she will drop a ball. If she is currently juggling $ k$ balls, this probability is $ \frac{k}{10}$. Find the expected number of seconds until she has dropped all the balls.

Let $S = \{(x, y) : x, y \in \{1, 2, 3, \dots, 2012\}\}$. For all points $(a, b)$, let $N(a, b) = \{(a - 1, b), (a + 1, b), (a, b - 1), (a, b + 1)\}$. Kathy constructs a set $T$ by adding $n$ distinct points from $S$ to $T$ at random. If the expected value of $\displaystyle \sum_{(a, b) \in T} | N(a, b) \cap T |$ is 4, then compute $n$. [i]Proposed by Lewis Chen[/i]

Marko lives on the origin of the Cartesian plane. Every second, Marko moves $1$ unit up with probability $\tfrac{2}{9}$, $1$ unit right with probability $\tfrac{2}{9}$, $1$ unit up and $1$ unit right with probability $\tfrac{4}{9}$, and he doesn’t move with probability $\tfrac{1}{9}$. After $2019$ seconds, Marko ends up on the point $(A, B)$. What is the expected value of $A\cdot B$?

Five balls are arranged around a circle. Chris chooses two adjacent balls at random and interchanges them. Then Silva does the same, with her choice of adjacent balls to interchange being independent of Chris's. What is the expected number of balls that occupy their original positions after these two successive transpositions? $(\textbf{A})\: 1.6\qquad(\textbf{B}) \: 1.8\qquad(\textbf{C}) \: 2.0\qquad(\textbf{D}) \: 2.2\qquad(\textbf{E}) \: 2.4$

Among $100$ points in the plane, no three collinear, exactly $4026$ pairs are connected by line segments. Each point is then randomly assigned an integer from $1$ to $100$ inclusive, each equally likely, such that no integer appears more than once. Find the expected value of the number of segments which join two points whose labels differ by at least $50$. [i]Proposed by Evan Chen[/i]

A robot on the number line starts at $1$. During the first minute, the robot writes down the number $1$. Each minute thereafter, it moves by one, either left or right, with equal probability. It then multiplies the last number it wrote by $n/t$, where $n$ is the number it just moved to, and $t$ is the number of minutes elapsed. It then writes this number down. For example, if the robot moves right during the second minute, it would write down $2/2=1$. Find the expected sum of all numbers it writes down, given that it is finite. [i]Proposed by Ethan Tan[/i]

Let $K{}$ be an equilateral triangle of unit area, and choose $n{}$ independent random points uniformly from $K{}$. Let $K_n$ be the intersection of all translations of $K{}$ that contain all the selected points. Determine the expected value of the area of $K_n.$

An equilateral triangle is tiled with $n^2$ smaller congruent equilateral triangles such that there are $n$ smaller triangles along each of the sides of the original triangle. For each of the small equilateral triangles, we randomly choose a vertex $V$ of the triangle and draw an arc with that vertex as center connecting the midpoints of the two sides of the small triangle with $V$ as an endpoint. Find, with proof, the expected value of the number of full circles formed, in terms of $n.$ [img]http://s3.amazonaws.com/classroom.artofproblemsolving.com/Images/Transcripts/497b4e1ef5043a84b433a5c52c4be3ae.png[/img]

You are tossing an unbiased coin. The last $ 28 $ consecutive flips have all resulted in heads. Let $ x $ be the expected number of additional tosses you must make before you get $ 60 $ consecutive heads. Find the sum of all distinct prime factors in $ x $.