Let $n$ be a positive integer and let $\mathcal{A}$ be a family of non-empty subsets of $\{1, 2, \ldots, n \}$ such that if $A \in \mathcal{A}$ and $A$ is subset of a set $B\subseteq \{1, 2, \ldots, n\}$, then $B$ is also in $\mathcal{A}$. Show that the function $$f(x):=\sum_{A \in \mathcal{A}} x^{|A|}(1-x)^{n-|A|}$$ is strictly increasing for $x \in (0,1)$.

Let $\zeta_1, \ldots, \zeta_n$ be (not necessarily independent) random variables with normal distribution for which $E\zeta_j=0$ and $E\zeta_j^2\le 1$ for all $1\le j\le n$. Prove that $$E\left( \max_{1\le j\le n} \zeta_j \right)\le\sqrt{2\log n}$$ (translated by Miklós Maróti)

A point is chosen at random from within a circular region. What is the probability that the point is closer to the center of the region than it is to the boundary of the region? $\text{(A)}\ 1/4 \qquad \text{(B)}\ 1/3 \qquad \text{(C)}\ 1/2 \qquad \text{(D)}\ 2/3 \qquad \text{(E)}\ 3/4$

Let $ \xi_1,\xi_2,...$ be independent, identically distributed random variables with distribution \[ P(\xi_1=-1)=P(\xi_1=1)=\frac 12 .\] Write $ S_n=\xi_1+\xi_2+...+\xi_n \;(n=1,2,...),\ \;S_0=0\ ,$ and \[ T_n= \frac{1}{\sqrt{n}} \max _{ 0 \leq k \leq n}S_k .\] Prove that $ \liminf_{n \rightarrow \infty} (\log n)T_n=0$ with probability one. [i]P. Revesz[/i]

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

Real numbers $x,y,$ and $z$ are chosen from the interval $[-1,1]$ independently and uniformly at random. What is the probability that $$\vert{x}\vert+\vert{y}\vert+\vert{z}\vert+\vert{x+y+z}\vert=\vert{x+y}\vert+\vert{y+z}\vert+\vert{z+x}\vert?$$

Consider a coin with a head toss probability $p$ where $0 <p <1$ is fixed. Toss the coin several times, the tosses should be independent of each other. Denote by $A_i$ the event that of the $i$-th, $(i + 1)$-th, $\ldots$ , the $(i+m-1)$-th throws, exactly $T$ is the tail. For $T = 1$, calculate the conditional probability $\mathbb{P}(\bar{A_2} \bar{A_3} \cdots \bar{A_m} | A_1)$, and for $T = 2$, prove that $\mathbb{P}(\bar{A_2} \bar{A_3} \cdots \bar{A_m} | A_1)$ has approximation in the form $a+ \tfrac{b}{m} + \mathcal{O}(p^m)$ as $m \to \infty$.

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

Kevin has $255$ cookies, each labeled with a unique nonempty subset of $\{1,2,3,4,5,6,7,8\}$. Each day, he chooses one cookie uniformly at random out of the cookies not yet eaten. Then, he eats that cookie, and all remaining cookies that are labeled with a subset of that cookie (for example, if he chooses the cookie labeled with $\{1,2\}$, he eats that cookie as well as the cookies with $\{1\}$ and $\{2\}$). The expected value of the number of days that Kevin eats a cookie before all cookies are gone can be expressed in the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$. [i]Proposed by Ray Li[/i]

Two three-letter strings, $aaa$ and $bbb$, are transmitted electronically. Each string is sent letter by letter. Due to faulty equipment, each of the six letters has a 1/3 chance of being received incorrectly, as an $a$ when it should have been a $b$, or as a $b$ when it should be an $a$. However, whether a given letter is received correctly or incorrectly is independent of the reception of any other letter. Let $S_a$ be the three-letter string received when $aaa$ is transmitted and let $S_b$ be the three-letter string received when $bbb$ is transmitted. Let $p$ be the probability that $S_a$ comes before $S_b$ in alphabetical order. When $p$ is written as a fraction in lowest terms, what is its numerator?

The George Washington Bridge is $2016$ meters long. Sally is standing on the George Washington Bridge, $1010$ meters from its left end. Each step, she either moves $1$ meter to the left or $1$ meter to the right, each with probability $\dfrac{1}{2}$. What is the expected number of steps she will take to reach an end of the bridge?

Three points are randomly placed on a circle. What is the probability that they lie on the same semicircle

Kate has two bags $X$ and $Y$. Bag $X$ contains $5$ red marbles (and nothing else). Bag $Y$ contains $4$ red marbles and $1$ blue marble (and nothing else). Kate chooses one of her bags at random (each with probability $\frac{1}{2}$) and removes a random marble from that bag (each marble in that bag being equally likely). She repeats the previous step until one of the bags becomes empty. At that point, what is the probability that the blue marble is still in bag $Y$?

Let $X$ and $Y$ be independent random variables with "Saint-Petersburg" distribution, i.e. for any $k=1,2,\ldots$ their value is $2^k$ with probability $\frac{1}{2^k}$. Show that $X$ and $Y$ can be realized on a sufficiently big probability space such that there exists another pair of independent "Saint-Petersburg" random variables $(X', Y')$ on this space with the property that $X+Y=2X'+Y'I(Y'\le X')$ almost surely (here $I(A)$ denotes the indicator function of the event $A$). (translated by L. Erdős)

The Ultimate Question is a 10-part problem in which each question after the first depends on the answer to the previous problem. As in the Short Answer section, the answer to each (of the 10) problems is a nonnegative integer. You should submit an answer for each of the 10 problems you solve (unlike in previous years). In order to receive credit for the correct answer to a problem, you must also correctly answer $\textit{every one}$ $\textit{of the previous parts}$ $\textit{of the Ultimate Question}$.

The figure on the right shows the map of Squareville, where each city block is of the same length. Two friends, Alexandra and Brianna, live at the corners marked by $A$ and $B$, respectively. They start walking toward each other's house, leaving at the same time, walking with the same speed, and independently choosing a path to the other's house with uniform distribution out of all possible minimum-distance paths [that is, all minimum-distance paths are equally likely]. What is the probability they will meet? [asy] size(200); defaultpen(linewidth(0.8)); for(int i=0;i<=2;++i) { for(int j=0;j<=4;++j) { draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--cycle); } } for(int i=3;i<=4;++i) { for(int j=3;j<=6;++j) { draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--cycle); } } label("$A$",origin,SW); label("$B$",(5,7),SE); [/asy]

How many positive integers less than 10,000 have at most two different digits?

The $ 600$ students at King Middle School are divided into three groups of equal size for lunch. Each group has lunch at a different time. A computer randomly assigns each student to one of the three lunch groups. The probability that the three friends, Al, Bob, and Carol, will be assigned to the same lunch group is approximately: \[ \textbf{(A)}\ \frac{1}{27} \qquad \textbf{(B)}\ \frac{1}{9} \qquad \textbf{(C)}\ \frac{1}{8} \qquad \textbf{(D)}\ \frac{1}{6} \qquad \textbf{(E)}\ \frac{1}{3} \]

Juli is a mathematician and devised an algorithm to find a husband. The strategy is: • Start interviewing a maximum of $1000$ prospective husbands. Assign a ranking $r$ to each person that is a positive integer. No two prospects will have same the rank $r$. • Reject the first $k$ men and let $H$ be highest rank of these $k$ men. • After rejecting the first $k$ men, select the next prospect with a rank greater than $H$ and then stop the search immediately. If no candidate is selected after $999$ interviews, the $1000th$ person is selected. Juli wants to find the value of $k$ for which she has the highest probability of choosing the highest ranking prospect among all $1000$ candidates without having to interview all $1000$ prospects. [b](a)[/b] (6 points:) What is the probability that the highest ranking prospect among all $1000$ prospects is the $(m + 1)th$ prospect? [b](b)[/b] (6 points:) Assume the highest ranking prospect is the $(m + 1)th$ person to be interviewed. What is the probability that the highest rank candidate among the first $m$ candidates is one of the first $k$ candidates who were rejected? [b](c)[/b] (6 points:) What is the probability that the prospect with the highest rank is the $(m+1)th$ person and that Juli will choose the $(m+1)th$ man using this algorithm? [b](d)[/b] (16 points:) The total probability that Juli will choose the highest ranking prospect among the $1000$ prospects is the sum of the probability for each possible value of $m+1$ with $m+1$ ranging between $k+1$ and $1000$. Find the sum. To simplify your answer use the formula $In N \approx \frac{1}{N-1}+\frac{1}{N-2}+...+\frac{1}{2}+1$ [b](e)[/b] (6 points:) Find that value of $k$ that maximizes the probability of choosing the highest ranking prospect without interviewing all $1000$ candidates. You may need to know that the maximum of the function $x ln \frac{A}{x-1}$ is approximately $\frac{A + 1}{e}$, where $A$ is a constant and $e$ is Euler’s number, $e = 2.718....$

A poll shows that $ 70\%$ of all voters approve of the mayor's work. On three separate occasions a pollster selects a voter at random. What is the probability that on exactly one of these three occasions the voter approves of the mayor's work? $ \textbf{(A)}\ 0.063 \qquad \textbf{(B)}\ 0.189 \qquad \textbf{(C)}\ 0.233 \qquad \textbf{(D)}\ 0.333 \qquad \textbf{(E)}\ 0.441$

A set of lines in the plane is in [i]general position[/i] if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its [i]finite regions[/i]. Prove that for all sufficiently large $n$, in any set of $n$ lines in general position it is possible to colour at least $\sqrt{n}$ lines blue in such a way that none of its finite regions has a completely blue boundary. [i]Note[/i]: Results with $\sqrt{n}$ replaced by $c\sqrt{n}$ will be awarded points depending on the value of the constant $c$.

Let $ a_1, a_2, \ldots , a_n$ be distinct positive integers and let $ M$ be a set of $ n \minus{} 1$ positive integers not containing $ s \equal{} a_1 \plus{} a_2 \plus{} \ldots \plus{} a_n.$ A grasshopper is to jump along the real axis, starting at the point $ 0$ and making $ n$ jumps to the right with lengths $ a_1, a_2, \ldots , a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $ M.$ [i]Proposed by Dmitry Khramtsov, Russia[/i]

Let $\mathcal{N}_p$ stand for a $p$ dimensional random variable of standard normal distribution. For $a\in\mathbb{R}^p$, let $H_p(a)$ stand for the expectation $E|\mathcal{N}_p+a|$. For $p>1$, prove that $$H_p(a)=(p-1)\int_0^{\infty} H_1\left( \frac{|a|}{\sqrt{r^2+1}}\right) \frac{r^{p-2}}{\sqrt{(r^2+1)^p}} \mathrm{d}r$$

A box contains $p$ white balls and $q$ black balls. Beside the box there is a pile of black balls. Two balls are taken out of the box. If they have the same color, a black ball from the pile is put into the box. If they have different colors, the white ball is put back into the box. This procedure is repeated until the last two balls are removed from the box and one last ball is put in. What is the probability that this last ball is white?

Two different squares are randomly chosen from an $8\times8$ chessboard. What is the probability that two queens placed on the two squares can attack each other? Recall that queens in chess can attack any square in a straight line vertically, horizontally, or diagonally from their current position.