MathDB

2024 CMIMC Theoretical Computer Science

Part of 2024 CMIMC

Subcontests

(3)
3
1

2024 TCS Problem 3

In this problem, we explore a variant of the Monty Hall Problem.
There are nn doors numbered 1,…,n1, \dots, n. A single gold coin is placed randomly behind one of the doors, with the probability it is placed behind door ii equalling pi.p_i. There are rr "rounds" in which we may make at most kk "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:
[*]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.
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 kk turns. After all the turns in round jj are complete, suppose there are djd_j doors remaining. Bob will compute the probability of each individual door containing the coin. Let mjm_j be the minimum of these probabilities computed during the jjth round. Then, Bob awards Alice djmjd_jm_j points. Note that Bob will pay Alice rr times, and Alice's total payout is the sum of the rr individual payouts. Note that opened doors remain revealed between rounds.
Suppose SS is some strategy that determines which doors Alice sends to the host. Let F(S,n,k,r,(p1,…,pn))F(S, n,k,r,(p_1, \dots, p_n)) be the minimum possible amount Alice could earn with strategy SS for parameters (n,k,r,(p1,…,pn))(n,k,r,(p_1, \dots, p_n)), and let G(n,k,r,(p1,…,pn))=max⁡SF(S,n,k,r,(p1,…,pn)).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,(p1,…,pn))(n,k,r,(p_1, \dots, p_n)) for which G(n,k,r,(p1,…,pn))=r.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.
Proposed by Hari Desikan
2
1

2024 TCS Problem 2

There are two different versions of this problem, each with different solutions. You must find bounds for each of these problems.
[*] 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 nn 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−1n-1 cards. Bob then walks into the room seeing the n−1n-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 nn 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 nn 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−1n-1 cards. Carol then comes in to the room and randomly discards one of the n−1n-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−2n-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 nn for which Bob could guarantee that he could use Alice's encoding to find the card placed to the side.
Proposed by Eric Oh
1
1

2024 TCS Problem 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×nn\times n grid of squares (for integer n≥2n\geq 2), each of which is either blank or has an arrow pointing up, down, left, or right. You are also given a 2×22\times 2 grid of squares that appears somewhere in this grid, possibly rotated. For example, see if you can find the following 2×22\times 2 grid inside the larger 4×44\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∘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×22\times 2 grid to appear more than once in the big grid. The grid above doesn't work, as the following 2×22\times 2 grid appears twice, once in the top left corner (rotated 90∘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 repeat-free grid. We are interested in finding out for which nn constructing an n×nn\times n repeat-free grid is possible. Here's what we know so far.
[*] Any 2×22\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×nn\times n repeat-free grid, we can also construct a k×kk\times k repeat-free grid for any k≤nk\leq n by just taking the top left k×kk\times k of the original one we found. [*] By the previous observation, if it is impossible to construct such an n×nn\times n repeat-free grid, we cannot construct a k×kk\times k repeat-free grid for any k≥nk\geq n, as otherwise we could take the top left n×nn\times n to get one working for nn.
These three observations together tell us that either we can construct an n×nn\times n repeat-free grid for all n≥2n\geq 2, or there exists some upper limit N≥2N\geq 2 such that we can construct an n×nn\times n repeat-free grid for all n≤Nn\leq N but cannot construct one for any n>Nn> N. Your goal is to determine if such an NN 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≥nN\geq n for some nn, you need to construct an n×nn\times n repeat-free grid (you do not need to prove your construction works). For the upper bound, to show that NN is at most some value nn, you must prove that it is impossible to construct an (n+1)×(n+1)(n+1)\times (n+1) repeat-free grid.
Proposed by Connor Gordon and Eric Oh