Found problems: 63
Consider an undirected, connected graph $G$ with vertex set $\{v_1,v_2,\ldots, v_6\}$. Starting at the vertex $v_1$, an ant uses a DFS algorithm to traverse through $G$ under the condition that if there are multiple unvisited neighbors of some vertex, the ant chooses the $v_i$ with smallest $i$. How many possible graphs $G$ are there satisfying the following property: for each $1\leq i\leq 6$, the vertex $v_i$ is the $i^{\text{th}}$ new vertex the ant traverses?
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.$$
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$.
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$.
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)$?
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)$?
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?
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)$?
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$?
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?
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.
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$?
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?
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?
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?
Given the list \[A=[9,12,1,20,17,4,10,7,15,8,13,14],\] we would like to sort it in increasing order. To accomplish this, we will perform the following operation repeatedly: remove an element, then insert it at any position in the list, shifting elements if necessary. What is the minimum number of applications of this operation necessary to sort $A$?
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?
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.
Define
\[f(h,t) =
\begin{cases}
8h & h = t \\
(h-t)^2 & h \neq t.
\end{cases}\]
Cody plays a game with a fair coin, where he begins by flipping it once. At each turn in the game, if he has flipped $h$ heads and $t$ tails and $h + t < 6$, he can choose either to stop and receive $f(h,t)$ dollars or he can flip the coin again; if $h + t = 6$ then the game ends and he receives $f(h,t)$ dollars. If Cody plays to maximize expectancy, how much money, in dollars, can he expect to win from this game?
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?
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}$.
For how many distinct ordered triples $(a,b,c)$ of boolean variables does the expression $a \lor (b \land c)$ evaluate to true?
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.
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.)