User:Vqbc/Testing

\section{HMMT Spring 2021 \\ March 06, 2021 \\ Combinatorics Round}

1. Leo the fox has a 5 by 5 checkerboard grid with alternating red and black squares. He fills in the grid with the numbers $1,2,3, \ldots, 25$ such that any two consecutive numbers are in adjacent squares (sharing a side) and each number is used exactly once. He then computes the sum of the numbers in the 13 squares that are the same color as the center square. Compute the maximum possible sum Leo can obtain.

Proposed by: Milan Haiman

\section{Answer: 169}

Solution: Since consecutive numbers are in adjacent squares and the grid squares alternate in color, consecutive numbers must be in squares of opposite colors. Then the odd numbers $1,3,5, \ldots, 25$ all share the same color while the even numbers $2,4, \ldots, 24$ all share the opposite color. Since we have 13 odd numbers and 12 even numbers, the odd numbers must correspond to the color in the center square, so Leo's sum is always $1+3+5+\cdots+25=169$

2. Ava and Tiffany participate in a knockout tournament consisting of a total of 32 players. In each of 5 rounds, the remaining players are paired uniformly at random. In each pair, both players are equally likely to win, and the loser is knocked out of the tournament. The probability that Ava and Tiffany play each other during the tournament is $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers. Compute $100 a+b$ .

Proposed by: Sheldon Kieren Tan

\section{Answer: 116}

Solution: Each match eliminates exactly one player, so exactly $32-1=31$ matches are played, each of which consists of a different pair of players. Among the $\left(\begin{array}{c}32 \\ 2\end{array}\right)=\frac{32 \cdot 31}{2}=496$ pairs of players, each pair is equally likely to play each other at some point during the tournament. Therefore, the probability that Ava and Tiffany form one of the 31 pairs of players that play each other is $\frac{31}{496}=\frac{1}{16}$ , giving an answer of $100 \cdot 1+16=116$ .

3. Let $N$ be a positive integer. Brothers Michael and Kylo each select a positive integer less than or equal to $N$ , independently and uniformly at random. Let $p_{N}$ denote the probability that the product of these two integers has a units digit of 0 . The maximum possible value of $p_{N}$ over all possible choices of $N$ can be written as $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers. Compute $100 a+b .$

\section{Proposed by: James Lin}

\section{Answer: 2800}

Solution: For $k \in\{2,5,10\}$ , let $q_{k}=\frac{\lfloor N / k\rfloor}{N}$ be the probability that an integer chosen uniformly at random from $[N]$ is a multiple of $k$ . Clearly, $q_{k} \leq \frac{1}{k}$ , with equality iff $k$ divides $N .$

The product of $p_{1}, p_{2} \in[N]$ can be a multiple of 10 in two ways:

- one of them is a multiple of $10 ;$ this happens with probability $q_{10}\left(2-q_{10}\right) ;$

- one of them is a multiple of 2 (but not 5 ) and the other is a multiple of 5 (but not 2 ); this happens with probability $2\left(q_{2}-q_{10}\right)\left(q_{5}-q_{10}\right)$ . This gives

$\begin{align*} p_{N} &=q_{10} \cdot\left(2-q_{10}\right)+2\left(q_{2}-q_{10}\right)\left(q_{5}-q_{10}\right) \\ & \leq q_{10} \cdot\left(2-q_{10}\right)+2\left(\frac{1}{2}-q_{10}\right)\left(\frac{1}{5}-q_{10}\right) \\ &=\frac{1}{5}\left(1+3 q_{10}+5 q_{10}^{2}\right) \\ & \leq \frac{1}{5}\left(1+\frac{3}{10}+\frac{5}{100}\right) \\ &=\frac{27}{100} \end{align*}$

and equality holds iff $N$ is a multiple of $10 .$

4. Let $S=\{1,2, \ldots, 9\} .$ Compute the number of functions $f: S \rightarrow S$ such that, for all $s \in S, f(f(f(s)))=$ $s$ and $f(s)-s$ is not divisible by $3 .$

Proposed by: James Lin

Answer: 288

Solution: Since $f(f(f(s)))=s$ for all $s \in S$ , each cycle in the cycle decomposition of $f$ must have length 1 or 3 . Also, since $f(s) \not \equiv s \bmod 3$ for all $s \in S$ , each cycle cannot contain two elements $a, b$ such that $a=b$ mod $3 .$ Hence each cycle has exactly three elements, one from each of residue classes mod $3 .$

In particular, $1,4,7$ belong to distinct cycles. There are $6 \cdot 3$ ways to choose two other numbers in the cycle containing 1. Then, there are $4 \cdot 2$ ways to choose two other numbers in the cycle containing 4 . Finally, there are $2 \cdot 1$ ways to choose two other numbers in the cycle containing 7 . Hence the desired number of functions $f$ is $6 \cdot 3 \cdot 4 \cdot 2 \cdot 2 \cdot 1=288$ .

5. Teresa the bunny has a fair 8-sided die. Seven of its sides have fixed labels $1,2, \ldots, 7$ , and the label on the eighth side can be changed and begins as 1 . She rolls it several times, until each of $1,2, \ldots, 7$ appears at least once. After each roll, if $k$ is the smallest positive integer that she has not rolled so far, she relabels the eighth side with $k$ . The probability that 7 is the last number she rolls is $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers. Compute $100 a+b .$

Proposed by: Milan Haiman

Answer: 104

Solution 1: Let $n=7$ and $p=\frac{1}{4}$ .

Let $q_{k}$ be the probability that $n$ is the last number rolled, if $k$ numbers less than $n$ have already been rolled. We want $q_{0}$ and we know $q_{n-1}=1$ .

We have the relation

$q_{k}=(1-p) \frac{k}{n-1} q_{k}+\left[1-(1-p) \frac{k+1}{n-1}\right] q_{k+1}$

This rearranges to

$\left[1-(1-p) \frac{k}{n-1}\right] q_{k}=\left[1-(1-p) \frac{k+1}{n-1}\right] q_{k+1}$

This means that the expression on the LHS does not depend on $k$ , so

$[1-0] \cdot q_{0}=[1-(1-p)] \cdot q_{n-1}=p$

Solution 2: For a given sequence of Teresa's rolls, let $x_{i}$ be the $i$ th distinct number rolled. We want to compute the probability that $x_{7}=7$ .

For a given index $i$ , we say that $x_{i}$ is correct if $x_{i}$ is the least positive integer not in $\left\{x_{1}, \ldots, x_{i-1}\right\} .$ Note that the probability of a given sequence $x_{1}, \ldots, x_{7}$ depends only on the number of correct $x_{i}$ , since the probability of rolling the correct number on a given roll is higher by a factor of $2 .$

Now, suppose $x_{7}=7$ . Consider $x_{i}^{\prime}=x_{i-1}+1$ for $1<i \leq 7$ , and $x_{1}^{\prime}=1$ . Note that this operation on sequences $x_{1}, \ldots, x_{7}$ pairs sequences ending in 7 with sequences starting with 1 . Additionally, we have that $x_{7}$ and $x_{1}^{\prime}$ are both correct, and that $x_{i}^{\prime}$ is correct if and only if $x_{i-1}$ is correct. Thus $x_{1}, \ldots, x_{7}$ and $x_{1}^{\prime}, \ldots, x_{7}^{\prime}$ have the same probability.

So, we conclude that the probability of $x_{7}=7$ is the same as the probability of $x_{1}=1 .$ But this is just $\frac{1}{4}$ .

6. A light pulse starts at a corner of a reflective square. It bounces around inside the square, reflecting off of the square's perimeter $n$ times before ending in a different corner. The path of the light pulse, when traced, divides the square into exactly 2021 regions. Compute the smallest possible value of $n$ .

Proposed by: Krit Boonsiriseth

Answer: 129

Solution: The main claim is that if the light pulse reflects vertically (on the left/right edges) $a$ times and horizontally $b$ times, then gcd $(a+1, b+1)=1$ , and the number of regions is $\frac{(a+2)(b+2)}{2} .$ This claim can be conjectured by looking at small values of $a$ and $b$ ; we give a full proof at the end.

Assuming the claim, we are trying to find the least possible value of $a+b$ when $(a+2)(b+2)=2 \cdot 2021=$ $2 \cdot 43 \cdot 47 .$ This happens when $(a+2, b+2)=(47,86)$ , which also satisfies ged $(a+1, b+1)=1$ , and gives $a+b=47+86-4=129$ .

We now prove the claim. Imagine that at each reflection, it is the square that gets reflected instead. Then the path $p$ of the light pulse becomes a straight segment $s$ from $(0,0)$ to $(a+1, b+1)$ of slope $+m=\frac{a+1}{b+1}$ .

- The square starts as 1 region; the light pulse hitting a corner at the end creates 1 more region.

- Each reflection of the light pulse creates a region. These correspond to intersections of $s$ with a line $x=n$ or $y=n$ for $x \in[a], y \in[b] .$ There are $a+b$ such intersections.

- Each self-intersection of $p$ creates a region. An intersection on $p$ corresponds to two on $s$ , and each intersection of $s$ happens with a line of slope $-m$ passing through an even integral point, i.e. a line of the form $(b+1) x+(a+1) y=2 k$ . The open segment $s$ intersects these lines for $k \in[a b+a+b] .$ However, the $a+b$ intersections that happens on a gridline $x \in \mathbb{Z}$ or $y \in \mathbb{Z}$ do not count, so here we have an additional $a b / 2$ regions.

Therefore, the total number of regions is

$2+a+b+\frac{a b}{2}=\frac{(a+2)(b+2)}{2}$

7. Let $S=\{1,2, \ldots, 2021\}$ , and let $\mathcal{F}$ denote the set of functions $f: S \rightarrow S .$ For a function $f \in \mathcal{F}$ , let

$T_{f}=\left\{f^{2021}(s): s \in S\right\}$

where $f^{2021}(s)$ denotes $f(f(\cdots(f(s)) \cdots))$ with 2021 copies of $f .$ Compute the remainder when

$\sum_{f \in \mathcal{F}}\left|T_{f}\right|$

is divided by the prime 2017, where the sum is over all functions $f$ in $\mathcal{F}$ .

Proposed by: Milan Haiman

\section{Answer: 255}

Solution: The key idea is that $t \in T_{f}$ if and only if $f^{k}(t)=t$ for some $k>0$ . To see this, let $s \in S$ and consider

$s, f(s), f(f(s)), \ldots, f^{2021}(s)$

This sequence has 2022 terms that are all in $S$ , so we must have a repeat. Suppose $f^{m}(s)=f^{n}(s)$ with $0 \leq n<m \leq 2021$ . Then $f^{2021}(s)=f^{2021+m-n}(s) .$ In particular, for $t=f^{2021}(s)$ , we have $f^{k}(t)=t$ with $k=m-n .$ On the other hand, if $f^{k}(t)=t$ , then letting $s=f^{2021 k-2021}(t)$ gives $f^{2021}(s)=t .$

We will compute the number of $f$ for which $f^{k}(1)=1$ for some $k$ , and then multiply by 2021 . We do this by casework on the minimum possible value of $k$ .

Given $k$ , we just need to choose distinct values in $\{2, \ldots, 2021\}$ for each of $f^{1}(1), f^{2}(1), \ldots, f^{k-1}(1)$ . We have $\frac{2020 !}{(2021-k) !}$ ways to do this. For each of the $2021-k$ other values with $f$ not yet determined, we can do anything we want, giving $2021^{2021-k}$ choices.

SO,

$\sum_{f \in \mathcal{F}}\left|T_{f}\right|=2021 \sum_{k=1}^{2021} \frac{2020 !}{(2021-k) !} \cdot 2021^{2021-k}$

Taking this mod 2017, all terms with $k>4$ reduce to 0, and $2021^{2021-k}$ reduces to $4^{5-k}$ for $k \leq 4 .$ We are thus left with

$\sum_{f \in \mathcal{F}}\left|T_{f}\right| \equiv 4\left[4^{4}+3 \cdot 4^{3}+3 \cdot 2 \cdot 4^{2}+3 \cdot 2 \cdot 1 \cdot 4^{1}\right] \equiv 255 \quad(\bmod 2017)$

8. Compute the number of ways to fill each cell in a $8 \times 8$ square grid with one of the letters $H, M$ , or $T$ such that every $2 \times 2$ square in the grid contains the letters $H, M, M, T$ in some order.

Proposed by: Sheldon Kieren Tan

Answer: 1076

Solution: We solve the problem for general $n \times n$ boards where $n$ even. Let the cell in the $i$ -th row and $j$ -th column be $a_{i, j}$ .

Claim: In any valid configuration, either the rows (or columns) alternate between $(\cdots, H, M, H, M, \cdots)$ and $(\cdots, T, M, T, M, \cdots)$ or $(\cdots, M, M, M, M, \cdots)$ and $(\cdots, H, T, H, T, \cdots)$ .

Proof: First note that all configurations which follow the above criteria are valid.

If the rows alternate as above we are done. Else there exists one of the below configurations in one of the rows, from which we can deduce the rest of the 3 columns as follows:

$\begin{array}{||c|c|c||} \hline\left(a_{i, j-1}, a_{i, j}, a_{i, j+1}\right) & \left(a_{i+1, j-1}, a_{i+1, j}, a_{i+1, j+1}\right) & \left(a_{i+2, j-1}, a_{i+2, j}, a_{i+2, j+1}\right) \\ \hline \hline(H, M, T) & (T, M, H) & (H, M, T) \\ \hline(T, M, H) & (H, M, T) & (T, M, H) \\ \hline(H, T, M) & (M, M, H) & (H, T, M) \\ \hline(M, T, H) & (H, M, M) & (M, T, H) \\ \hline(T, H, M) & (M, M, T) & (T, H, M) \\ \hline(M, H, T) & (T, M, M) & (M, H, T) \\ \hline(T, M, M) & (M, H, T) & (T, M, M) \\ \hline(M, M, T) & (T, H, M) & (M, M, T) \\ \hline(H, M, M) & (M, T, H) & (H, M, M) \\ \hline(M, M, H) & (H, T, M) & (M, M, H) \\ \hline \end{array}$

It can be noted that the configurations alternate as we move down/up the columns, implying that the 3 columns consist of alternating letters (or $(M, M, \cdots)$ ). We can now check that all columns obey the above form, and in particular, must alternate as stated in the claim.

It now suffices to count the number of cases. When the rows alternate between $(\cdots, H, M, H, M, \cdots)$ and $(\cdots, T, M, T, M, \cdots)$ , there are 2 ways to choose which one occupies the odd-numbered rows, and $2^{n}$ ways to alternate between the 2 letters in each row. When the rows alternate between $(\cdots, H, T, H, T, \cdots)$ and $(\cdots, M, M, M, M, \cdots)$ , there are 2 ways to choose which occupies the oddnumbered rows, and $2^{\frac{n}{2}}$ ways to alternate between the 2 letters in the rows. The number of cases for columns is the same.

Finally, if both the rows and columns alternate as above, it suffices to fix the first 2 rows (then the rest of the board is uniquely determined by extending the columns). There are $2 \times 2^{2}=8$ ways to do this if the rows are $(\cdots, H, M, H, M, \cdots)$ and $(\cdots, T, M, T, M, \cdots)$ , and $2 \times 2=4$ ways to do this if the rows are $(\cdots, M, M, M, M, \cdots)$ and $(\cdots, H, T, H, T, \cdots)$ .

Hence the total number of configurations is $2\left(2^{n+1}+2^{\frac{n}{2}+1}\right)-12=2^{n+2}+2^{\frac{n}{2}+2}-12$ .

9. An up-right path between two lattice points $P$ and $Q$ is a path from $P$ to $Q$ that takes steps of length 1 unit either up or to the right.

How many up-right paths from $(0,0)$ to $(7,7)$ , when drawn in the plane with the line $y=x-2.021$ , enclose exactly one bounded region below that line?

Proposed by: Anders Olsen

\section{Answer: 637}

Solution: We will make use of a sort of bijection which is typically used to prove the closed form for the Catalan numbers. 1 We will count these paths with complementary counting. Since both the starting and ending points are above the line $x-2.021$ , any path which traverses below this line (and hence includes a point on the line $y=x-3)$ will enclose at least one region. In any such path, we can reflect the portion of the path after the first visit to the line $y=x-3$ over that line to get a path from $(0,0)$ to $(10,4)$ . This process is reversible for any path to $(10,4)$ , so the number of paths enclosing at least one region is $\left(\begin{array}{c}14 \\ 4\end{array}\right)$ .

More difficult is to count the paths that enclose at least two regions. For any such path, consider the first and final times it intersects the line $y=x-3 .$ Since at least two regions are enclosed, there must be some point on the intermediate portion of the path on the line $y=x-2$ . Then we can reflect only this portion of the path over the line $y=x-3$ to get a new path containing a point on the line $y=x-4$ . We can then do a similar reflection starting from the first such point to get a path from $(0,0)$ to $(11,3)$ . This process is reversible, so the number of paths which enclose at least two regions is $\left(\begin{array}{c}14 \\ 3\end{array}\right)$ . Then the desired answer is just $\left(\begin{array}{c}14 \\ 4\end{array}\right)-\left(\begin{array}{c}14 \\ 3\end{array}\right)=637$ .

10. Jude repeatedly flips a coin. If he has already flipped $n$ heads, the coin lands heads with probability $\frac{1}{n+2}$ and tails with probability $\frac{n+1}{n+2}$ . If Jude continues flipping forever, let $p$ be the probability that he flips 3 heads in a row at some point. Compute $\lfloor 180 p\rfloor$ .

Proposed by: Anders Olsen

\section{Answer: 47}

Solution: Let $p_{n}$ be the probability that the $n$ th head is flipped after a tail and Jude has yet to flip 3 heads consecutively to this point. For example, $p_{2}=\frac{2}{3}$ , as it is impossible for 3 heads to be flipped consecutively and the second head comes after a tail exactly when the first flip after the first head is a

'See https://en.wikipedia.org/wiki/Catalan_number\%23Second_proof for useful pictures tail, which happens with probability $\frac{2}{3}$ . Similarly, $p_{3}=\frac{3}{4}$ . We now establish a recursion between values of $p_{n}$ :

$p_{n}=\frac{n}{n+1} p_{n-1}+\frac{1}{n+1} p_{n-2} .$

The first term comes from when the previous head had tails both before and after, and the second term comes from when the previous 2 heads were consecutive. Of course there cannot be other terms, as this would imply that 3 heads were flipped consecutively. This enables us to easily compute the next few terms: $\frac{11}{15}, \frac{53}{72}, \frac{103}{140}$ , and so on. Notably, the differences between consecutive terms (starting from $\left.p_{3}-p_{2}\right)$ are $\frac{2}{24},-\frac{2}{120}, \frac{2}{720},-\frac{2}{5040}$ , and so on. This leads us to guess that $p_{n}=2 \sum_{i=0}^{n+1} \frac{(-1)^{i}}{i !}$ , which indeed satisfies the given recurrence relation. Then

$\lim _{n \rightarrow \infty} p_{n}=2 \sum_{i=0}^{\infty} \frac{(-1)^{i}}{i !}=\frac{2}{e} .$

But since the probability that the $n$ th head comes after a tail approaches 1 as $n$ increases, this limit is the same as the limit of the probability that the first $n$ heads do not include 3 that came consecutively. Then this limit is just the probability that we never flip 3 consecutive heads. Then the desired probability is just $p=1-\frac{2}{e}$ . We are asked to compute $\lfloor 180 p\rfloor$ . This is the floor of $180-\frac{360}{e}$ . To compute $360 / e$ , note that we can just truncate the infinite sum

$\frac{360}{e}=\sum_{n=0}^{\infty} \frac{360(-1)^{n}}{n !}$

as it converges rather quickly. The first several terms are $360-360+180-60+15-3+\frac{1}{2}$ , and the rest are insignificant. This sums to about $132.5$ , giving an answer of $\lfloor 180-132.5\rfloor=47$ .

Page

Toolbox

Search

User:Vqbc/Testing