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 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 all share the same color while the even numbers 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
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 , where and are relatively prime positive integers. Compute .
Proposed by: Sheldon Kieren Tan
\section{Answer: 116}
Solution: Each match eliminates exactly one player, so exactly matches are played, each of which consists of a different pair of players. Among the 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 , giving an answer of .
3. Let be a positive integer. Brothers Michael and Kylo each select a positive integer less than or equal to , independently and uniformly at random. Let denote the probability that the product of these two integers has a units digit of 0 . The maximum possible value of over all possible choices of can be written as , where and are relatively prime positive integers. Compute
\section{Proposed by: James Lin}
\section{Answer: 2800}
Solution: For , let be the probability that an integer chosen uniformly at random from is a multiple of . Clearly, , with equality iff divides
The product of can be a multiple of 10 in two ways:
- one of them is a multiple of this happens with probability
- 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 . This gives
and equality holds iff is a multiple of
4. Let Compute the number of functions such that, for all and is not divisible by
Proposed by: James Lin
Answer: 288
Solution: Since for all , each cycle in the cycle decomposition of must have length 1 or 3 . Also, since for all , each cycle cannot contain two elements such that mod Hence each cycle has exactly three elements, one from each of residue classes mod
In particular, belong to distinct cycles. There are ways to choose two other numbers in the cycle containing 1. Then, there are ways to choose two other numbers in the cycle containing 4 . Finally, there are ways to choose two other numbers in the cycle containing 7 . Hence the desired number of functions is .
5. Teresa the bunny has a fair 8-sided die. Seven of its sides have fixed labels , and the label on the eighth side can be changed and begins as 1 . She rolls it several times, until each of appears at least once. After each roll, if is the smallest positive integer that she has not rolled so far, she relabels the eighth side with . The probability that 7 is the last number she rolls is , where and are relatively prime positive integers. Compute
Proposed by: Milan Haiman
Answer: 104
Solution 1: Let and .
Let be the probability that is the last number rolled, if numbers less than have already been rolled. We want and we know .
We have the relation
This rearranges to
This means that the expression on the LHS does not depend on , so
Solution 2: For a given sequence of Teresa's rolls, let be the th distinct number rolled. We want to compute the probability that .
For a given index , we say that is correct if is the least positive integer not in Note that the probability of a given sequence depends only on the number of correct , since the probability of rolling the correct number on a given roll is higher by a factor of
Now, suppose . Consider for , and . Note that this operation on sequences pairs sequences ending in 7 with sequences starting with 1 . Additionally, we have that and are both correct, and that is correct if and only if is correct. Thus and have the same probability.
So, we conclude that the probability of is the same as the probability of But this is just .
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 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 .
Proposed by: Krit Boonsiriseth
Answer: 129
Solution: The main claim is that if the light pulse reflects vertically (on the left/right edges) times and horizontally times, then gcd , and the number of regions is This claim can be conjectured by looking at small values of and ; we give a full proof at the end.
Assuming the claim, we are trying to find the least possible value of when This happens when , which also satisfies ged , and gives .
We now prove the claim. Imagine that at each reflection, it is the square that gets reflected instead. Then the path of the light pulse becomes a straight segment from to of slope .
- 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 with a line or for There are such intersections.
- Each self-intersection of creates a region. An intersection on corresponds to two on , and each intersection of happens with a line of slope passing through an even integral point, i.e. a line of the form . The open segment intersects these lines for However, the intersections that happens on a gridline or do not count, so here we have an additional regions.
Therefore, the total number of regions is
7. Let , and let denote the set of functions For a function , let
where denotes with 2021 copies of Compute the remainder when
is divided by the prime 2017, where the sum is over all functions in .
Proposed by: Milan Haiman
\section{Answer: 255}
Solution: The key idea is that if and only if for some . To see this, let and consider
This sequence has 2022 terms that are all in , so we must have a repeat. Suppose with . Then In particular, for , we have with On the other hand, if , then letting gives
We will compute the number of for which for some , and then multiply by 2021 . We do this by casework on the minimum possible value of .
Given , we just need to choose distinct values in for each of . We have ways to do this. For each of the other values with not yet determined, we can do anything we want, giving choices.
SO,
Taking this mod 2017, all terms with reduce to 0, and reduces to for We are thus left with
8. Compute the number of ways to fill each cell in a square grid with one of the letters , or such that every square in the grid contains the letters in some order.
Proposed by: Sheldon Kieren Tan
Answer: 1076
Solution: We solve the problem for general boards where even. Let the cell in the -th row and -th column be .
Claim: In any valid configuration, either the rows (or columns) alternate between and or and .
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:
$$ (Error compiling LaTeX. Unknown error_msg)\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$ (Error compiling LaTeX. Unknown error_msg)(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$ (Error compiling LaTeX. Unknown error_msg)(\cdots, H, M, H, M, \cdots)(\cdots, T, M, T, M, \cdots)2^{n}(\cdots, H, T, H, T, \cdots)(\cdots, M, M, M, M, \cdots)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$ (Error compiling LaTeX. Unknown error_msg)2 \times 2^{2}=8(\cdots, H, M, H, M, \cdots)(\cdots, T, M, T, M, \cdots)2 \times 2=4(\cdots, M, M, M, M, \cdots)(\cdots, H, T, H, T, \cdots)$.
Hence the total number of configurations is$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)PQPQ$that takes steps of length 1 unit either up or to the right.
How many up-right paths from$ (Error compiling LaTeX. Unknown error_msg)(0,0)(7,7)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$ (Error compiling LaTeX. Unknown error_msg)x-2.021y=x-3)y=x-3(0,0)(10,4)(10,4)\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$ (Error compiling LaTeX. Unknown error_msg)y=x-3 .y=x-2y=x-3y=x-4(0,0)(11,3)\left(\begin{array}{c}14 \\ 3\end{array}\right)\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$ (Error compiling LaTeX. Unknown error_msg)n\frac{1}{n+2}\frac{n+1}{n+2}p\lfloor 180 p\rfloor$.
Proposed by: Anders Olsen
\section{Answer: 47}
Solution: Let$ (Error compiling LaTeX. Unknown error_msg)p_{n}np_{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$ (Error compiling LaTeX. Unknown error_msg)\frac{2}{3}p_{3}=\frac{3}{4}p_{n}$:
<cmath> p_{n}=\frac{n}{n+1} p_{n-1}+\frac{1}{n+1} p_{n-2} . </cmath>
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:$ (Error compiling LaTeX. Unknown error_msg)\frac{11}{15}, \frac{53}{72}, \frac{103}{140}\left.p_{3}-p_{2}\right)\frac{2}{24},-\frac{2}{120}, \frac{2}{720},-\frac{2}{5040}p_{n}=2 \sum_{i=0}^{n+1} \frac{(-1)^{i}}{i !}$, which indeed satisfies the given recurrence relation. Then
<cmath> \lim _{n \rightarrow \infty} p_{n}=2 \sum_{i=0}^{\infty} \frac{(-1)^{i}}{i !}=\frac{2}{e} . </cmath>
But since the probability that the$ (Error compiling LaTeX. Unknown error_msg)nnnp=1-\frac{2}{e}\lfloor 180 p\rfloor180-\frac{360}{e}360 / e$, note that we can just truncate the infinite sum
<cmath> \frac{360}{e}=\sum_{n=0}^{\infty} \frac{360(-1)^{n}}{n !} </cmath>
as it converges rather quickly. The first several terms are$ (Error compiling LaTeX. Unknown error_msg)360-360+180-60+15-3+\frac{1}{2}132.5\lfloor 180-132.5\rfloor=47$.