HMMT 二月 2011 · ALGCOMB 赛 · 第 20 题
HMMT February 2011 — ALGCOMB Round — Problem 20
题目详情
- Alice and Bob play a game in which two thousand and eleven 2011 × 2011 grids are distributed between the two of them, 1 to Bob, and the other 2010 to Alice. They go behind closed doors and fill their 2 grid(s) with the numbers 1 , 2 , . . . , 2011 so that the numbers across rows (left-to-right) and down columns (top-to-bottom) are strictly increasing. No two of Alice’s grids may be filled identically. After the grids are filled, Bob is allowed to look at Alice’s grids and then swap numbers on his own grid, two at a time, as long as the numbering remains legal (i.e. increasing across rows and down columns) after each swap. When he is done swapping, a grid of Alice’s is selected at random. If there exist two integers in the same column of this grid that occur in the same row of Bob’s grid, Bob wins. Otherwise, Alice wins. If Bob selects his initial grid optimally, what is the maximum number of swaps that Bob may need in order to guarantee victory?
解析
- Alice and Bob play a game in which two thousand and eleven 2011 × 2011 grids are distributed between the two of them, 1 to Bob, and the other 2010 to Alice. They go behind closed doors and fill their 2 grid(s) with the numbers 1 , 2 , . . . , 2011 so that the numbers across rows (left-to-right) and down columns (top-to-bottom) are strictly increasing. No two of Alice’s grids may be filled identically. After the grids are filled, Bob is allowed to look at Alice’s grids and then swap numbers on his own grid, two at a time, as long as the numbering remains legal (i.e. increasing across rows and down columns) after each swap. When he is done swapping, a grid of Alice’s is selected at random. If there exist two integers in the same column of this grid that occur in the same row of Bob’s grid, Bob wins. Otherwise, Alice wins. If Bob selects his initial grid optimally, what is the maximum number of swaps that Bob may need in order to guarantee victory? Answer: 1 Consider the grid whose entries in the j th row are, in order, 2011 j − 2010 , 2011 j − 2009 , . . . , 2011 j . Call this grid A . For k = 1 , 2 . . . , 2010, let grid A be the grid obtained from A by swapping the rightmost 0 k 0 entry of the k th row with the leftmost entry of the k +1st row. We claim that if A ∈ { A , A , . . . , A } , 0 1 2010 then given any legally numbered grid B such that A and B differ in at least one entry, there exist two integers in the same column of B that occur in the same row of A . We first consider A . Assume for the sake of contradiction B is a legally numbered grid distinct from 0 A , such that there do not exist two integers in the same column of B that occur in the same row 0 of A . Since the numbers 1 , 2 , . . . , 2011 occur in the same row of A , they must all occur in different 0 0 columns of B . Clearly 1 is the leftmost entry in B ’s first row. Let m be the smallest number that does not occur in the first row of B . Since each row is in order, m must be the first entry in its row. But then 1 and m are in the same column of B , a contradiction. It follows that the numbers 1 , 2 , . . . , 2011 all occur in the first row of B . Proceeding by induction, 2011 j − 2010 , 2011 j − 2009 , . . . , 2011 j must all occur in the j th row of B for all 1 ≤ j ≤ 2011. Since A is the only legally numbered grid satsifying 0 this condition, we have reached the desired contradiction. Now note that if A ∈ { A , . . . , A } , there exist two integers in the same column of A that occur in 1 2010 0 the same row of A . In particular, if A = A and 1 ≤ k ≤ 2010, then the integers 2011 k − 2010 and k 2011 k + 1 occur in the same column of A and in the same row of A . Therefore, it suffices to show 0 k that for all 1 ≤ k ≤ 2010, there is no legally numbered grid B distinct from A and A such that there k 0 do not exist two integers in the same column of B that occur in the same row of A . Assume for the 0 sake of contradiction that there does exist such a grid B . By the same logic as above, applied to the first k − 1 rows and applied backwards to the last 2010 − k − 1 rows, we see that B may only differ from A in the k th and k + 1st rows. However, there are only two legally numbered grids that are identical k to A outside of rows k and k + 1, namely A and A . This proves the claim. k 0 k It remains only to note that, by the pigeonhole principle, if one of Alice’s grids is A , then there exists 0 a positive integer k , 1 ≤ k ≤ 2010, such that A is not one of the Alice’s grids. Therefore, if Bob sets k his initial grid to be A , he will require only one swap to switch his grid to A after examining Alice’s 0 k grids. If A is not among Alice’s grids, then if Bob sets his initial grid to be A , he will not in fact 0 0 require any swaps at all. Algebra & Combinatorics Individual Test