HMMT 二月 2010 · COMB 赛 · 第 10 题

英文解析

10. [ 8 ] In a 16 × 16 table of integers, each row and column contains at most 4 distinct integers. What isthe maximum number of distinct integers that there can be in the whole table?
    Answer: 49 First, we show that 50 is too big. Assume for sake of contradiction that a labelingwith at least 50 distinct integers exists. By the Pigeonhole Principle, there must be at least one row,
    say the first row, with at least 4 distinct integers in it; in this case, that is exactly 4, since that is the maximum number of distinct integers in one row. Then, in the remaining 15 rows there must be atleast 46 distinct integers (these 46 will also be distinct from the 4 in the first row). Using Pigeonholeagain, there will be another row, say the second row, with 4 distinct integers in it. Call the set ofintegers in the first and second rows S . Because the 4 distinct integers in the second row are distinctfrom the 4 in the first row, there are 8 distinct values in the first two rows, so | S | = 8. Now considerthe subcolumns containing the cells in rows 3 to 16. In each subcolumn, there are at most 2 values notin S , because there are already two distinct values in that column from the cells in the first two rows.
    So, the maximum number of distinct values in the table is 16 · 2 + 8 = 40, a contradiction. So a validlabeling must have fewer than 50 distinct integers. Below, we show by example that 49 is attainable.
    Combinatorics Subject Test
    1 17 33 - - - - - - - - - - - - -

• 2 18 34 - - - - - - - - - - - -
• • 3 19 35 - - - - - - - - - - -
• • • 4 20 36 - - - - - - - - - -
• • • • 5 21 37 - - - - - - - - -
• • • • • 6 22 38 - - - - - - - -
• • • • • • 7 23 39 - - - - - - -
• • • • • • • 8 24 40 - - - - - -
• • • • • • • • 9 25 41 - - - - -
• • • • • • • • • 10 26 42 - - - -
• • • • • • • • • • 11 27 43 - - -
• • • • • • • • • • • 12 28 44 - -
• • • • • • • • • • • • 13 29 45 -
• • • • • • • • • • • • • 14 30 46
                          47 - - - - - - - - - - - - - 15 31
                          32 48 - - - - - - - - - - - - - 16
                          Cells that do not contain a number are colored with color 49.
                          Combinatorics Subject Test