HMMT 二月 2012 · 冲刺赛 · 第 20 题

英文解析

20. [ 11 ] Let n be the maximum number of bishops that can be placed on the squares of a 6 × 6 chessboardsuch that no two bishops are attacking each other. Let k be the number of ways to put n bishops onan 6 × 6 chessboard such that no two bishops are attacking each other. Find n + k . (Two bishops areconsidered to be attacking each other if they lie on the same diagonal. Equivalently, if we label the squares with coordinates ( x, y ), with 1 ≤ x, y ≤ 6, then the bishops on ( a, b ) and ( c, d ) are attackingeach other if and only if | a − c | = | b − d | .)
    Answer: 74 Color the square with coordinates ( i, j ) black if i + j is odd and white otherwise,
    for all 1 ≤ i, j ≤ 6. Looking at the black squares only, we note that there are six distinct diagonalswhich run upward and to the right, but that two of them consist only of a corner square; we cannotsimultaneously place bishops on both of these corner squares. Consequently, we can place at most fivebishops on black squares. (This can be achieved by placing bishops on (1 , 2) , (1 , 4) , (6 , 1) , (6 , 3) , (6 , 5).)
    If there are five bishops on black squares, there must be exactly one bishop on one of the two blackcorner squares, (6 , 1) and (1 , 6): suppose without loss of generality that we place a bishop on (1 , 6).
    Then, exactly one of (3 , 6) and (1 , 4) must also contain a bishop, and there are 2 ways to place twobishops on the four remaining black squares that are not yet under attack. Thus, we have a total of
    2 · 2 · 2 possible placements on black squares.
    Similarly, there are at most 5 bishops which can be placed on white squares and 2 ways to place them,3
    6 6
    so that n = 10 and k = 2 . Finally, n + k = 10 + 2 = 74.