Let $(p_1,p_2,..., p_n)$ be a random permutation of the set $\{1,2,...,n)$. If $n$ is odd, prove that the product $(p_1-1)\cdot (p_2-2)\cdot ...\cdot (p_n-n)$ is an even number. @below fixed.
Problem
Source: Kosovo MO 2010 Grade 12, Problem 4
Tags: number theory
07.06.2021 19:10
What is the pattern in the product? That is, what is the $i$-th factor? I guess it involves $p_i$ but what do you subtract? The sequence $(1,1,\dots,n)$ does not have an obvious continuation in my opinion...
07.06.2021 19:16
I interpret it as $\textstyle\prod_{1\le i\le n}(p_i-i)$. Suppose the product is odd, hence $p_i-i\equiv1\pmod{2}$ for $1\le i\le n$. Summing these up, we find that on the one hand, $\textstyle\sum_i (p_i-i)=0$, whereas on the other hand the sum is congruent to $n$, which is odd. A contradiction is reached.
07.06.2021 19:18
grupyorum wrote: I interpret it as $\textstyle\prod_{1\le i\le n}(p_i-i)$. But the second factor clearly is $p_2-1$ not $p_2-2$...
07.06.2021 21:05
There's k even numbers but k+1 odd numbers (since n=2k+1). By pairing them, pigeonhole principle implies that at least one odd number must be paired with another odd number, and hence one of the factors (p_i-i) must be even.