Prove that $S_{2n} \geq n$ for all $n$

For every positive integer $n$, define $S_n$ as the number of permutations $(a_1,a_2,\ldots,a_n)$ of $(1,2,\ldots,n)$ such that $$\dfrac{a_1}{1}+\dfrac{a_2}{2}+\dfrac{a_3}{3}+\cdots+\dfrac{a_n}{n}$$ is a positive integer. Prove that $S_{2n} \geq n$ for all $n$.

If $n = 1$, then $\dfrac{a_1}{1}+\dfrac{a_2}{2}$ needs to be an integer and there is only one possibility: $(a_1,a_2) = (1,2)$.

If $n = 2$, then $\dfrac{a_1}{1}+\dfrac{a_2}{2}+\dfrac{a_3}{3}+\dfrac{a_4}{4}$ needs to be an integer. The $4$-tuples $(a_1,a_2,a_3,a_4) = (1,2,3,4),(4,1,3,2)$ work.

How can we generalize this for any $n$?

• Wouldn't induction work here?
– RGS
Oct 25 '17 at 21:33
• How come does $(1,4,3,2)$ work? Doesn't that give $1/1 + 4/2 + 3/3 + 2/4 = 6.5$?
– RGS
Oct 25 '17 at 21:39
• Hint: Clearly $S_{2n}\geq S_{2n-2}$ because for every "good" permutation of $(1, \ldots, 2n-2)$ there's one of $(1, \ldots, 2n)$ where we just set $a_{2n-1}=2n-1$, $a_{2n}=2n$. Can you find at least one "good" permutation of $(1, \ldots, 2n)$ where $a_{2n}=n$? Oct 25 '17 at 21:48

We will proceed by induction! You already proved the base case for $n = 1$, now we only need to show that if $C_{2k} \geq k, C_{2(k+1)} \geq k+1$.

In fact, for the tuples $(a_1, \cdots a_{2k}, a_{2k+1}, a_{2K+2})$ note that each solution for $2k$ works, appending $(2k+1, 2k+2)$ in the end:

For example, $(1, 2)$ works for $n=1$, thus $(1,2,3,4)$ works for $n=2$.

All we need now is another permutation that works for $2k+2$ that does not end with $(2k+1, 2k+2)$.

One can see that we can easily take

$$(2, 1, \cdots, k, 2k+2, k+2, \cdots, 2k, 2k+1, k)$$

So, for example, with $k = 3$ we would be defining

$$(2,1,6,4,5,3)$$

Now we have that $$C_{2(k+1)} \geq C_{2k} + 1 \geq k + 1$$

which was what we wanted to prove.

• Your $k=3$ example doesn't match your description for general $k$; As far as I can tell it should be a permutation of $(1\ldots 8)$. (And the solution for general $k$ can't be quite right, because the 'almost middle' term $a_k$ is $2k+2$, leading to a contribution to the sum of $\frac{2k+2}{k}=2+\frac2k$ with no compensating term.) Oct 25 '17 at 21:57
• I do not even get what the "$\ldots$" are supposed to stand for Oct 25 '17 at 22:01
• @HagenvonEitzen I presume they're just direct sequences of (increasing) numbers; thus $a_i=i$ for $3\leq i\leq k-1$ and $k+1\leq i\leq 2k$. Oct 25 '17 at 22:08
• @StevenStadnicki Ah! So we have the identity permutation, except that we swap $1\leftrightarrow2$ and $k+1\leftrightarrow 2(k+1)$; works for Oct 25 '17 at 22:11
• @HagenvonEitzen The problem is that as the answer is currently written it's swapping $k\leftrightarrow 2k+2$; I believe your version does the right thing. Oct 25 '17 at 22:13