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}

We have a collection of $1720$ balls, half of which are black and half of which are white, aligned in a straight line. Our task is to make the balls alternating in color along the line. The following greedy algorithm accomplishes that task for $2n$ balls: \begin{tabular}{l} 1: \textbf{FOR} $i$ \textbf{IN} $[2,3,\dots,2n]$ \\ 2: $\quad$ \textbf{IF} balls $i-1$ and $i$ have the same color: \\ 3: $\quad\quad$ $j\gets$ smallest index greater than $i$ for which balls $i-1$ and $j$ have different colors \\ 4: $\quad\quad$ swap balls $i$ and $j$ \end{tabular} Given a configuration $C$ of our $1720$ balls, let $\hat{\sigma}(C)$ denote the number of swaps the greedy algorithm takes, and let $\sigma(C)$ denote the minimum number of swaps actually necessary to perform the task. Find the maximum value over all configurations $C$ of $\hat{\sigma}(C)-\sigma(C)$.

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?

You are given the existence of an unsorted sequence $a_1,\ldots, a_5$ of five distinct real numbers. The Erdos-Szekeres theorem states that there exists a subsequence of length $3$ which is either strictly increasing or strictly decreasing. You do not have access to the $a_i$, but you do have an oracle which, when given two indexes $1\leq i < j\leq 5$, will tell you whether $a_i < a_j$ or $a_i > a_j$. What is the minimum number of calls to the oracle needed in order to identify an ordered triple of integers $(r,s,t)$ such that $a_r,a_s,a_t$ is one such sequence?

Alice thinks of an integer $1 \le n \le 2048$. Bob asks $k$ true or false questions about Alice's integer; Alice then answers each of the questions, but she may lie on at most one question. What is the minimum value of $k$ for which Bob can guarantee he knows Alice's integer after she answers?

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?

The $\emph{Stooge sort}$ is a particularly inefficient recursive sorting algorithm defined as follows: given an array $A$ of size $n$, we swap the first and last elements if they are out of order; we then (if $n\ge3$) Stooge sort the first $\lceil\tfrac{2n}3\rceil$ elements, then the last $\lceil\tfrac{2n}3\rceil$, then the first $\lceil\tfrac{2n}3\rceil$ elements again. Given that this runs in $O(n^\alpha)$, where $\alpha$ is minimal, find the value of $(243/32)^\alpha$.

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

Consider a $4 \times 4$ grid of squares. We place coins in some of the grid squares so that no two coins are orthogonally adjacent, and each $2 \times 2$ square in the grid has at least one coin. How many ways are there to place the coins?

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?

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

I give you a function $\textbf{rand}$ that returns a number chosen uniformly at random from $[0,T]$ for some number $T$ that you don't know. Your task is to approximate $T$. You do this by calling $\textbf{rand}$ $100$ times, recording the results as $X_1,X_2,\dots,X_{100}$, and guessing \[\hat{T}=\alpha\cdot\max\{X_1,X_2,\dots,X_{100}\}\] for some $\alpha$. Which value of $\alpha$ ensures that $\mathbb{E}[\hat{T}]=T$?

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?

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.

David is taking a true/false exam with $9$ questions. Unfortunately, he doesn’t know the answer to any of the questions, but he does know that exactly $5$ of the answers are True. In accordance with this, David guesses the answers to all $9$ questions, making sure that exactly $5$ of his answers are True. What is the probability he answers at least $5$ questions correctly?

Consider the grid of numbers shown below. 20 01 96 56 16 37 48 38 64 60 96 97 42 20 98 35 64 96 40 71 50 58 90 16 89 Among all paths that start on the top row, move only left, right, and down, and end on the bottom row, what is the minimum sum of their entries?

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

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

Given a list $A$, let $f(A) = [A[0] + A[1], A[0] - A[1]]$. Alef makes two programs to compute $f(f(...(f(A))))$, where the function is composed $n$ times: \begin{tabular}{l|l} 1: \textbf{FUNCTION} $T_1(A, n)$ & 1: \textbf{FUNCTION} $T_2(A, n)$ \\ 2: $\quad$ \textbf{IF} $n = 0$ & 2: $\quad$ \textbf{IF} $n = 0$ \\ 3: $\quad$ $\quad$ \textbf{RETURN} $A$ & 3: $\quad$ $\quad$ \textbf{RETURN} $A$ \\ 4: $\quad$ \textbf{ELSE} & 4: $\quad$ \textbf{ELSE} \\ 5: $\quad$ $\quad$ \textbf{RETURN} $[T_1(A, n - 1)[0] + T_1(A, n - 1)[1],$ & 5: $\quad$ $\quad$ $B \leftarrow T_2(A, n - 1)$ \\ $\quad$ $\quad$ $\quad$ $T_1(A, n - 1)[0] - T_1(A, n - 1)[1]]$ & 6: $\quad$ $\quad$ \textbf{RETURN} $[B[0] + B[1], B[0] - B[1]]$ \\ \end{tabular} Each time $T_1$ or $T_2$ is called, Alef has to pay one dollar. How much money does he save by calling $T_2([13, 37], 4)$ instead of $T_1([13, 37], 4)$?

Max flips $2020$ fair coins. Let the probability that there are at most $505$ heads be $p$. Estimate $-\log_2(p)$ to 5 decimal places, in the form $x.abcde$ where $x$ is a positive integer and $a, b, c, d, e$ are decimal digits.

Given $x_0\in\mathbb R$, $f,g:\mathbb R\to\mathbb R$, we define the $\emph{non-redundant binary tree}$ $T(x_0,f,g)$ in the following way: [list=1] [*]The tree $T$ initially consists of just $x_0$ at height $0$. [*]Let $v_0,\dots,v_k$ be the vertices at height $h$. Then the vertices of height $h+1$ are added to $T$ by: for $i=0,1,\dots,k$, $f(v_i)$ is added as a child of $v_i$ if $f(v_i)\not\in T$, and $g(v_i)$ is added as a child of $v_i$ if $g(v_i)\not\in T$. [/list] For example, if $f(x)=x+1$ and $g(x)=x-1$, then the first three layers of $T(0,f,g)$ look like: [asy] size(100); draw((-0.1,-0.2)--(-0.4,-0.8),EndArrow(size=3)); draw((0.1,-0.2)--(0.4,-0.8),EndArrow(size=3)); draw((-0.6,-1.2)--(-0.9,-1.8),EndArrow(size=3)); draw((0.6,-1.2)--(0.9,-1.8),EndArrow(size=3)); label("$0$",(0,0)); label("$1$",(-.5,-1)); label("$-1$",(.5,-1)); label("$2$",(-1,-2)); label("$-2$",(1,-2));[/asy] If $f(x)=1024x-2047\lfloor x/2\rfloor$ and $g(x)=2x-3\lfloor x/2\rfloor+2\lfloor x/4\rfloor$, then how many vertices are in $T(2016,f,g)$?

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

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