HMMT 十一月 2023 · 冲刺赛 · 第 35 题
HMMT November 2023 — Guts Round — Problem 35
题目详情
- [20] Dorothea has a 3 × 4 grid of dots. She colors each dot red, blue, or dark gray. Compute the number of ways Dorothea can color the grid such that there is no rectangle whose sides are parallel to the grid lines and whose vertices all have the same color. Submit a positive integer A. If the correct answer is C and your answer is A , you will receive j k 2 A C 20 min , points. C A √
解析
- [20] Dorothea has a 3 × 4 grid of dots. She colors each dot red, blue, or dark gray. Compute the number of ways Dorothea can color the grid such that there is no rectangle whose sides are parallel to the grid lines and whose vertices all have the same color. Submit a positive integer A. If the correct answer is C and your answer is A , you will receive j k 2 A C 20 min , points. C A Proposed by: Amy Feng, Isabella Quan, Pitchayut Saengrungkongka, Rishabh Das, Vidur Jasuja Answer: 284688 Solution: To find an appropriate estimate, we will lower bound the number of rectangles. Let P ( R ) be the probability a random 3 by 4 grid will have a rectangle with all the same color in the grid. Let P ( r ) be the probability that a specific rectangle in the grid will have the same color. Note 4 3 3 1 P ( r ) = = . Observe that there are = 18 rectangles in the grid. Hence, we know that 4 3 27 2 2 18 2 P ( R ) ≤ 18 · P ( r ) = = . Thus, 1 − P ( R ), the probability no such rectangle is in the grid, is at most 27 3 12 1 3 11 . This implies that our answer should be at least = 3 , which is enough for around half points. 3 3 Closer estimations can be obtained by using more values of Inclusion-Exclusion. n = 4 c n t = 0 f o r i i n range ( 3 ∗ ∗ ( 3 ∗ n ) ) : mask = i a = [ [ ] , [ ] , [ ] ] f o r x i n range ( 3 ) : f o r y i n range ( n ) : a [ x ] . append ( mask % 3 ) mask //= 3 p a i r s = [ s e t ( ) f o r i i n range ( 3 ) ] works = True f o r i i n range ( n ) : f o r j , k i n [ ( 0 , 1 ) , ( 0 , 2 ) , ( 1 , 2 ) ] : i f a [ j ] [ i ] == a [ k ] [ i ] : i f ( j , k ) i n p a i r s [ a [ j ] [ i ] ] : works = F a l s e e l s e : p a i r s [ a [ j ] [ i ] ] . add ( ( j , k ) ) i f works : c n t += 1 p r i n t ( c nt ) √