HMMT 二月 2011 · 冲刺赛 · 第 19 题
HMMT February 2011 — Guts Round — Problem 19
题目详情
- [ 12 ] Find the least positive integer N with the following property: If all lattice points in [1 , 3] × [1 , 7] × [1 , N ] are colored either black or white, then there exists a rectangular prism, whose faces are parallel to the xy , xz , and yz planes, and whose eight vertices are all colored in the same color.
解析
- [ 12 ] Find the least positive integer N with the following property: If all lattice points in [1 , 3] × [1 , 7] × [1 , N ] are colored either black or white, then there exists a rectangular prism, whose faces are parallel to the xy , xz , and yz planes, and whose eight vertices are all colored in the same color. Answer: 127 Guts Round First we claim that if the lattice points in [1 , 3] × [1 , 7] are colored either black or white, then there exists a rectangle whose faces are parallel to the x and y axes, whose vertices are all the same color (a.k.a. monochromatic). Indeed, in every row y = i , 1 ≤ i ≤ 7, there are two lattice points with the same color. Note there are 3 combinations of 2 columns to choose from (for the two similarly-colored lattice points to be in), and 2 colors to choose from. By the Pigeonhole Principle, in the 2 · 3 + 1 = 7 rows two rows must have a pair of similarly-colored lattice points in the same columns, i.e. there is a monochromatic rectangle. This shows that in each cross section z = i , 1 ≤ i ≤ N there is a monochromatic rectangle. Next, ( )( ) ( ) ( ) 3 7 3 7 note there are possibilities for this rectangle ( ways to choose the 2 x -coordinates and 2 2 2 2 ( )( ) 3 7 ways to choose the 2 y -coordinates), and 2 possible colors. Thus if N = 2 + 1 = 127, then by 2 2 the Pigeonhole Principle there are two values of i such that the same-colored rectangle has the same x and y coordinates in the plane z = i , i.e. there is a monochromatic rectangular prism. For N = 126 the assertion is not true. In each cross section z = i , we can color so that there is exactly 1 monochromatic rectangle, and in the 126 cross sections, have all 126 possible monochromatic rectangles represented. To do this, in each cross section we color so that each row has exactly 2 lattice points of the same color, and such that 6 of the rows give all possible combinations of 2 points having the same color. This way, there will be exactly 1 monochromatic rectangle in each cross section; we can obviously vary it for the different cross sections.