MathDB

3

Part of 2007 China National Olympiad

Problems(2)

China Mathematics Olympiads (National Round) 2007 Problem 6

Source:

11/28/2010
Find a number n≥9n \geq 9 such that for any nn numbers, not necessarily distinct, a1,a2,…,ana_1,a_2, \ldots , a_n, there exists 9 numbers ai1,ai2,…,ai9,(1≤i1<i2<…<i9≤n)a_{i_1}, a_{i_2}, \ldots , a_{i_9}, (1 \leq i_1 < i_2 < \ldots < i_9 \leq n) and bi∈4,7,i=1,2,…,9b_i \in {4,7}, i =1, 2, \ldots , 9 such that b1ai1+b2ai2+…+b9ai9b_1a_{i_1} + b_2a_{i_2} + \ldots + b_9a_{i_9} is a multiple of 9.
pigeonhole principlenumber theory unsolvednumber theory
China Mathematics Olympiads (National Round) 2007 Problem 3

Source:

11/28/2010
Let a1,a2,…,a11a_1, a_2, \ldots , a_{11} be 11 pairwise distinct positive integer with sum less than 2007. Let S be the sequence of 1,2,…,20071,2, \ldots ,2007. Define an operation to be 22 consecutive applications of the following steps on the sequence SS: on ii-th step, choose a number from the sequense SS at random, say xx. If 1≤i≤111 \leq i \leq 11, replace xx with x+aix+a_i ; if 12≤i≤2212 \leq i \leq 22, replace xx with x−ai−11x-a_{i-11} . If the result of operation on the sequence SS is an odd permutation of {1,2,…,2007}\{1, 2, \ldots , 2007\}, it is an odd operation; if the result of operation on the sequence SS is an even permutation of {1,2,…,2007}\{1, 2, \ldots , 2007\}, it is an even operation. Which is larger, the number of odd operation or the number of even permutation? And by how many?
Here {x1,x2,…,x2007}\{x_1, x_2, \ldots , x_{2007}\} is an even permutation of {1,2,…,2007}\{1, 2, \ldots ,2007\} if the product ∏i>j(xi−xj)\prod_{i > j} (x_i - x_j) is positive, and an odd one otherwise.
combinatorics unsolvedcombinatorics