combinatorics - power of 2 involving floor function divides cyclic product

if $S_n={a_1,a_2,a_3,...,a_{2n}}$} where $a_1,a_2,a_3,...,a_{2n}$ are all distinct integers.Denote by $T$ the product
$$T=\prod_{i,j\epsilon S_n,i Prove that $2^{(n^2-n+2[\frac{n}{3}])}\times \text{lcm}(1,3,5,...,(2n-1))$ divides $T$.(where [] is the floor function)

I have tried many approaches.I tried using the fact that either number of odd or even integers$\ge(n+1)$ and since in $T$ every integer is paired with every other integer only once.Since even-even and odd-odd both give even numbers:$2^{\frac{n(n+1)}{2}}$ divides $T$.As for the $lcm(1,,3,5,....(2n-1))$ I have no Idea what to do.Please help.I am quite new to NT.Thank you.

Answer

HINT:

You're not quite correct for the powers of $2$. There are $2n$ numbers total, so there can in fact be exactly $n$ odds and $n$ evens (i.e. neither has to be $\ge n+1$.)

Instead: Let there be $k$ odds, and $2n-k$ evens. This gives you ${k \choose 2}$ factors of $2$ from the (odd - odd) terms and ${2n-k \choose 2}$ factors of $2$ from the (even - even) terms.

• First you can show that their sum is minimized at $k=n$ and that sum is $n(n-1) = n^2 - n$.




• So now you're need another $2[{n \over 3}]$ more factors of $2$. These come from splitting evens further into $4k$ vs $4k+2$, and the odds into $4k+1$ vs $4k+3$, because some of the differences will provide a factor of $4$, i.e. an additional factor of $2$ in addition to the factor of $2$ you already counted.

  
  
  
  
  
  
  • Proof sketch: e.g. suppose there are $n$ evens, and for simplicity of example lets say $n$ is itself even. In the worst split exactly $n/2$ will be multiples of $4$, which gives another $\frac12 {\frac n 2}({\frac n 2}-1)$ factors of $2$ from these numbers of form $4k$, and a similar thing happens with the $4k+1$'s, the $4k+2$'s, and the $4k+3$'s. This funny thing is that if you add up everything, $n({\frac n 2}-1) \ge 2[{\frac n 3}]$ (you can try it, and you will need to prove it). In other words $2[{\frac n 3}]$ is not a tight bound at all, but rather a short-hand that whoever wrote the question settled on just to make you think about the splits into $4k + j$. In fact a really tight bound would involve thinking about splits into $8k+j, 16k+j$ etc.
  
  



• As for $lcm(1, 3, 5, \dots, 2n-1)$, first note that $lcm$ divides $T$ just means each of the odd numbers divide $T$. You can prove this by the pigeonhole principle.

  
  
  
  
  
  • Further explanation: E.g. consider $lcm(3, 9) = 9$, so this lcm divides $T$ if both odd numbers divide $T$. In general, the lcm can be factorized into $3^{n_3} 5^{n_5} 7^{n_7} 11^{n_{11}} \dots$ and it divides $T$ if every term $p^{n_p}$ divides $T$. but in your case $p^{n_p}$ itself must be one of the numbers in the list $(1, 3, 5, \dots, 2n-1)$ or else the lcm wouldn't contain that many factors of $p$.
  
  

Can you finish from here?