Let $x_i\in\{+1,\ -1\}$, $i=1,\ 2,\ \cdots,\ 2n$. If their sum equals $0$ and the following inequality holds for any positive integer $k$ satisfying $1\le k < 2n$: $$x_1+x_2+\cdots + x_k\ge 0$$

Find the number of possible ordered sequence $\{x_1,\ x_2,\ \cdots,\ x_{2n}\}$.

(Hanoi Tower) There are $3$ identical rods labeled as $A$, $B$, $C$; and $n$ disks of different sizes which can be slide onto any of these three rods. Initially, the $n$ disks are stacked in ascending order of their sizes on $A$. What is the minimal number of moves in order to transfer all the disks to $B$ providing that each move can only transfer one disk to another rod's topmost position and at no time, a bigger disk can be placed on top of a smaller one.

Find the total number of sequences of length $n$ containing only letters $A$ and $B$ such that no two $A$s are next to each other. For example, for $n = 2$, there are $3$ possible sequences: $AB$, $BA$, and $BB$.

How many distinct permutations of the letters of the word REDDER are there that do not contain a palindromic substring of length at least two? (A substring is a contiguous block of letters that is part of the string. A string is palindromic if it is the same when read backwards.)

Reimu and Sanae play a game using $4$ fair coins. Initially both sides of each coin are white. Starting with Reimu, they take turns to color one of the white sides either red or green. After all sides are colored, the 4 coins are tossed. If there are more red sides showing up, then Reimu wins, and if there are more green sides showing up, then Sanae wins. However, if there is an equal number of red sides and green sides, then neither of them wins. Given that both of them play optimally to maximize the probability of winning, what is the probability that Reimu wins? 

Yannick is playing a game with $100$ rounds, starting with $1$ coin. During each round, there is a $n\%$ chance that he gains an extra coin, where $n$ is the number of coins he has at the beginning of the round. What is the expected number of coins he will have at the end of the game?

Contessa is taking a random lattice walk in the plane, starting at $(1, 1)$. (In a random lattice walk, one moves up, down, left, or right $1$ unit with equal probability at each step.) If she lands on a point of the form $(6m, 6n)$ for $m$, $n\in\mathbb{Z}$, she ascends to heaven, but if she lands on a point of the form $(6m+ 3, 6n+ 3)$ for $m,\ n\in\mathbb{Z}$, she descends to hell. What is the probability that she ascends to heaven? 

A point $P$ lies at the center of square $ABCD$. A sequence of points $\{P_n\}$ is determined by $P_0 = P$, and given point $P_i$ , point $P_{i+1}$ is obtained by reflecting $P_i$ over one of the four lines $AB$, $BC$, $CD$, $DA$, chosen uniformly at random and independently for each $i$. What is the probability that $P_8 = P$? 

In an election for the Peer Pressure High School student council president, there are $2019$ voters and two candidates Alice and Celia (who are voters themselves). At the beginning, Alice and Celia both vote for themselves, and Alice’s boyfriend Bob votes for Alice as well. Then one by one, each of the remaining $2016$ voters votes for a candidate randomly, with probabilities proportional to the current number of the respective candidate’s votes. For example, the first undecided voter David has a $2/3$ probability of voting for Alice and a $1/3$ probability of voting for Celia. What is the probability that Alice wins the election (by having more votes than Celia)?

For a positive integer $N$, we color the positive divisors of $N$ (including $1$ and $N$) with four colors. A coloring is called multichromatic if whenever $a$, $b$ and $\gcd(a, b)$ are pairwise distinct divisors of $N$, then they have pairwise distinct colors. What is the maximum possible number of multichromatic colorings a positive integer can have if it is not the power of any prime? 

How many ways can one fill a $3\times 3$ square grid with nonnegative integers such that no nonzero integer appears more than once in the same row or column and the sum of the numbers in every row and column equals $7$?

Fred the Four-Dimensional Fluffy Sheep is walking in $4$-dimensional space. He starts at the origin. Each minute, he walks from his current position $(a_1,\ a_2,\ a_3,\ a_4)$ to some position $(x_1,\ x_2,\ x_3,\ x_4)$ with integer coordinates satisfying $$(x_1−a_1)^2+(x_2−a_2)^2+(x_3−a_3)^2+(x_4−a_4)^2 = 4$$

and $\mid (x_1 + x_2 + x_3 + x_4) − (a_1 + a_2 + a_3 + a_4)\mid = 2$. In how many ways can Fred reach $(10, 10, 10, 10)$ after exactly $40$ minutes, if he is allowed to pass through this point during his walk?

Consider a $2\times 3$ grid where each entry is one of $0$, $1$, and $2$. For how many such grids is the sum of the numbers in every row and in every column a multiple of $3$? One valid grid is shown below: $$\begin{bmatrix}  1& 2 & 0\\ 2& 1 &0 \end{bmatrix}$$

A $4\times 4$ window is made out of $16$ square windowpanes. How many ways are there to stain each of the windowpanes, red, pink, or magenta, such that each windowpane is the same color as exactly two of its neighbors? Two different windowpanes are neighbors if they share a side. 

How many ways are there for Nick to travel from $(0,\ 0)$ to $(16,\ 16)$ in the coordinate plane by moving one unit in the positive $x$ or $y$ direction at a time, such that Nick changes direction an odd number of times?

A bag contains nine blue marbles, ten ugly marbles, and one special marble. Ryan picks marbles randomly from this bag with replacement until he draws the special marble. He notices that none of the marbles he drew were ugly. Given this information, what is the expected value of the number of total marbles he drew? 

Sarah stands at $(0,\ 0)$ and Rachel stands at $(6,\ 8)$ in the Euclidean plane. Sarah can only move $1$ unit in the positive $x$ or $y$ direction, and Rachel can only move $1$ unit in the negative $x$ or $y$ direction. Each second, Sarah and Rachel see each other, independently pick a direction to move at the same time, and move to their new position. Sarah catches Rachel if Sarah and Rachel are ever at the same point. Rachel wins if she is able to get to $(0,\ 0)$ without being caught; otherwise, Sarah wins. Given that both of them play optimally to maximize their probability of winning, what is the probability that Rachel wins? 

A tourist is learning an incorrect way to sort a permutation $(p_1,\ \cdots,\ p_n)$ of the integers $(1,\ \cdots,\ n)$. We define a fix on two adjacent elements $p_i$ and $p_{i+1}$, to be an operation which swaps the two elements if $p_i > p_{i+1}$, and does nothing otherwise. The tourist performs $n-1$ rounds of fixes, numbered $a = 1$, $2$, $\cdots$, $n − 1$. In round a of fixes, the tourist fixes $p_a$ and $p_{a+1}$, then $p_{a+1}$ and $p_{a+2}$, and so on, up to $p_{n−1}$ and $p_n$. In this process, there are $(n − 1) + (n − 2) + · · · + 1 = n(n−1) 2$ total fixes performed. How many permutations of $(1,\ \cdots ,\ 2018)$ can the tourist start with to obtain $(1,\ \cdots ,\ 2018)$ after performing these steps?

A permutation of $\{1,\ 2,\ \cdots,\ 7\}$ is chosen uniformly at random. A partition of the permutation into contiguous blocks is correct if, when each block is sorted independently, the entire permutation becomes sorted. For example, the permutation $(3,\ 4,\ 2,\ 1,\ 6,\ 5,\ 7)$ can be partitioned correctly into the blocks $[3,\ 4,\ 2,\ 1]$ and $[6,\ 5,\ 7]$, since when these blocks are sorted, the permutation becomes $(1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7)$. Find the expected value of the maximum number of blocks into which the permutation can be partitioned correctly. 

How many ordered sequences of $36$ digits have the property that summing the digits to get a number and taking the last digit of the sum results in a digit which is not in our original sequence? (Digits range from $0$ to $9$.)

Lily has a $300\times 300$ grid of squares. She now removes $100\times 100$ squares from each of the four corners and colors each of the remaining $50000$ squares black and white. Given that no $2\times 2$ square is colored in a checkerboard pattern, find the maximum possible number of (unordered) pairs of squares such that one is black, one is white and the squares share an edge.

Kelvin the Frog is going to roll three fair ten-sided dice with faces labelled $0,\ 1,\ 2,\ \cdots,\ 9$. First he rolls two dice, and finds the sum of the two rolls. Then he rolls the third die. What is the probability that the sum of the first two rolls equals the third roll?

There are $2017$ jars in a row on a table, initially empty. Each day, a nice man picks ten consecutive jars and deposits one coin in each of the ten jars. Later, Kelvin the Frog comes back to see that $N$ of the jars all contain the same positive integer number of coins (i.e. there is an integer $d > 0$ such that $N$ of the jars have exactly $d$ coins). What is the maximum possible value of $N$? 

Sam spends his days walking around the following $2\times 2$ grid of squares. $$\begin{bmatrix} 1& 2 \\ 4&3 \end{bmatrix}$$

Say that two squares are adjacent if they share a side. He starts at the square labeled $1$ and every second walks to an adjacent square. How many paths can Sam take so that the sum of the numbers on every square he visits in his path is equal to $20$ (not counting the square he started on)?