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]

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

Assume that $ R$, a recursive, binary relation on $ \mathbb{N}$ (the set of natural numbers), orders $ \mathbb{N}$ into type $ \omega$. Show that if $ f(n)$ is the $ n$th element of this order, then $ f$ is not necessarily recursive. [i]L. Posa[/i]

Every day, Pinky the flamingo eats either $1$ or $2$ shrimp, each with equal probability. Once Pinky has consumed $10$ or more shrimp in total, its skin will turn pink. Once Pinky has consumed $11$ or more shrimp in total, it will get sick. What is the probability that Pinky does not get sick on the day its skin turns pink?

How many distinct spanning trees does the graph below have? Recall that a $\emph{spanning tree}$ of a graph $G$ is a subgraph of $G$ that is a tree and containing all the vertices of $G$. [center][img]http://i.imgur.com/NMF12pE.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$?

The nation of CMIMCland consists of 8 islands, none of which are connected. Each citizen wants to visit the other islands, so the government will build bridges between the islands. However, each island has a volcano that could erupt at any time, destroying that island and any bridges connected to it. The government wants to guarantee that after any eruption, a citizen from any of the remaining $7$ islands can go on a tour, visiting each of the remaining islands exactly once and returning to their home island (only at the end of the tour). What is the minimum number of bridges needed?

Aaron is trying to write a program to compute the terms of the sequence defined recursively by $a_0=0$, $a_1=1$, and \[a_n=\begin{cases}a_{n-1}-a_{n-2}&n\equiv0\pmod2\\2a_{n-1}-a_{n-2}&\text{else}\end{cases}\] However, Aaron makes a typo, accidentally computing the recurrence by \[a_n=\begin{cases}a_{n-1}-a_{n-2}&n\equiv0\pmod3\\2a_{n-1}-a_{n-2}&\text{else}\end{cases}\] For how many $0\le k\le2016$ did Aaron coincidentally compute the correct value of $a_k$?

The continent of Trianglandia is an equilateral triangle of side length $9$, divided into $81$ triangular countries of side length $1$. Each country has the resources to choose at most $1$ of its $3$ sides and build a “wall” covering that entire side. However, since all the countries are at war, no two countries are willing to have their walls touch, even at a corner. What is the maximum number of walls that can be built in Trianglandia?

Consider an undirected, connected graph $G$ with vertex set $\{v_1,v_2,\ldots, v_6\}$. Starting at the vertex $v_1$, an ant uses a DFS algorithm to traverse through $G$ under the condition that if there are multiple unvisited neighbors of some vertex, the ant chooses the $v_i$ with smallest $i$. How many possible graphs $G$ are there satisfying the following property: for each $1\leq i\leq 6$, the vertex $v_i$ is the $i^{\text{th}}$ new vertex the ant traverses?

Consider the sequence of sets defined by $S_0=\{0,1\},S_1=\{0,1,2\}$, and for $n\ge2$, \[S_n=S_{n-1}\cup\{2^n+x\mid x\in S_{n-2}\}.\] For example, $S_2=\{0,1,2\}\cup\{2^2+0,2^2+1\}=\{0,1,2,4,5\}$. Find the $200$th smallest element of $S_{2016}$.

Given a list $A$ of $n$ real numbers, the following algorithm, known as $\textit{insertion sort}$, sorts the elements of $A$ from least to greatest. \begin{tabular}{l} 1: \textbf{FUNCTION} $IS(A)$ \\ 2: $\quad$ \textbf{FOR} $i=0,\ldots, n-1$: \\ 3: $\quad\quad$ $j \leftarrow i$\\ 4: $\quad\quad$ \textbf{WHILE} $j>0$ \& $A[j-1]>A[j]:$\\ 5: $\quad\quad\quad$ \textbf{SWAP} $A[j], A[j-1]$\\ 6: $\quad\quad\quad$ $j \leftarrow j-1$\\ 7: \textbf{RETURN} $A$ \end{tabular} As $A$ ranges over all permutations of $\{1, 2, \ldots, n\}$, let $f(n)$ denote the expected number of comparisons (i.e., checking which of two elements is greater) that need to be made when sorting $A$ with insertion sort. Evaluate $f(13) - f(12)$.

Given the list \[A=[9,12,1,20,17,4,10,7,15,8,13,14],\] we would like to sort it in increasing order. To accomplish this, we will perform the following operation repeatedly: remove an element, then insert it at any position in the list, shifting elements if necessary. What is the minimum number of applications of this operation necessary to sort $A$?