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.

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

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

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

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?

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

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?

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

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

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?

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

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?