HMMT 二月 2011 · 冲刺赛 · 第 19 题

英文解析

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 parallelto 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 thereexists 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-coloredlattice 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 amonochromatic 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 xand 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 isexactly 1 monochromatic rectangle, and in the 126 cross sections, have all 126 possible monochromaticrectangles represented. To do this, in each cross section we color so that each row has exactly 2 latticepoints of the same color, and such that 6 of the rows give all possible combinations of 2 points havingthe same color. This way, there will be exactly 1 monochromatic rectangle in each cross section; wecan obviously vary it for the different cross sections.