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?

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

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

In concurrent computing, two processes may have their steps interwoven in an unknown order, as long as the steps of each process occur in order. Consider the following two processes: \begin{tabular}{c|cc} Process & $A$ & $B$\\ \hline Step 1 & $x\leftarrow x-4$ & $x\leftarrow x-5$\\ Step 2 & $x\leftarrow x\cdot3$ & $x\leftarrow x\cdot4$\\ Step 3 & $x\leftarrow x-4$ & $x\leftarrow x-5$\\ Step 4 & $x\leftarrow x\cdot3$ & $x\leftarrow x\cdot4$ \end{tabular} One such interweaving is $A1$, $B1$, $A2$, $B2$, $A3$, $B3$, $B4$, $A4$, but $A1$, $A3$, $A2$, $A4$, $B1$, $B2$, $B3$, $B4$ is not since the steps of $A$ do not occur in order. We run $A$ and $B$ concurrently with $x$ initially valued at $6$. Find the minimal possible value of $x$ among all interweavings.

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

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.

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.

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?

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]

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

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]

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?