HMMT 二月 2013 · 团队赛 · 第 2 题
HMMT February 2013 — Team Round — Problem 2
题目详情
- [ 15 ] A cafe has 3 tables and 5 individual counter seats. People enter in groups of size betw een 1 and
4, inclusive, and groups never share a table. A group of more than 1 will always t ry to sit at a table,
but will sit in counter seats if no tables are available. Conversely, a group o f 1 will always try to sit at the counter first. One morning, M groups consisting of a total of N people enter and sit down. Then,
a single person walks in, and realizes that all the tables and counter seats are o ccupied by some personor group. What is the minimum possible value of M + N ?
英文原题
Chooses a column, and add 1 to each entry.
He would like to get an array where all integers are divisible by 2013. On how many arrays is this
possible?
解析
英文解析
- Chooses a column, and add 1 to each entry.
He would like to get an array where all integers are divisible by 2013. On how many arrays is thispossible?
4025
Answer: 2013 We claim that the set of grids on which it is possible to obtain an array of allzeroes (mod 2013) is indexed by ordered 4025-tuples of residues (mod 2013), corresponding to the
4025
starting entries in the first row and first column of the grid, giving the answer of 2013 . To do this,
we show that given after fixing all of the entries in the first row and column, there is a unique startinggrid which can become an array of all zeroes after applying the appropriate operations.
Let a be the entry in the i -th row and the j -th column. Suppose there is a sequence of operationsi,jgiving all zeroes in the array; let r be the number of times we operate on row i , and let c be thei jnumber of times we operate on column j . It is enough to take all of these values to be residues modulo - Clearly, a + r + c ≡ 0 (mod 2013) for each i, j . In particular, r + c ≡ a . Now, for eachi,j i j 1 1 1 , 1
i, j , we have a ≡ − r − ci,j i j
≡ ( a + c ) + ( a + r )
i, 1 1 1 ,j 1
≡ a + a − a ,
i, 1 1 ,j 1 , 1
which is fixed. Thus, there rest of the entries in the grid are forced.
Conversely, if we set a to be the appropriate representative of the residue class of a + a − ai,j i, 1 1 ,j 1 , 1
modulo 2013, we may take r ≡ − a (mod 2013), and c ≡ a − a (mod 2013) for each i, j . It isi i, 1 j 1 , 1 1 ,jclear that a + r + c ≡ 0 (mod 2013) for each i, j , so we’re done.
i,j i j