Let $\varepsilon$ denote the empty string. Given a pair of strings $(A,B)\in\{0,1,2\}^*\times\{0,1\}^*$, we are allowed the following operations: \[\begin{cases} (A,1)\to(A0,\varepsilon)\\ (A,10)\to(A00,\varepsilon)\\ (A,0B)\to(A0,B)\\ (A,11B)\to(A01,B)\\ (A,100B)\to(A0012,1B)\\ (A,101B)\to(A00122,10B) \end{cases}\] We perform these operations on $(A,B)$ until we can no longer perform any of them. We then iteratively delete any instance of $20$ in $A$ and replace any instance of $21$ with $1$ until there are no such substrings remaining. Among all binary strings $X$ of size $9$, how many different possible outcomes are there for this process performed on $(\varepsilon,X)$?

For integer $n\geq 2$ and real $0\leq p\leq 1$, define $\mathcal{W}_{n,p}$ to be the complete weighted undirected random graph with vertex set $\{1,2,\ldots,n\}$: the edge $(i,j)$ will have weight $\min(i,j)$ with probability $p$ and weight $\max(i,j)$ otherwise. Let $\mathcal{L}_{n,p}$ denote the total weight of the minimum spanning tree of $\mathcal{W}_{n,p}$. Find the largest integer less than the expected value of $\mathcal{L}_{2018,1/2}$.

Let $\Gamma = \{\varepsilon,0,00,\ldots\}$ be the set of all finite strings consisting of only zeroes. We consider $\textit{six-state unary DFAs}$ $D = (F,q_0,\delta)$ where $F$ is a subset of $Q = \{1,2,3,4,5,6\}$, not necessarily strict and possibly empty; $q_0\in Q$ is some $\textit{start state}$; and $\delta: Q\rightarrow Q$ is the $\textit{transition function}$. For each such DFA $D$, we associate a set $F_D\subseteq\Gamma$ as the set of all strings $w\in\Gamma$ such that \[\underbrace{\delta(\cdots(\delta(q_0))\cdots)}_{|w|\text{ applications}}\in F,\] We say a set $\mathcal D$ of DFAs is $\textit{diverse}$ if for all $D_1,D_2\in\mathcal D$ we have $F_{D_1}\neq F_{D_2}$. What is the maximum size of a diverse set?

Answer the following questions : [b](a)[/b] Evaluate $~~\lim_{x\to 0^{+}} \Big(x^{x^x}-x^x\Big)$ [b](b)[/b] Let $A=\frac{2\pi}{9}$, i.e. $40$ degrees. Calculate the following $$1+\cos A+\cos 2A+\cos 4A+\cos 5A+\cos 7A+\cos 8A$$ [b](c)[/b] Find the number of solutions to $$e^x=\frac{x}{2017}+1$$

You are presented with a mystery function $f:\mathbb N^2\to\mathbb N$ which is known to satisfy \[f(x+1,y)>f(x,y)\quad\text{and}\quad f(x,y+1)>f(x,y)\] for all $(x,y)\in\mathbb N^2$. I will tell you the value of $f(x,y)$ for \$1. What's the minimum cost, in dollars, that it takes to compute the $19$th smallest element of $\{f(x,y)\mid(x,y)\in\mathbb N^2\}$? Here, $\mathbb N=\{1,2,3,\dots\}$ denotes the set of positive integers.

Let $n$ be a positive integer. Jadzia has to write all integers from $1$ to $2n-1$ on a board, and she writes each integer in blue or red color. We say that pair of numbers $i,j\in \{1,2,3,...,2n-1\}$, where $i\leqslant j$, is $\textit{good}$ if and only if number of blue numbers among $i,i+1,...,j$ is odd. Determine, in terms of $n$, maximal number of good pairs.

We are given the following function $f$, which takes a list of integers and outputs another list of integers. (Note that here the list is zero-indexed.) \begin{tabular}{l} 1: \textbf{FUNCTION} $f(A)$ \\ 2: $\quad$ \textbf{FOR} $i=1,\ldots, \operatorname{length}(A)-1$: \\ 3: $\quad\quad$ $A[i]\leftarrow A[A[i]]$ \\ 4: $\quad\quad$ $A[0]\leftarrow A[0]-1$ \\ 5: $\quad$ \textbf{RETURN} $A$ \end{tabular} Suppose the list $B$ is equal to $[0,1,2,8,2,0,1,7,0]$. In how many entries do $B$ and $f(B)$ differ?

Ryan has three distinct eggs, one of which is made of rubber and thus cannot break; unfortunately, he doesn't know which egg is the rubber one. Further, in some 100-story building there exists a floor such that all normal eggs dropped from below that floor will not break, while those dropped from at or above that floor will break and cannot be dropped again. What is the minimum number of times Ryan must drop an egg to determine the floor satisfying this property?

Consider a $1$-indexed array that initially contains the integers $1$ to $10$ in increasing order. The following action is performed repeatedly (any number of times): [code] def action(): Choose an integer n between 1 and 10 inclusive Reverse the array between indices 1 and n inclusive Reverse the array between indices n+1 and 10 inclusive (If n = 10, we do nothing) [/code] How many possible orders can the array have after we are done with this process?

In concurrent computing, two processes may have their steps interwoven in an unknown order, as long as the steps of each process occur in order. Consider the following two processes: \begin{tabular}{c|cc} Process & $A$ & $B$\\ \hline Step 1 & $x\leftarrow x-4$ & $x\leftarrow x-5$\\ Step 2 & $x\leftarrow x\cdot3$ & $x\leftarrow x\cdot4$\\ Step 3 & $x\leftarrow x-4$ & $x\leftarrow x-5$\\ Step 4 & $x\leftarrow x\cdot3$ & $x\leftarrow x\cdot4$ \end{tabular} One such interweaving is $A1$, $B1$, $A2$, $B2$, $A3$, $B3$, $B4$, $A4$, but $A1$, $A3$, $A2$, $A4$, $B1$, $B2$, $B3$, $B4$ is not since the steps of $A$ do not occur in order. We run $A$ and $B$ concurrently with $x$ initially valued at $6$. Find the minimal possible value of $x$ among all interweavings.

Robert has five beads in his hand, with the letters $C, M, I, M,$ and $C,$ and he wants to make a circular bracelet spelling "$CMIMC.$" However, the power went out, so Robert can no longer see the beads in his hand. Thus, he puts the five beads on the bracelet randomly, hoping that the bracelet, when possibly rotated or flipped, spells out "$CMIMC.$" What is the probability that this happens? (Robert doesn’t care whether some letters appear upside down or backwards.)

We define the $\emph{weight}$ of a path to be the sum of the numbers written on each edge of the path. Find the minimum weight among all paths in the graph below that visit each vertex precisely once: [center][img]http://i.imgur.com/V99Eg9j.png[/img][/center]

Define a search algorithm called $\texttt{powSearch}$. Throughout, assume $A$ is a 1-indexed sorted array of distinct integers. To search for an integer $b$ in this array, we search the indices $2^0,2^1,\ldots$ until we either reach the end of the array or $A[2^k] > b$. If at any point we get $A[2^k] = b$ we stop and return $2^k$. Once we have $A[2^k] > b > A[2^{k-1}]$, we throw away the first $2^{k-1}$ elements of $A$, and recursively search in the same fashion. For example, for an integer which is at position $3$ we will search the locations $1, 2, 4, 3$. Define $g(x)$ to be a function which returns how many (not necessarily distinct) indices we look at when calling $\texttt{powSearch}$ with an integer $b$ at position $x$ in $A$. For example, $g(3) = 4$. If $A$ has length $64$, find \[g(1) + g(2) + \ldots + g(64).\]

Sophia writes an algorithm to solve the graph isomorphism problem. Given a graph $G=(V,E)$, her algorithm iterates through all permutations of the set $\{v_1, \dots, v_{|V|}\}$, each time examining all ordered pairs $(v_i,v_j)\in V\times V$ to see if an edge exists. When $|V|=8$, her algorithm makes $N$ such examinations. What is the largest power of two that divides $N$?

How many complete directed graphs with vertex set $V=\{1,2,3,4,5,6\}$ contain no $3$-cycles? A graph is $\textit{directed}$ if all edges have a direction (e.g. from $u$ to $v$ rather than between $u$ and $v$), and $\textit{complete}$ if every pair of vertices has an edge between them. Further, a $\textit{3-cycle}$ in a directed graph is a triple $(u,v,w)$ of vertices such that there are edges from $u$ to $v$, $v$ to $w$, and $w$ to $u$.

Catherine has a plate containing $300$ circular crumbling mooncakes, arranged as follows: [asy] unitsize(10); for (int i = 0; i < 16; ++i){ for (int j = 0; j < 3; ++j){ draw(circle((sqrt(3)*i,j),0.5)); draw(circle((sqrt(3)*(i+0.5),j-0.5),0.5)); } } dot((16*sqrt(3)+.5,.75)); dot((16*sqrt(3)+1,.75)); dot((16*sqrt(3)+1.5,.75)); [/asy] (This continues for $100$ total columns). She wants to pick some of the mooncakes to eat, however whenever she takes a mooncake all adjacent mooncakes will be destroyed and cannot be eaten. Let $M$ be the maximal number of mooncakes she can eat, and let $n$ be the number of ways she can pick $M$ mooncakes to eat (Note: the order in which she picks mooncakes does not matter). Compute the ordered pair ($M$, $n$).

What is the minimum number of times you have to take your pencil off the paper to draw the following figure (the dots are for decoration)? You must lift your pencil off the paper after you're done, and this is included in the number of times you take your pencil off the paper. You're not allowed to draw over an edge twice. [center][img]http://i.imgur.com/CBGmPmv.png[/img][/center]

Cody has an unfair coin that flips heads with probability either $\tfrac13$ or $\tfrac23$, but he doesn't know which one it is. Using this coin, what is the fewest number of independent flips needed to simulate a coin that he knows will flip heads with probability $\tfrac13$?

For how many distinct ordered triples $(a,b,c)$ of boolean variables does the expression $a \lor (b \land c)$ evaluate to true?

Consider the following two vertex-weighted graphs, and denote them as having vertex sets $V=\{v_1,v_2,\ldots,v_6\}$ and $W=\{w_1,w_2,\ldots,w_6\}$, respectively (numbered in the same direction and way). The weights in the second graph are such that for all $1\le i\le 6$, the weight of $w_i$ is the sum of the weights of the neighbors of $v_i$. Determine the sum of the weights of the original graph.

Consider a complete graph of $2020$ vertices. What is the least number of edges that need to be marked such that each triangle ($3$-vertex subgraph) has an odd number of marked edges?

Divide a regular $8960$-gon into non-overlapping parallelograms. Suppose that $R$ of these parallelograms are rectangles. What is the minimum possible value of $R$?

Alan is bored one day and decides to write down all the divisors of $1260^2$ on a wall. After writing down all of them, he realizes he wrote them on the wrong wall and needs to erase all his work. Every second, he picks a random divisor which is still on the wall and instantly erases it and every number that divides it. What is the expected time it takes for Alan to erase everything on the wall?

Define \[f(h,t) = \begin{cases} 8h & h = t \\ (h-t)^2 & h \neq t. \end{cases}\] Cody plays a game with a fair coin, where he begins by flipping it once. At each turn in the game, if he has flipped $h$ heads and $t$ tails and $h + t < 6$, he can choose either to stop and receive $f(h,t)$ dollars or he can flip the coin again; if $h + t = 6$ then the game ends and he receives $f(h,t)$ dollars. If Cody plays to maximize expectancy, how much money, in dollars, can he expect to win from this game?

Consider the set $L$ of binary strings of length less than or equal to $9$, and for a string $w$ define $w^{+}$ to be the set $\{w,w^2,w^3,\ldots\}$ where $w^k$ represents $w$ concatenated to itself $k$ times. How many ways are there to pick an ordered pair of (not necessarily distinct) elements $x,y\in L$ such that $x^{+}\cap y^{+}\neq \varnothing$?