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?

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

A $\emph{planar}$ graph is a connected graph that can be drawn on a sphere without edge crossings. Such a drawing will divide the sphere into a number of faces. Let $G$ be a planar graph with $11$ vertices of degree $2$, $5$ vertices of degree $3$, and $1$ vertex of degree $7$. Find the number of faces into which $G$ divides the sphere.

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]

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

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?

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

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?

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

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?

We consider a simple model for balanced parenthesis checking. Let $\mathcal R=\{\texttt{(())}\rightarrow \texttt{A},\texttt{(A)}\rightarrow\texttt{A},\texttt{AA}\rightarrow\texttt{A}\}$ be a set of rules for phrase reduction. Ideally, any given phrase is balanced if and only if the model is able to reduce the phrase to $\texttt{A}$ by some arbitrary sequence of rule applications. For example, to show $\texttt{((()))}$ is balanced we can perform the following sequence of reductions. \[\texttt{((()))}\rightarrow\texttt{(A)}\rightarrow\texttt{A}\qquad \checkmark\] Unfortunately, the above set of rules $\mathcal R$ is not complete, since there exist parenthetical phrases which are balanced but which are not balanced according to $\mathcal R$. Determine the number of such phrases of length $14$.

Let $a_n$ be the number of ways to express $n$ as an ordered sum of powers of $3.$ For example $a_4=3,$ since $$4=1+1+1+1=1+3=3+1.$$ Let $b_n$ denote the remainder upon dividing $a_n$ by $3.$ Evaluate $$\sum_{n=1}^{3^{2025}} b_n.$$

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

Let $n$ and $k$ be positive integers, with $k \le n.$ Define a (simple, undirected) graph $G_{n,k}$ as follows: its vertices are all of the binary strings of length $n,$ and there is an edge between two strings if and only if they differ in exactly $k$ positions. If $c_{n,k}$ denotes the number of connected components of $G_{n,k},$ compute $$\sum_{n=1}^{10} \sum_{k=1}^n c_{n,k}.$$ (For example, $G_{3,2}$ has two connected components.)

Define a string to be doubly palindromic if it can be split into two (non-empty) parts that are read the same both backwards and forwards. For example hannahhuh is doubly palindromic as it can be split into hannah and huh. How many doubly palindromic strings of length 9 using only the letters $\{a, b, c, d\}$ are there?

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

There are $34$ friends are sitting in a circle playing the following game. Every round, four of them are chosen at random, and have a rap battle. The winner of the rap battle stays in the circle and the other three leave. This continues until one player remains. Everyone has equal rapping ability, i.e. every person has equal probability to win a round. What is the probability that Michael and James end up battling in the same round?

An $\textit{access pattern}$ $\pi$ is a permutation of $\{1,2,\dots,50\}$ describing the order in which some $50$ memory addresses are accessed. We define the $\textit{locality}$ of $\pi$ to be how much the program jumps around the memory, or numerically, \[\sum_{i=2}^{50}\left\lvert\pi(i)-\pi(i-1)\right\rvert.\] If $\pi$ is a uniformly randomly chosen access pattern, what is the expected value of its locality?

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

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?

Seven cards numbered $1$ through $7$ lay stacked in a pile in ascending order from top to bottom ($1$ on top, $7$ on bottom). A shuffle involves picking a random card [i]of the six not currently on top[/i], and putting it on top. The relative order of all the other cards remains unchanged. Find the probability that, after $10$ shuffles, $6$ is higher in the pile than $3$.

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

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

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

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.