A [i]triangulation[/i] of a polygon is a subdivision of the polygon into triangles meeting edge to edge, with the property that the set of triangle vertices coincides with the set of vertices of the polygon. Adam randomly selects a triangulation of a regular $180$-gon. Then, Bob selects one of the $178$ triangles in this triangulation. The expected number of $1^\circ$ angles in this triangle can be expressed as $\frac{a}{b}$, where $a$ and $b$ are relatively prime positive integers. Compute $100a + b$. [i]Proposed by Lewis Chen[/i]

A dog has three trainers: [list] [*]The first trainer gives him a treat right away. [*]The second trainer makes him jump five times, then gives him a treat. [*]The third trainer makes him jump three times, then gives him no treat. [/list] The dog will keep picking trainers with equal probability until he gets a treat. (The dog's memory isn't so good, so he might pick the third trainer repeatedly!) What is the expected number of times the dog will jump before getting a treat?

In chess, there are two types of minor pieces, the bishop and the knight. A bishop may move along a diagonal, as long as there are no pieces obstructing its path. A knight may jump to any lattice square $\sqrt{5}$ away as long as it isn't occupied. One day, a bishop and a knight were on squares in the same row of an infinite chessboard, when a huge meteor storm occurred, placing a meteor in each square on the chessboard independently and randomly with probability $p$. Neither the bishop nor the knight were hit, but their movement may have been obstructed by the meteors. The value of $p$ that would make the expected number of valid squares that the bishop can move to and the number of squares that the knight can move to equal can be expressed as $\frac{a}{b}$ for relatively prime positive integers $a, b$. Compute $100a + b$. [i]Proposed by Lewis Chen[/i]

We randomly choose 5 distinct positive integers less than or equal to 90. What is the floor of 10 times the expected value of the fourth largest number?

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?

In a dance party initially there are $20$ girls and $22$ boys in the pool and infinitely many more girls and boys waiting outside. In each round, a participant is picked uniformly at random; if a girl is picked, then she invites a boy from the pool to dance and then both of them elave the party after the dance; while if a boy is picked, then he invites a girl and a boy from the waiting line and dance together. The three of them all stay after the dance. The party is over when there are only (two) boys left in the pool. (a) What is the probability that the party never ends? (b) Now the organizer of this party decides to reverse the rule, namely that if a girl is picked, then she invites a boy and a girl from the waiting line to dance and the three stay after the dance; while if a boy is picked, he invites a girl from the pool to dance and both leave after the dance. Still the party is over when there are only (two) boys left in the pool. What is the expected number of rounds until the party ends?

Let $R$ be the rectangle in the coordinate plane with corners $(0, 0)$, $(20, 0)$, $(20, 22)$, and $(0, 22)$, and partition $R$ into a $20\times 22$ grid of unit squares. For a given line in the coordinate plane, let its [i]pixelation[/i] be the set of grid squares in $R$ that contain part of the line in their interior. If $P$ is a point chosen uniformly at random in $R$, then compute the expected number of sets of grid squares that are pixelations of some line through $P$.

Erick stands in the square in the 2nd row and 2nd column of a 5 by 5 chessboard. There are \$1 bills in the top left and bottom right squares, and there are \$5 bills in the top right and bottom left squares, as shown below. \[\begin{tabular}{|p{1em}|p{1em}|p{1em}|p{1em}|p{1em}|} \hline \$1 & & & & \$5 \\ \hline & E & & &\\ \hline & & & &\\ \hline & & & &\\ \hline \$5 & & & & \$1 \\ \hline \end{tabular}\] Every second, Erick randomly chooses a square adjacent to the one he currently stands in (that is, a square sharing an edge with the one he currently stands in) and moves to that square. When Erick reaches a square with money on it, he takes it and quits. The expected value of Erick's winnings in dollars is $m/n$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

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.

A permutation $ \pi$ is selected randomly through all $ n$-permutations. a) if \[ C_a(\pi)\equal{}\mbox{the number of cycles of length }a\mbox{ in }\pi\] then prove that $ E(C_a(\pi))\equal{}\frac1a$ b) Prove that if $ \{a_1,a_2,\dots,a_k\}\subset\{1,2,\dots,n\}$ the probability that $ \pi$ does not have any cycle with lengths $ a_1,\dots,a_k$ is at most $ \frac1{\sum_{i\equal{}1}^ka_i}$

A tree $T$ is given. Starting with the complete graph on $n$ vertices, subgraphs isomorphic to $T$ are erased at random until no such subgraph remains. For what trees does there exist a positive constant $c$ such that the expected number of edges remaining is at least $cn^2$ for all positive integers $n$? [i]David Yang.[/i]

Suppose we wish to pick a random integer between $1$ and $N$ inclusive by flipping a fair coin. One way we can do this is through generating a random binary decimal between $0$ and $1$, then multiplying the result by $N$ and taking the ceiling. However, this would take an infinite amount of time. We therefore stopping the flipping process after we have enough flips to determine the ceiling of the number. For instance, if $N=3$, we could conclude that the number is $2$ after flipping $.011_2$, but $.010_2$ is inconclusive. Suppose $N=2014$. The expected number of flips for such a process is $\frac{m}{n}$ where $m$, $n$ are relatively prime positive integers, find $100m+n$. [i]Proposed by Lewis Chen[/i]

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?

Let $a_1,a_2,a_3,\ldots$ be an infinite sequence where for all positive integers $i$, $a_i$ is chosen to be a random positive integer between $1$ and $2016$, inclusive. Let $S$ be the set of all positive integers $k$ such that for all positive integers $j<k$, $a_j\neq a_k$. (So $1\in S$; $2\in S$ if and only if $a_1\neq a_2$; $3\in S$ if and only if $a_1\neq a_3$ and $a_2\neq a_3$; and so on.) In simplest form, let $\dfrac{p}{q}$ be the expected number of positive integers $m$ such that $m$ and $m+1$ are in $S$. Compute $pq$.

Xavier takes a permutation of the numbers $1$ through $2011$ at random, where each permutation has an equal probability of being selected. He then cuts the permutation into increasing contiguous subsequences, such that each subsequence is as long as possible. Compute the expected number of such subsequences. [i]Author: Alex Zhu[/i] [hide="Clarification"]An increasing contiguous subsequence is an increasing subsequence all of whose terms are adjacent in the original sequence. For example, 1,3,4,5,2 has two maximal increasing contiguous subsequences: (1,3,4,5) and (2). [/hide]

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?$

$20$ players are playing in a Super Mario Smash Bros. Melee tournament. They are ranked $1-20$, and player $n$ will always beat player $m$ if $n<m$. Out of all possible tournaments where each player plays $18$ distinct other players exactly once, one is chosen uniformly at random. Find the expected number of pairs of players that win the same number of games.

Prove that the following inequality holds with the exception of finitely many positive integers $n$: \[\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)>4n^2.\]

For each $i=1,2,..N$, let $a_i,b_i,c_i$ be integers such that at least one of them is odd. Show that one can find integers $x,y,z$ such that $xa_i+yb_i+zc_i$ is odd for at least $\frac{4}{7}N$ different values of $i$.

Let $a_1,a_2,...,a_9$ be nine real numbers, not necessarily distinct, with average $m$. Let $A$ denote the number of triples $1 \le i < j < k \le 9$ for which $a_i + a_j + a_k \ge 3m$. What is the minimum possible value of $A$? [i]Proposed by Ray Li[/i]

Richard has a four infinitely large piles of coins: a pile of pennies (worth 1 cent each), a pile of nickels (5 cents), a pile of dimes (10 cents), and a pile of quarters (25 cents). He chooses one pile at random and takes one coin from that pile. Richard then repeats this process until the sum of the values of the coins he has taken is an integer number of dollars. (One dollar is 100 cents.) What is the expected value of this final sum of money, in cents? [i]Proposed by Lewis Chen[/i]

A rock is dropped off a cliff of height $ h $ As it falls, a camera takes several photographs, at random intervals. At each picture, I measure the distance the rock has fallen. Let the average (expected value) of all of these distances be $ kh $. If the number of photographs taken is huge, find $ k $. That is: what is the time-average of the distance traveled divided by $ h $, dividing by $h$? $ \textbf {(A) } \dfrac{1}{4} \qquad \textbf {(B) } \dfrac{1}{3} \qquad \textbf {(C) } \dfrac{1}{\sqrt{2}} \qquad \textbf {(D) } \dfrac{1}{2} \qquad \textbf {(E) } \dfrac{1}{\sqrt{3}} $ [i]Problem proposed by Ahaan Rungta[/i]

Tom is searching for the $6$ books he needs in a random pile of $30$ books. What is the expected number of books must he examine before finding all $6$ books he needs?

Bob, having little else to do, rolls a fair $6$-sided die until the sum of his rolls is greater than or equal to $700$. What is the expected number of rolls needed? Any answer within $.0001$ of the correct answer will be accepted.

A player is playing the following game. In each turn he flips a coin and guesses the outcome. If his guess is correct, he gains $ 1$ point; otherwise he loses all his points. Initially the player has no points, and plays the game until he has $ 2$ points. (a) Find the probability $ p_{n}$ that the game ends after exactly $ n$ flips. (b) What is the expected number of flips needed to finish the game?