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?

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

Ryan has three distinct eggs, one of which is made of rubber and thus cannot break; unfortunately, he doesn't know which egg is the rubber one. Further, in some 100-story building there exists a floor such that all normal eggs dropped from below that floor will not break, while those dropped from at or above that floor will break and cannot be dropped again. What is the minimum number of times Ryan must drop an egg to determine the floor satisfying this property?

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

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

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?

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?

Catherine has a plate containing $300$ circular crumbling mooncakes, arranged as follows: [asy] unitsize(10); for (int i = 0; i < 16; ++i){ for (int j = 0; j < 3; ++j){ draw(circle((sqrt(3)*i,j),0.5)); draw(circle((sqrt(3)*(i+0.5),j-0.5),0.5)); } } dot((16*sqrt(3)+.5,.75)); dot((16*sqrt(3)+1,.75)); dot((16*sqrt(3)+1.5,.75)); [/asy] (This continues for $100$ total columns). She wants to pick some of the mooncakes to eat, however whenever she takes a mooncake all adjacent mooncakes will be destroyed and cannot be eaten. Let $M$ be the maximal number of mooncakes she can eat, and let $n$ be the number of ways she can pick $M$ mooncakes to eat (Note: the order in which she picks mooncakes does not matter). Compute the ordered pair ($M$, $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}

You are presented with a mystery function $f:\mathbb N^2\to\mathbb N$ which is known to satisfy \[f(x+1,y)>f(x,y)\quad\text{and}\quad f(x,y+1)>f(x,y)\] for all $(x,y)\in\mathbb N^2$. I will tell you the value of $f(x,y)$ for \$1. What's the minimum cost, in dollars, that it takes to compute the $19$th smallest element of $\{f(x,y)\mid(x,y)\in\mathbb N^2\}$? Here, $\mathbb N=\{1,2,3,\dots\}$ denotes the set of positive integers.

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?

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

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]

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

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?

Answer the following questions : [b](a)[/b] Evaluate $~~\lim_{x\to 0^{+}} \Big(x^{x^x}-x^x\Big)$ [b](b)[/b] Let $A=\frac{2\pi}{9}$, i.e. $40$ degrees. Calculate the following $$1+\cos A+\cos 2A+\cos 4A+\cos 5A+\cos 7A+\cos 8A$$ [b](c)[/b] Find the number of solutions to $$e^x=\frac{x}{2017}+1$$

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

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]

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?

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?

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

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?

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

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?

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?