HMMT 二月 2018 · COMB 赛 · 第 14 题

HMMT February 2018 February 10, 2018 Combinatorics

1. Consider a 2 × 3 grid where each entry is one of 0, 1, and 2. For how many such grids is the sum of the numbers in every row and in every column a multiple of 3? One valid grid is shown below. [ ] 1 2 0 2 1 0
2. Let a and b be five-digit palindromes (without leading zeroes) such that a < b and there are no other five-digit palindromes strictly between a and b . What are all possible values of b − a ? (A number is a palindrome if it reads the same forwards and backwards in base 10.)
3. A 4 × 4 window is made out of 16 square windowpanes. How many ways are there to stain each of the windowpanes, red, pink, or magenta, such that each windowpane is the same color as exactly two of its neighbors? Two different windowpanes are neighbors if they share a side.
4. How many ways are there for Nick to travel from (0 , 0) to (16 , 16) in the coordinate plane by moving one unit in the positive x or y direction at a time, such that Nick changes direction an odd number of times?
5. A bag contains nine blue marbles, ten ugly marbles, and one special marble. Ryan picks marbles randomly from this bag with replacement until he draws the special marble. He notices that none of the marbles he drew were ugly. Given this information, what is the expected value of the number of total marbles he drew?
6. Sarah stands at (0 , 0) and Rachel stands at (6 , 8) in the Euclidean plane. Sarah can only move 1 unit in the positive x or y direction, and Rachel can only move 1 unit in the negative x or y direction. Each second, Sarah and Rachel see each other, independently pick a direction to move at the same time, and move to their new position. Sarah catches Rachel if Sarah and Rachel are ever at the same point. Rachel wins if she is able to get to (0 , 0) without being caught; otherwise, Sarah wins. Given that both of them play optimally to maximize their probability of winning, what is the probability that Rachel wins?
7. A tourist is learning an incorrect way to sort a permutation ( p , . . . , p ) of the integers (1 , . . . , n ). We 1 n define a fix on two adjacent elements p and p , to be an operation which swaps the two elements i i +1 if p > p , and does nothing otherwise. The tourist performs n − 1 rounds of fixes, numbered i i +1 a = 1 , 2 , . . . , n − 1. In round a of fixes, the tourist fixes p and p , then p and p , and so on, a a +1 a +1 a +2 n ( n − 1) up to p and p . In this process, there are ( n − 1) + ( n − 2) + · · · + 1 = total fixes performed. n − 1 n 2 How many permutations of (1 , . . . , 2018) can the tourist start with to obtain (1 , . . . , 2018) after per- forming these steps?
8. A permutation of { 1 , 2 , . . . , 7 } is chosen uniformly at random. A partition of the permutation into contiguous blocks is correct if, when each block is sorted independently, the entire permutation becomes sorted. For example, the permutation (3 , 4 , 2 , 1 , 6 , 5 , 7) can be partitioned correctly into the blocks [3 , 4 , 2 , 1] and [6 , 5 , 7], since when these blocks are sorted, the permutation becomes (1 , 2 , 3 , 4 , 5 , 6 , 7). Find the expected value of the maximum number of blocks into which the permutation can be parti- tioned correctly.
9. How many ordered sequences of 36 digits have the property that summing the digits to get a number and taking the last digit of the sum results in a digit which is not in our original sequence? (Digits range from 0 to 9.)
10. Lily has a 300 × 300 grid of squares. She now removes 100 × 100 squares from each of the four corners and colors each of the remaining 50000 squares black and white. Given that no 2 × 2 square is colored in a checkerboard pattern, find the maximum possible number of (unordered) pairs of squares such that one is black, one is white and the squares share an edge.