返回题库

HMMT 二月 2019 · COMB 赛 · 第 9 题

HMMT February 2019 — COMB Round — Problem 9

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. How many ways can one fill a 3 × 3 square grid with nonnegative integers such that no nonzero integerappears more than once in the same row or column and the sum of the numbers in every row andcolumn equals 7?
解析

英文解析

  1. How many ways can one fill a 3 × 3 square grid with nonnegative integers such that no nonzero integerappears more than once in the same row or column and the sum of the numbers in every row andcolumn equals 7?
    Proposed by: Sam Korsky
    Answer: 216
    In what ways could we potentially fill a single row? The only possibilities are if it contains the numbers
    (0 , 0 , 7) or (0 , 1 , 6) or (0 , 2 , 5) or (0 , 3 , 4) or (1 , 2 , 4). Notice that if we write these numbers in binary,
    in any choices for how to fill the row, there will be exactly one number with a 1 in its rightmost digit,
    exactly one number with a 1 in the second digit from the right, and exactly exactly one number with a
    1 in the third digit from the right. Thus, consider the following operation: start with every unit squarefilled with the number 0. Add 1 to three unit squares, no two in the same row or column. Then add 2
    to three unit squares, no two in the same row or column. Finally, add 4 to three unit squares, no twoin the same row or column. There are clearly 6 = 216 ways to perform this operation and every such 3
    operation results in a unique, suitably filled-in 3 by 3 square. Hence the answer is 216.