Define a self-balanced tree to be a tree such that for any node, the size of the left subtree is within 1 of the size of the right subtree. How many balanced trees are there of size 2046?

Let $p(k)$ be the probability that if we choose a uniformly random subset $S$ of $\{1, 2, \ldots, 18\},$ then $|S| \equiv k \pmod{5}.$ Evaluate $$\sum_{k=0}^4 \left|p(k)-\frac{1}{5}\right|.$$

Define a [i]rooted tree[/i] to be a tree $T$ with a singular node designated as the [i]root[/i] of $T$. (Note that every node in the tree can have an arbitrary number of children.) Each vertex adjacent to the root node of $T$ is itself the root of some tree called a [i]maximal subtree[/i] of $T$. Say two rooted trees $T_1$ and $T_2$ are [i]similar[/i] if there exists some way to cycle the maximal subtrees of $T_1$ to get $T_2$. For example, the first pair of trees below are similar but the second pair are not. How many rooted trees with $2019$ nodes are there up to similarity? [center] [img=500x100]https://i.imgur.com/8axcDvz.png[/img] [/center]

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]

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?

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?

Consider the natural implementation of computing Fibonacci numbers: \begin{tabular}{l} 1: \textbf{FUNCTION} $\text{FIB}(n)$: \\ 2:$\qquad$ \textbf{IF} $n = 0$ \textbf{OR} $n = 1$ \textbf{RETURN} 1 \\ 3:$\qquad$ \textbf{RETURN} $\text{FIB}(n-1) + \text{FIB}(n-2)$ \end{tabular} When $\text{FIB}(10)$ is evaluated, how many recursive calls to $\text{FIB}$ occur?

Let $n=2017$ and $x_1,\dots,x_n$ be boolean variables. An \emph{$7$-CNF clause} is an expression of the form $\phi_1(x_{i_1})+\dots+\phi_7(x_{i_7})$, where $\phi_1,\dots,\phi_7$ are each either the function $f(x)=x$ or $f(x)=1-x$, and $i_1,i_2,\dots,i_7\in\{1,2,\dots,n\}$. For example, $x_1+(1-x_1)+(1-x_3)+x_2+x_4+(1-x_3)+x_{12}$ is a $7$-CNF clause. What's the smallest number $k$ for which there exist $7$-CNF clauses $f_1,\dots,f_k$ such that \[f(x_1,\dots,x_n):=f_1(x_1,\dots,x_n)\cdots f_k(x_1,\dots,x_n)\] is $0$ for all values of $(x_1,\dots,x_n)\in\{0,1\}^n$?

The intramural squash league has 5 players, namely Albert, Bassim, Clara, Daniel, and Eugene. Albert has played one game, Bassim has played two games, Clara has played 3 games, and Daniel has played 4 games. Assuming no two players in the league play each other more than one time, how many games has Eugene played?

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?

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

Consider the following modified algorithm for binary search, which we will call $\textit{weighted binary search}$: \begin{tabular}{l} 01: \textbf{FUNCTION} SEARCH($L$, value) \\ 02:$\qquad$ hi $\leftarrow$ $\operatorname{len}(L) - 1$ \\ 03:$\qquad$ lo $\leftarrow$ 0 \\ 04:$\qquad$ \textbf{WHILE} hi $\geq$ lo \\ 05:$\qquad\qquad$ guess $\leftarrow$ $\lfloor w \cdot\text{lo} + (1-w) \cdot \text{hi}\rfloor$ \\ 06:$\qquad\qquad$ mid $\leftarrow$ $L[\text{guess}]$ \\ 07:$\qquad\qquad$ \textbf{IF} mid $> \text{value}$ \\ 08: $\qquad\qquad\qquad$ hi $\leftarrow$ $\text{guess} - 1$ \\ 09: $\qquad\qquad$ \textbf{ELSE IF} mid $< \text{value}$ \\ 10: $\qquad\qquad\qquad$ lo $\leftarrow$ $\text{guess} + 1$ \\ 11: $\qquad\qquad$ \textbf{ELSE} \\ 12: $\qquad\qquad\qquad$ \textbf{RETURN} guess \\ 13:$\qquad$ \textbf{RETURN} -1 (not found) \end{tabular}\\ Assume $L$ is a list of the integers $\{1,2,\ldots,100\}$, in that order. Further assume that accessing the $k$th index of $L$ costs $k+1$ tokens (e.g. $L[0]$ costs $1$ token). Let $S$ be the set of all $w\in[\tfrac12,1)$ which minimize the average cost when $\texttt{value}$ is an integer selected at random in the range $[1,50]$. Given that $S=\left(x,\tfrac {74}{99}\right]$, determine $x$.

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

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).\]

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]

Consider a $12$-card deck containing all four suits of $2, 3,$ and $4.$ A [i]double[/i] is defined as two cards directly next to each other in the deck, with the same value. Suppose we scan the deck left to right, and whenever we encounter a double, we remove all the cards up to that point (including the double). Let $N$ denote the number of times we have to remove cards. What is the expected value of $N$?

In the following list of numbers (given in their binary representations), each number appears an even number of times, except for one number that appears exactly three times. Find the number that appears exactly three times. Leave the answer in its binary representation. \begin{tabular}{cccccc} 010111 & 000001 & 100000 & 011000 & 110101 & 100001 \\ 010100 & 011111 & 111001 & 010001 & 010100 & 101100 \\ 010001 & 011011 & 011111 & 011011 & 100000 & 000001 \\ 110011 & 001000 & 111101 & 100001 & 101100 & 110011 \\ 111111 & 011000 & 001000 & 101000 & 111111 & 101000 \\ 010111 & 100011 & 111001 & 100011 & 110101 & 011111 \\ 100000 & 010100 & 010001 & 101100 & 010111 & 011011 \\ 011000 & 111101 & 111111 & 100001 & 101000 & 100011 \\ 011011 & 010111 & 110011 & 111111 & 000001 & 010001 \\ 101000 & 111001 & 010100 & 110101 & 011000 & 110101 \\ 001000 & 000001 & 100000 & 111101 & 100011 & 001000 \\ 111001 & 110011 & 100001 & 011111 & 101100 \end{tabular}

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