HMMT 二月 2012 · 冲刺赛 · 第 20 题
HMMT February 2012 — Guts Round — Problem 20
题目详情
- [ 11 ] Let n be the maximum number of bishops that can be placed on the squares of a 6 × 6 chessboard such that no two bishops are attacking each other. Let k be the number of ways to put n bishops on an 6 × 6 chessboard such that no two bishops are attacking each other. Find n + k . (Two bishops are considered 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 attacking each other if and only if | a − c | = | b − d | .) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TH 15 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 11 FEBRUARY 2012 — GUTS ROUND
解析
- [ 11 ] Let n be the maximum number of bishops that can be placed on the squares of a 6 × 6 chessboard such that no two bishops are attacking each other. Let k be the number of ways to put n bishops on an 6 × 6 chessboard such that no two bishops are attacking each other. Find n + k . (Two bishops are considered 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 attacking each 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 diagonals which run upward and to the right, but that two of them consist only of a corner square; we cannot simultaneously place bishops on both of these corner squares. Consequently, we can place at most five bishops 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 black corner 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 two bishops 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. 3 Similarly, there are at most 5 bishops which can be placed on white squares and 2 ways to place them, 6 6 so that n = 10 and k = 2 . Finally, n + k = 10 + 2 = 74.