Found problems: 6
2023 CMIMC TCS, 2
After years at sail, you and your crew have found the island that houses the great treasure of Scottybeard, the greatest pirate to ever sail the high seas. The island takes the shape of a unit square, and the treasure (which we treat as a single point) could be buried under any point on the island.
To assist you in finding his treasure, Scotty has left a peculiar instrument. To use this instrument, you may draw any directed line (possibly one that never hits the island!), and the instrument will tell you whether the treasure lies to the "left" or the "right" of the line.*
[asy]
draw((0,0)--(1,0)--(1,1)--(0,1)--cycle);
draw((1,0.5)--(0.8,0.42),arrow=Arrow());
draw((0.8,0.42)--(0.6,0.34),arrow=Arrow());
draw((0.6,0.34)--(0.4,0.26),arrow=Arrow());
draw((0.4,0.26)--(0.2,0.18),arrow=Arrow());
draw((0.2,0.18)--(0,0.1));
label("``Right''", (0.5,0.55));
label("``Left''", (0.8,0.2));
[/asy]
However, Scotty also left a trap! If the instrument ever reports ``left'' three times in a row or ``right'' three times in a row, the island will suddenly sink into the sea, submerging the treasure forever and drowning you and your crew! You want to avoid this at all costs.
To minimize the amount of energy spent digging, you would like to narrow down the set of possible locations of the treasure to be as small as possible. However, Scotty left one last trick; you can only use the instrument 12 times before it breaks!
Devise an algorithm to use the instrument no more than 12 times that can never result in the island sinking and narrows the worst-case space of possible locations of the treasure to have as small an area as possible.
* [size=75]Where "left" or "right" is taken with respect to an observer walking along the line in its designated direction. There is also a probability zero chance the treasure is precisely on the line; this won't affect anything, but for the sake of clarity let's say the instrument reports "left" in this case.[/size]
[b]Scoring:[/b] An algorithm that achieves a worst-case area of $K$ will be awarded:
[list]
[*] 1 point for any $K<1$
[*] 10 points for $K=\tfrac 14$
[*] 20 points for $\tfrac 1{128}<K<\tfrac 14$
[*] 30 points for $K=\tfrac 1{128}$
[*] 50 points for $K_{\text{min}}<K<\tfrac 1 {128}$
[*] 75 points for $K=K_{\text{min}}$
[*] 100 points for $K=K_{\text{min}}$, with a proof that this is optimal
[/list]
(where $K_{\text{min}}$ is the smallest possible worst-case area, which we are not disclosing to avoid giving anything away)
[i]Proposed by Connor Gordon[/i]
2023 CMIMC TCS, 3
You are given a deck of $n \cdot m$ different cards where $n$ and $m$ are fixed numbers both between $10^{99}$ and $10^{100}$. You perform an [i]$m$-perfect shuffle[/i] for some times. In a single $m$-perfect shuffle, you divide the deck into $m$ piles with $n$ consecutive cards in each pile. You take one card from each pile, in order of the piles, for $n$ times to form the new deck. (The $m$-perfect shuffle is deterministic)
For example, if the cards are labeled 12345678 where $n=4$ and $m=2$, you divide the deck into 1234 and 5678, and after one $2$-perfect shuffle you get 15263748. In another example, if the cards are labeled 123456789 where $n=3$ and $m=3$, you divide the deck into 123, 456, and 789, and after one $3$-perfect shuffle you get 147258369.
Find an algorithm that, in at most $k$ steps, outputs the smallest positive number of $m$-perfect shuffle after which the deck is exactly the same as the original deck. In each step, you can do one arithmetic operation in $\{+, -, *, /, \bmod\}$, do one comparison, break out of a loop, or store one number to a specific location of an array. You can use the following precomputed numbers of steps in your solution:
[list]
[*] Checking if $a$ divides $b$ for any two integers $a$ and $b$ takes 2 steps because you need to compute $b \bmod a$ then compare with $0$.
[*]A loop over $k$ iterations takes $2k$ steps because you need to increment the loop index by $1$ $k$ times and check the loop guard $k$ times.
[*]Simulating one "$m$-perfect shuffle" takes $7nm$ steps because there is one loop index increment, four arithmetic operations, and one store in each iteration of the loop.
[/list]
[b]Scoring:[/b]
An algorithm that completes in at most $k$ steps will be awarded:
[list]
[*] 1 pt for $k > 10^{10^{10^{10}}}$
[*] 10 pts for $k = 10^{10^{10^{10}}}$
[*] 20 pts for $k = 10^{420}$
[*] 30 pts for $k = 10^{360}$
[*] 50 pts for $k = 10^{240}$
[*] 70 pts for $k = 10^{202}$
[*] 80 pts for $k = 10^{201}$
[*] 95 pts for $k = 10^{120}$
[*] 98 pts for $k = 10^{102}$
[*] 100 pts for $k = 10^{101}$
[/list]
[i]Proposed by Mingkuan Xu[/i]
2024 CMIMC Theoretical Computer Science, 1
Mellon Game Lab has come up with a concept for a new game: Square Finder. The premise is as follows. You are given an $n\times n$ grid of squares (for integer $n\geq 2$), each of which is either blank or has an arrow pointing up, down, left, or right. You are also given a $2\times 2$ grid of squares that appears somewhere in this grid, possibly rotated. For example, see if you can find the following $2\times 2$ grid inside the larger $4\times 4$ grid.
[asy]
size(2cm);
defaultpen(fontsize(16pt));
string b = "";
string u = "$\uparrow$";
string d = "$\downarrow$";
string l = "$\leftarrow$";
string r = "$\rightarrow$";
// input should be n x n
string[][] input =
{{b,u},{r,l}};
int n = input.length;
// draw table
for (int i=0; i<=n; ++i)
{
draw((i,0)--(i,n));
draw((0,i)--(n,i));
}
// fill table
for (int i=1; i<=n; ++i)
{
for (int j=1; j<=n; ++j)
{
label(input[i-1][j-1], (j-0.5,n-i+0.5));
}
}
[/asy]
[asy]
size(4cm);
defaultpen(fontsize(16pt));
string b = "";
string u = "$\uparrow$";
string d = "$\downarrow$";
string l = "$\leftarrow$";
string r = "$\rightarrow$";
// input should be n x n
string[][] input =
{{u,b,b,r},{b,r,u,d},{d,b,u,b},{u,r,b,l}};
int n = input.length;
// draw table
for (int i=0; i<=n; ++i)
{
draw((i,0)--(i,n));
draw((0,i)--(n,i));
}
// fill table
for (int i=1; i<=n; ++i)
{
for (int j=1; j<=n; ++j)
{
label(input[i-1][j-1], (j-0.5,n-i+0.5));
}
}
[/asy]
Did you spot it? It's in the bottom left, rotated by $90^\circ$ clockwise. To make the game as interesting as possible, Mellon Game Lab would like the grid to be as large as possible and for no $2\times 2$ grid to appear more than once in the big grid. The grid above doesn't work, as the following $2\times 2$ grid appears twice, once in the top left corner (rotated $90^\circ$ counterclockwise) and once directly below it (overlapping).
[asy]
size(2cm);
defaultpen(fontsize(16pt));
string b = "";
string u = "$\uparrow$";
string d = "$\downarrow$";
string l = "$\leftarrow$";
string r = "$\rightarrow$";
// input should be n x n
string[][] input =
{{b,r},{d,b}};
int n = input.length;
// draw table
for (int i=0; i<=n; ++i)
{
draw((i,0)--(i,n));
draw((0,i)--(n,i));
}
// fill table
for (int i=1; i<=n; ++i)
{
for (int j=1; j<=n; ++j)
{
label(input[i-1][j-1], (j-0.5,n-i+0.5));
}
}
[/asy]
Let's call a grid that avoids such repeats a [i]repeat-free grid[/i]. We are interested in finding out for which $n$ constructing an $n\times n$ repeat-free grid is possible. Here's what we know so far.
[list]
[*] Any $2\times 2$ grid is repeat-free, as there is only one subgrid to worry about, and there can't possibly be any repeats.
[*] If we can construct an $n\times n$ repeat-free grid, we can also construct a $k\times k$ repeat-free grid for any $k\leq n$ by just taking the top left $k\times k$ of the original one we found.
[*] By the previous observation, if it is impossible to construct such an $n\times n$ repeat-free grid, we cannot construct a $k\times k$ repeat-free grid for any $k\geq n$, as otherwise we could take the top left $n\times n$ to get one working for $n$.
[/list]
These three observations together tell us that either we can construct an $n\times n$ repeat-free grid for all $n\geq 2$, or there exists some upper limit $N\geq 2$ such that we can construct an $n\times n$ repeat-free grid for all $n\leq N$ but cannot construct one for any $n> N$. Your goal is to determine if such an $N$ exists, and if so, place bounds on its value.
More precisely, this problem consists of two parts: a lower bound and an upper bound. For the lower bound, to show that $N\geq n$ for some $n$, you need to construct an $n\times n$ repeat-free grid (you do not need to prove your construction works). For the upper bound, to show that $N$ is at most some value $n$, you must prove that it is impossible to construct an $(n+1)\times (n+1)$ repeat-free grid.
[i]Proposed by Connor Gordon and Eric Oh[/i]
2023 CMIMC TCS, 1
Carnegie Corporation is trying to promote a new department director from its employees. Carnegie Corporation has $n$ employees each with some unknown real-valued score and wants to pick the $M$-th highest scoring employee to be the new department director. The corporation has a magical machine that, once a day, can be used to compare two employees to see which one has a higher score. Unfortunately, this machine has a magical consequence: after every $k$ uses of this machine, if a new department director has not been chosen by the end of the day, one random employee is fired and a new employee (who has not necessarily the same score) is hired. Assume no two employees have equal scores and scores don't change over time.
Machines with a higher constant of $k$ will be more expensive, so management wants to minimize the value of $k$. Devise an algorithm which uses the minimum possible $k$ guaranteeing that, given any $1\leq M \leq n$, we can promote the $M$-th highest scoring employee as the new department director in finitely many days.
[b]Scoring:[/b] An algorithm that solves the case for a certain $k$ in terms of $n\geq 2$ and some constant $c\in \mathbb{R}^+$ will be awarded:
[list]
[*] $10$ pts for any finite $k$
[*] $20$ pts for any $k\leq cn\log(n)$ for some constant $c>0$
[*] $40$ pts for any $k\leq cn$ for some constant $c>1$
[*] $70$ pts for $k\leq n$
[*] $85$ pts for $k\leq n-\lfloor\sqrt{n/2}-\tfrac{1}{2}\rfloor + 1$
[*] $100$ pts for $k\leq n-\lfloor\sqrt{n}-\tfrac{1}{2}\rfloor + 1$
[/list]
[i]Proposed by David Tang[/i]
2024 CMIMC Theoretical Computer Science, 3
In this problem, we explore a variant of the Monty Hall Problem.
There are $n$ doors numbered $1, \dots, n$. A single gold coin is placed randomly behind one of the doors, with the probability it is placed behind door $i$ equalling $p_i.$ There are $r$ "rounds" in which we may make at most $k$ "turns" each, defined as follows:
During a "turn", you pick two doors and send them to the game host. Then, the host picks one of the two doors in the following manner:
[list]
[*]If neither door contains the coin, the host randomly picks one with equal probability.
[*] If one of the doors contains the coin, the host picks the door which does not have the coin.
[/list]
The host reveals that the picked door does not contain the coin, and opens it.
A "round" consists of Alice performing at least 1 and at most $k$ turns. After all the turns in round $j$ are complete, suppose there are $d_j$ doors remaining. Bob will compute the probability of each individual door containing the coin. Let $m_j$ be the minimum of these probabilities computed during the $j$th round. Then, Bob awards Alice $d_jm_j$ points. Note that Bob will pay Alice $r$ times, and Alice's total payout is the sum of the $r$ individual payouts. Note that opened doors remain revealed between rounds.
Suppose $S$ is some strategy that determines which doors Alice sends to the host. Let $F(S, n,k,r,(p_1, \dots, p_n))$ be the minimum possible amount Alice could earn with strategy $S$ for parameters $(n,k,r,(p_1, \dots, p_n))$, and let \[G(n,k,r,(p_1, \dots, p_n))= \max\limits _S F(S, n,k,r,(p_1, \dots, p_n)).\]
Find all tuples $(n,k,r,(p_1, \dots, p_n))$ for which $G(n,k,r,(p_1, \dots, p_n))=r.$ You may find it useful to consider lists where each element of a list is at most double the prior element.
[i]Proposed by Hari Desikan[/i]
2024 CMIMC Theoretical Computer Science, 2
There are two different versions of this problem, each with different solutions. You must find bounds for each of these problems.
[list]
[*] Alice and Bob are playing a collaborative game in which they agree upon an encoding/strategy. Alice shuffles a deck of 52 cards (numbered 1-52) (*) and takes the first $n$ cards off the top of the deck. Alice then chooses one card to be put to the side, and chooses an ordering of the other $n-1$ cards. Bob then walks into the room seeing the $n-1$ cards in the order Alice put them in. For example, if Alice was given 9-4-10-51-7-8 and chose to put 8 to the side, she could put 5 cards in order of 9-4-10-51-7 which Bob would see.
Find the lowest $n$ for which Bob could guarantee that he could use Alice's encoding to find the card placed to the side.
(*) (If you would prefer, you can write your solution in terms of the deck being a standard deck with 4 suits and 13 ranks, there's a way to move between them that we can handle.)
[*] Alice and Bob are playing a collaborative game in which they agree upon an encoding/strategy. Alice shuffles a deck of 52 cards (numbered 1-52) and takes the first $n$ cards off the top of the deck. Alice then chooses one card to be put to the side, and chooses an ordering of the other $n-1$ cards. Carol then comes in to the room and randomly discards one of the $n-1$ cards, and places the cards back in a way that preserves the order Alice had. Bob then walks into the room seeing the $n-2$ cards in the order Alice put them in. For example, if Alice was given 1-2-3-4-5-6 and chose to put 6 to the side, she would put 5 cards in order of 1-2-3-4-5, and Carol removed 4, Bob would see 1-2-3-5.
Find the lowest $n$ for which Bob could guarantee that he could use Alice's encoding to find the card placed to the side.
[/list]
[i]Proposed by Eric Oh[/i]