Let $a_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, \ldots ,2007$. Define an operation to be 22 consecutive applications of the following steps on the sequence $S$: on $i$-th step, choose a number from the sequense $S$ at random, say $x$. If $1 \leq i \leq 11$, replace $x$ with $x+a_i$ ; if $12 \leq i \leq 22$, replace $x$ with $x-a_{i-11}$ . If the result of operation on the sequence $S$ is an odd permutation of $\{1, 2, \ldots , 2007\}$, it is an odd operation; if the result of operation on the sequence $S$ is an even permutation of $\{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 $\{x_1, x_2, \ldots , x_{2007}\}$ is an even permutation of $\{1, 2, \ldots ,2007\}$ if the product $\prod_{i > j} (x_i - x_j)$ is positive, and an odd one otherwise.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
10.11.2016 17:28
Is this translation logical? i can't' understand...
11.11.2016 13:54
Well yes it is right.But I cannot and moreover donot want to understand the answer given offically.
11.11.2016 13:57
well as i remember it is done by pairing the so called odd and even operations and calcuatong the rest
21.12.2018 21:18
Lei Lei wrote: Let $a_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, \ldots ,2007$. Define an operation to be 22 consecutive applications of the following steps on the sequence $S$: on $i$-th step, choose a number from the sequense $S$ at random, say $x$. If $1 \leq i \leq 11$, replace $x$ with $x+a_i$ ; if $12 \leq i \leq 22$, replace $x$ with $x-a_{i-11}$ . If the result of operation on the sequence $S$ is an odd permutation of $\{1, 2, \ldots , 2007\}$, it is an odd operation; if the result of operation on the sequence $S$ is an even permutation of $\{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 $\{x_1, x_2, \ldots , x_{2007}\}$ is an even permutation of $\{1, 2, \ldots ,2007\}$ if the product $\prod_{i > j} (x_i - x_j)$ is positive, and an odd one otherwise. To clarify, I think the following is a correct translation of the problem: Let $a_1,...,a_{11}$ be 11 pairwise distinct positive integers with $\sum_{i=1}^{11} a_i \le 2007$. On a blackboard the numbers $1,2,...,2007$ were written in ascending order in positions $1,2,...,2007$. Let $\mathbf{x} = (x_1,...,x_{22})$ be a sequence of 22 not necessarily distinct positions on the board. An operation associated with $\mathbf{x}$ is defined as the operation consisting of $22$ steps, where in step $i$ we increase the number written in position $x_i$ by $a_i$ if $i \le 11$, and decrease it by $a_{i-11}$ otherwise. We say that $\mathbf x$ is good (resp. bad) if the operation associated with $\mathbf x$, when applied to the board, results in a even (resp. odd) permutation of $\{1,2,...,2007\}$. Which is larger, the number of odd operation or the number of even permutation? And by how many? Even, odd permutations are defined as in post #1.
04.02.2022 21:54
Solved with oVlad, who may have a different, non-recursive solution (though I feel like his argument is a more convoluted version of mine, which uses recursion/induction to simplify). I hope solving this does not bring me bad luck at AIME, the way I got rekt by AMC geos after I solved TSTST 21/3. On the contrary, I think this is actually a good problem for preparing for computational contests because this relies mostly on ideas useful for computational problems and this is a computational problem itself. Although the methods are used are very elementary and simple, it is still a hard problem. The answer is $\prod\limits_{j=1}^{11} a_i$. In general, if $a_1< \cdots< a_k$ are positive integers such that $\sum\limits_{j=1}^k a_j < m$ and 2007 is replaced with $m$ the answer should be $\prod\limits_{j=1}^{k} a_i$. Let $s_1, \cdots, s_m$ be the permutation the operation acts on (initially $s_j=j$ for all $1\le j\le m$) Observation 1: Let $b_j=a_j$ if $1\le j\le k$ and $-a_{j-k}$ if $k+1\le j\le 2k$. If we perform the operations in a FIXED order and two elements are equal after adding $b_1, \cdots, b_l$ then the total contribution with $b_1, \cdots, b_l$ at these fixed spots is 0. Proof: Suppose after a while $s_i=s_j$. $\sum\limits_{t\in S} a_t$ is the material added to $s_i$ after $s_i=s_j$ has already happened and $\sum\limits_{t\in Y} a_t$ is the material added to $s_j$. If $S=Y$ then in the end $s_i$ will be equal to $s_j$ so $\{s_1, \cdots, s_m\}$ is not a permutation of $\{1,\cdots,m\}$. Therefore we can pair each operation with fixed $(S,Y)$ with $(Y,S)$. We use this observation in two ways. 1. If $a_i$ is added to $s_j$ and $a_i+s_j \le m$, then we WLOG the moves are ordered such that $a_i$ adding to $s_j$ is FIRST. This readily implies that $a_1$ cannot be added to $1, \cdots, m-a_1$, then $a_2$ cannot be added to $1, \cdots, m-a_2$, ..., in this order. This means that after a number gets added, it must get subtracted on because otherwise it is at least $m$. We now reorder the moves such that $a_1$ is first and the second move is subtracting the number that the number that $a_1$ gets added to. If the second move is minus $a_1$ then the two moves basically cancel out. If the second move is minus a bigger number, the new number is $x+a_1-a_2$. Since $x+a_1 > m$ it follows that it is positive. Furthermore, since $a_1<a_2$ this number is less than $x$ so two numbers are equal. Therefore the contribution is 0. There are $a_1$ places to do this operation, namely $m-a_1+1, \cdots, m$. So we can induct and this is the inductive step; since adding and subtracting $a_2, a_3, \cdots, a_k$ gives total contrib of $\prod\limits_{j=2}^k a_j$ ways, this gives $\prod\limits_{j=1}^k a_j$ ways. Since the base case can be easily verified, the conclusion follows.