HMMT 二月 2010 · GEN2 赛 · 第 10 题

HMMT February 2010 — GEN2 Round — Problem 10

[ 8 ] In a 16 × 16 table of integers, each row and column contains at most 4 distinct integers. What is the maximum number of distinct integers that there can be in the whole table?

解析

[ 8 ] In a 16 × 16 table of integers, each row and column contains at most 4 distinct integers. What is the 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 labeling with 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 at General Test, Part 2 least 46 distinct integers (these 46 will also be distinct from the 4 in the first row). Using Pigeonhole again, there will be another row, say the second row, with 4 distinct integers in it. Call the set of integers in the first and second rows S . Because the 4 distinct integers in the second row are distinct from the 4 in the first row, there are 8 distinct values in the first two rows, so | S | = 8. Now consider the subcolumns containing the cells in rows 3 to 16. In each subcolumn, there are at most 2 values not in 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 valid labeling must have fewer than 50 distinct integers. Below, we show by example that 49 is attainable. 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. General Test, Part 2