Difference between revisions of "User:Vqbc/Testing"
(24 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | + | 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 <math>1,2,3, \ldots, 25</math> 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 | |
− | |||
− | == | + | Answer: 169 |
− | \begin{align} | + | |
+ | 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 <math>1,3,5, \ldots, 25</math> all share the same color while the even numbers <math>2,4, \ldots, 24</math> 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 <math>1+3+5+\cdots+25=169</math> | ||
+ | |||
+ | 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 <math>\frac{a}{b}</math>, where <math>a</math> and <math>b</math> are relatively prime positive integers. Compute <math>100 a+b</math>. | ||
+ | |||
+ | Proposed by: Sheldon Kieren Tan | ||
+ | |||
+ | Answer: 116 | ||
+ | |||
+ | Solution: Each match eliminates exactly one player, so exactly <math>32-1=31</math> matches are played, each of which consists of a different pair of players. Among the <math>\left( | ||
+ | |||
+ | 3. Let <math>N</math> be a positive integer. Brothers Michael and Kylo each select a positive integer less than or equal to <math>N</math>, independently and uniformly at random. Let <math>p_{N}</math> denote the probability that the product of these two integers has a units digit of 0 . The maximum possible value of <math>p_{N}</math> over all possible choices of <math>N</math> can be written as <math>\frac{a}{b}</math>, where <math>a</math> and <math>b</math> are relatively prime positive integers. Compute <math>100 a+b .</math> | ||
+ | |||
+ | Proposed by: James Lin | ||
+ | |||
+ | Answer: 2800 | ||
+ | |||
+ | Solution: For <math>k \in\{2,5,10\}</math>, let <math>q_{k}=\frac{\lfloor N / k\rfloor}{N}</math> be the probability that an integer chosen uniformly at random from <math>[N]</math> is a multiple of <math>k</math>. Clearly, <math>q_{k} \leq \frac{1}{k}</math>, with equality iff <math>k</math> divides <math>N .</math> | ||
+ | |||
+ | The product of <math>p_{1}, p_{2} \in[N]</math> can be a multiple of 10 in two ways: | ||
+ | |||
+ | - one of them is a multiple of <math>10 ;</math> this happens with probability <math>q_{10}\left(2-q_{10}\right) ;</math> | ||
+ | |||
+ | - 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 <math>2\left(q_{2}-q_{10}\right)\left(q_{5}-q_{10}\right)</math>. This gives | ||
+ | |||
+ | |||
+ | <cmath>\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*}</cmath> | ||
+ | |||
+ | |||
+ | and equality holds iff <math>N</math> is a multiple of <math>10 .</math> | ||
+ | |||
+ | 4. Let <math>S=\{1,2, \ldots, 9\} .</math> Compute the number of functions <math>f: S \rightarrow S</math> such that, for all <math>s \in S, f(f(f(s)))=</math> <math>s</math> and <math>f(s)-s</math> is not divisible by <math>3 .</math> | ||
+ | |||
+ | Proposed by: James Lin | ||
+ | |||
+ | Answer: 288 | ||
+ | |||
+ | Solution: Since <math>f(f(f(s)))=s</math> for all <math>s \in S</math>, each cycle in the cycle decomposition of <math>f</math> must have length 1 or 3 . Also, since <math>f(s) \not \equiv s \bmod 3</math> for all <math>s \in S</math>, each cycle cannot contain two elements <math>a, b</math> such that <math>a=b</math> mod <math>3 .</math> Hence each cycle has exactly three elements, one from each of residue classes mod <math>3 .</math> | ||
+ | |||
+ | In particular, <math>1,4,7</math> belong to distinct cycles. There are <math>6 \cdot 3</math> ways to choose two other numbers in the cycle containing 1. Then, there are <math>4 \cdot 2</math> ways to choose two other numbers in the cycle containing 4 . Finally, there are <math>2 \cdot 1</math> ways to choose two other numbers in the cycle containing 7 . Hence the desired number of functions <math>f</math> is <math>6 \cdot 3 \cdot 4 \cdot 2 \cdot 2 \cdot 1=288</math>. | ||
+ | |||
+ | 5. Teresa the bunny has a fair 8-sided die. Seven of its sides have fixed labels <math>1,2, \ldots, 7</math>, and the label on the eighth side can be changed and begins as 1 . She rolls it several times, until each of <math>1,2, \ldots, 7</math> appears at least once. After each roll, if <math>k</math> is the smallest positive integer that she has not rolled so far, she relabels the eighth side with <math>k</math>. The probability that 7 is the last number she rolls is <math>\frac{a}{b}</math>, where <math>a</math> and <math>b</math> are relatively prime positive integers. Compute <math>100 a+b .</math> | ||
+ | |||
+ | Proposed by: Milan Haiman | ||
+ | |||
+ | Answer: 104 | ||
+ | |||
+ | Solution 1: Let <math>n=7</math> and <math>p=\frac{1}{4}</math>. | ||
+ | |||
+ | Let <math>q_{k}</math> be the probability that <math>n</math> is the last number rolled, if <math>k</math> numbers less than <math>n</math> have already been rolled. We want <math>q_{0}</math> and we know <math>q_{n-1}=1</math>. | ||
+ | |||
+ | We have the relation | ||
+ | |||
+ | <cmath> | ||
+ | q_{k}=(1-p) \frac{k}{n-1} q_{k}+\left[1-(1-p) \frac{k+1}{n-1}\right] q_{k+1} | ||
+ | </cmath> | ||
+ | |||
+ | This rearranges to | ||
+ | |||
+ | <cmath> | ||
+ | \left[1-(1-p) \frac{k}{n-1}\right] q_{k}=\left[1-(1-p) \frac{k+1}{n-1}\right] q_{k+1} | ||
+ | </cmath> | ||
+ | |||
+ | This means that the expression on the LHS does not depend on <math>k</math>, so | ||
+ | |||
+ | <cmath> | ||
+ | [1-0] \cdot q_{0}=[1-(1-p)] \cdot q_{n-1}=p | ||
+ | </cmath> | ||
+ | |||
+ | Solution 2: For a given sequence of Teresa's rolls, let <math>x_{i}</math> be the <math>i</math> th distinct number rolled. We want to compute the probability that <math>x_{7}=7</math>. | ||
+ | |||
+ | For a given index <math>i</math>, we say that <math>x_{i}</math> is correct if <math>x_{i}</math> is the least positive integer not in <math>\left\{x_{1}, \ldots, x_{i-1}\right\} .</math> Note that the probability of a given sequence <math>x_{1}, \ldots, x_{7}</math> depends only on the number of correct <math>x_{i}</math>, since the probability of rolling the correct number on a given roll is higher by a factor of <math>2 .</math> | ||
+ | |||
+ | Now, suppose <math>x_{7}=7</math>. Consider <math>x_{i}^{\prime}=x_{i-1}+1</math> for <math>1<i \leq 7</math>, and <math>x_{1}^{\prime}=1</math>. Note that this operation on sequences <math>x_{1}, \ldots, x_{7}</math> pairs sequences ending in 7 with sequences starting with 1 . Additionally, we have that <math>x_{7}</math> and <math>x_{1}^{\prime}</math> are both correct, and that <math>x_{i}^{\prime}</math> is correct if and only if <math>x_{i-1}</math> is correct. Thus <math>x_{1}, \ldots, x_{7}</math> and <math>x_{1}^{\prime}, \ldots, x_{7}^{\prime}</math> have the same probability. | ||
+ | |||
+ | So, we conclude that the probability of <math>x_{7}=7</math> is the same as the probability of <math>x_{1}=1 .</math> But this is just <math>\frac{1}{4}</math>. | ||
+ | |||
+ | 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 <math>n</math> 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 <math>n</math>. | ||
+ | |||
+ | Proposed by: Krit Boonsiriseth | ||
+ | |||
+ | Answer: 129 | ||
+ | |||
+ | Solution: The main claim is that if the light pulse reflects vertically (on the left/right edges) <math>a</math> times and horizontally <math>b</math> times, then gcd <math>(a+1, b+1)=1</math>, and the number of regions is <math>\frac{(a+2)(b+2)}{2} .</math> This claim can be conjectured by looking at small values of <math>a</math> and <math>b</math>; we give a full proof at the end. | ||
+ | |||
+ | Assuming the claim, we are trying to find the least possible value of <math>a+b</math> when <math>(a+2)(b+2)=2 \cdot 2021=</math> <math>2 \cdot 43 \cdot 47 .</math> This happens when <math>(a+2, b+2)=(47,86)</math>, which also satisfies ged <math>(a+1, b+1)=1</math>, and gives <math>a+b=47+86-4=129</math>. | ||
+ | |||
+ | We now prove the claim. Imagine that at each reflection, it is the square that gets reflected instead. Then the path <math>p</math> of the light pulse becomes a straight segment <math>s</math> from <math>(0,0)</math> to <math>(a+1, b+1)</math> of slope <math>+m=\frac{a+1}{b+1}</math>. | ||
+ | |||
+ | - 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 <math>s</math> with a line <math>x=n</math> or <math>y=n</math> for <math>x \in[a], y \in[b] .</math> There are <math>a+b</math> such intersections. | ||
+ | |||
+ | - Each self-intersection of <math>p</math> creates a region. An intersection on <math>p</math> corresponds to two on <math>s</math>, and each intersection of <math>s</math> happens with a line of slope <math>-m</math> passing through an even integral point, i.e. a line of the form <math>(b+1) x+(a+1) y=2 k</math>. The open segment <math>s</math> intersects these lines for <math>k \in[a b+a+b] .</math> However, the <math>a+b</math> intersections that happens on a gridline <math>x \in \mathbb{Z}</math> or <math>y \in \mathbb{Z}</math> do not count, so here we have an additional <math>a b / 2</math> regions. | ||
+ | |||
+ | Therefore, the total number of regions is | ||
+ | |||
+ | <cmath> | ||
+ | 2+a+b+\frac{a b}{2}=\frac{(a+2)(b+2)}{2} | ||
+ | </cmath> | ||
+ | |||
+ | 7. Let <math>S=\{1,2, \ldots, 2021\}</math>, and let <math>\mathcal{F}</math> denote the set of functions <math>f: S \rightarrow S .</math> For a function <math>f \in \mathcal{F}</math>, let | ||
+ | |||
+ | <cmath> | ||
+ | T_{f}=\left\{f^{2021}(s): s \in S\right\} | ||
+ | </cmath> | ||
+ | |||
+ | where <math>f^{2021}(s)</math> denotes <math>f(f(\cdots(f(s)) \cdots))</math> with 2021 copies of <math>f .</math> Compute the remainder when | ||
+ | |||
+ | <cmath> | ||
+ | \sum_{f \in \mathcal{F}}\left|T_{f}\right| | ||
+ | </cmath> | ||
+ | |||
+ | is divided by the prime 2017, where the sum is over all functions <math>f</math> in <math>\mathcal{F}</math>. | ||
+ | |||
+ | Proposed by: Milan Haiman | ||
+ | |||
+ | Answer: 255 | ||
+ | |||
+ | Solution: The key idea is that <math>t \in T_{f}</math> if and only if <math>f^{k}(t)=t</math> for some <math>k>0</math>. To see this, let <math>s \in S</math> and consider | ||
+ | |||
+ | <cmath> | ||
+ | s, f(s), f(f(s)), \ldots, f^{2021}(s) | ||
+ | </cmath> | ||
+ | |||
+ | This sequence has 2022 terms that are all in <math>S</math>, so we must have a repeat. Suppose <math>f^{m}(s)=f^{n}(s)</math> with <math>0 \leq n<m \leq 2021</math>. Then <math>f^{2021}(s)=f^{2021+m-n}(s) .</math> In particular, for <math>t=f^{2021}(s)</math>, we have <math>f^{k}(t)=t</math> with <math>k=m-n .</math> On the other hand, if <math>f^{k}(t)=t</math>, then letting <math>s=f^{2021 k-2021}(t)</math> gives <math>f^{2021}(s)=t .</math> | ||
+ | |||
+ | We will compute the number of <math>f</math> for which <math>f^{k}(1)=1</math> for some <math>k</math>, and then multiply by 2021 . We do this by casework on the minimum possible value of <math>k</math>. | ||
+ | |||
+ | Given <math>k</math>, we just need to choose distinct values in <math>\{2, \ldots, 2021\}</math> for each of <math>f^{1}(1), f^{2}(1), \ldots, f^{k-1}(1)</math>. We have <math>\frac{2020 !}{(2021-k) !}</math> ways to do this. For each of the <math>2021-k</math> other values with <math>f</math> not yet determined, we can do anything we want, giving <math>2021^{2021-k}</math> choices. | ||
+ | |||
+ | SO, | ||
+ | |||
+ | <cmath> | ||
+ | \sum_{f \in \mathcal{F}}\left|T_{f}\right|=2021 \sum_{k=1}^{2021} \frac{2020 !}{(2021-k) !} \cdot 2021^{2021-k} | ||
+ | </cmath> | ||
+ | |||
+ | Taking this mod 2017, all terms with <math>k>4</math> reduce to 0, and <math>2021^{2021-k}</math> reduces to <math>4^{5-k}</math> for <math>k \leq 4 .</math> We are thus left with | ||
+ | |||
+ | <cmath> | ||
+ | \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) | ||
+ | </cmath> | ||
+ | |||
+ | 8. Compute the number of ways to fill each cell in a <math>8 \times 8</math> square grid with one of the letters <math>H, M</math>, or <math>T</math> such that every <math>2 \times 2</math> square in the grid contains the letters <math>H, M, M, T</math> in some order. | ||
+ | |||
+ | Proposed by: Sheldon Kieren Tan | ||
+ | |||
+ | Answer: 1076 | ||
+ | |||
+ | Solution: We solve the problem for general <math>n \times n</math> boards where <math>n</math> even. Let the cell in the <math>i</math>-th row and <math>j</math>-th column be <math>a_{i, j}</math>. | ||
+ | |||
+ | Claim: In any valid configuration, either the rows (or columns) alternate between <math>(\cdots, H, M, H, M, \cdots)</math> and <math>(\cdots, T, M, T, M, \cdots)</math> or <math>(\cdots, M, M, M, M, \cdots)</math> and <math>(\cdots, H, T, H, T, \cdots)</math>. | ||
+ | |||
+ | 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: | ||
+ | |||
+ | <cmath>\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 | \hline | ||
− | \end{ | + | \end{array}</cmath> |
+ | |||
+ | 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 <math>(M, M, \cdots)</math> ). 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 <math>(\cdots, H, M, H, M, \cdots)</math> and <math>(\cdots, T, M, T, M, \cdots)</math>, there are 2 ways to choose which one occupies the odd-numbered rows, and <math>2^{n}</math> ways to alternate between the 2 letters in each row. When the rows alternate between <math>(\cdots, H, T, H, T, \cdots)</math> and <math>(\cdots, M, M, M, M, \cdots)</math>, there are 2 ways to choose which occupies the oddnumbered rows, and <math>2^{\frac{n}{2}}</math> 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 <math>2 \times 2^{2}=8</math> ways to do this if the rows are <math>(\cdots, H, M, H, M, \cdots)</math> and <math>(\cdots, T, M, T, M, \cdots)</math>, and <math>2 \times 2=4</math> ways to do this if the rows are <math>(\cdots, M, M, M, M, \cdots)</math> and <math>(\cdots, H, T, H, T, \cdots)</math>. | ||
+ | |||
+ | Hence the total number of configurations is <math>2\left(2^{n+1}+2^{\frac{n}{2}+1}\right)-12=2^{n+2}+2^{\frac{n}{2}+2}-12</math>. | ||
+ | |||
+ | 9. An up-right path between two lattice points <math>P</math> and <math>Q</math> is a path from <math>P</math> to <math>Q</math> that takes steps of length 1 unit either up or to the right. | ||
+ | |||
+ | How many up-right paths from <math>(0,0)</math> to <math>(7,7)</math>, when drawn in the plane with the line <math>y=x-2.021</math>, enclose exactly one bounded region below that line? | ||
+ | |||
+ | Proposed by: Anders Olsen | ||
+ | |||
+ | 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 <math>x-2.021</math>, any path which traverses below this line (and hence includes a point on the line <math>y=x-3)</math> 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 <math>y=x-3</math> over that line to get a path from <math>(0,0)</math> to <math>(10,4)</math>. This process is reversible for any path to <math>(10,4)</math>, so the number of paths enclosing at least one region is <math>\left( | ||
+ | |||
+ | 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 <math>y=x-3 .</math> Since at least two regions are enclosed, there must be some point on the intermediate portion of the path on the line <math>y=x-2</math>. Then we can reflect only this portion of the path over the line <math>y=x-3</math> to get a new path containing a point on the line <math>y=x-4</math>. We can then do a similar reflection starting from the first such point to get a path from <math>(0,0)</math> to <math>(11,3)</math>. This process is reversible, so the number of paths which enclose at least two regions is <math>\left( | ||
+ | |||
+ | 10. Jude repeatedly flips a coin. If he has already flipped <math>n</math> heads, the coin lands heads with probability <math>\frac{1}{n+2}</math> and tails with probability <math>\frac{n+1}{n+2}</math>. If Jude continues flipping forever, let <math>p</math> be the probability that he flips 3 heads in a row at some point. Compute <math>\lfloor 180 p\rfloor</math>. | ||
+ | |||
+ | Proposed by: Anders Olsen | ||
+ | |||
+ | Answer: 47 | ||
+ | |||
+ | Solution: Let <math>p_{n}</math> be the probability that the <math>n</math>th head is flipped after a tail and Jude has yet to flip 3 heads consecutively to this point. For example, <math>p_{2}=\frac{2}{3}</math>, 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 <math>\frac{2}{3}</math>. Similarly, <math>p_{3}=\frac{3}{4}</math>. We now establish a recursion between values of <math>p_{n}</math> : | ||
+ | |||
+ | <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: <math>\frac{11}{15}, \frac{53}{72}, \frac{103}{140}</math>, and so on. Notably, the differences between consecutive terms (starting from <math>\left.p_{3}-p_{2}\right)</math> are <math>\frac{2}{24},-\frac{2}{120}, \frac{2}{720},-\frac{2}{5040}</math>, and so on. This leads us to guess that <math>p_{n}=2 \sum_{i=0}^{n+1} \frac{(-1)^{i}}{i !}</math>, 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 <math>n</math>th head comes after a tail approaches 1 as <math>n</math> increases, this limit is the same as the limit of the probability that the first <math>n</math> 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 <math>p=1-\frac{2}{e}</math>. We are asked to compute <math>\lfloor 180 p\rfloor</math>. This is the floor of <math>180-\frac{360}{e}</math>. To compute <math>360 / e</math>, 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 <math>360-360+180-60+15-3+\frac{1}{2}</math>, and the rest are insignificant. This sums to about <math>132.5</math>, giving an answer of <math>\lfloor 180-132.5\rfloor=47</math>. |
Latest revision as of 22:42, 4 January 2022
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
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
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
Proposed by: James Lin
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
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:
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 ). 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 and
, there are 2 ways to choose which one occupies the odd-numbered rows, and
ways to alternate between the 2 letters in each row. When the rows alternate between
and
, there are 2 ways to choose which occupies the oddnumbered rows, and
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 ways to do this if the rows are
and
, and
ways to do this if the rows are
and
.
Hence the total number of configurations is .
9. An up-right path between two lattice points and
is a path from
to
that takes steps of length 1 unit either up or to the right.
How many up-right paths from to
, when drawn in the plane with the line
, enclose exactly one bounded region below that line?
Proposed by: Anders Olsen
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 , any path which traverses below this line (and hence includes a point on the line
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
over that line to get a path from
to
. This process is reversible for any path to
, so the number of paths enclosing at least one region is
.
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 Since at least two regions are enclosed, there must be some point on the intermediate portion of the path on the line
. Then we can reflect only this portion of the path over the line
to get a new path containing a point on the line
. We can then do a similar reflection starting from the first such point to get a path from
to
. This process is reversible, so the number of paths which enclose at least two regions is
. Then the desired answer is just
.
10. Jude repeatedly flips a coin. If he has already flipped heads, the coin lands heads with probability
and tails with probability
. If Jude continues flipping forever, let
be the probability that he flips 3 heads in a row at some point. Compute
.
Proposed by: Anders Olsen
Answer: 47
Solution: Let be the probability that the
th head is flipped after a tail and Jude has yet to flip 3 heads consecutively to this point. For example,
, 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 . Similarly,
. We now establish a recursion between values of
:
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: , and so on. Notably, the differences between consecutive terms (starting from
are
, and so on. This leads us to guess that
, which indeed satisfies the given recurrence relation. Then
But since the probability that the th head comes after a tail approaches 1 as
increases, this limit is the same as the limit of the probability that the first
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
. We are asked to compute
. This is the floor of
. To compute
, note that we can just truncate the infinite sum
as it converges rather quickly. The first several terms are , and the rest are insignificant. This sums to about
, giving an answer of
.