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$?

  • $\begingroup$ Wouldn't induction work here? $\endgroup$
    – RGS
    Oct 25 '17 at 21:33
  • $\begingroup$ How come does $(1,4,3,2)$ work? Doesn't that give $1/1 + 4/2 + 3/3 + 2/4 = 6.5$? $\endgroup$
    – RGS
    Oct 25 '17 at 21:39
  • $\begingroup$ 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$? $\endgroup$ 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


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

which was what we wanted to prove.

  • $\begingroup$ 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.) $\endgroup$ Oct 25 '17 at 21:57
  • $\begingroup$ I do not even get what the "$\ldots$" are supposed to stand for $\endgroup$ Oct 25 '17 at 22:01
  • 1
    $\begingroup$ @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$. $\endgroup$ Oct 25 '17 at 22:08
  • $\begingroup$ @StevenStadnicki Ah! So we have the identity permutation, except that we swap $1\leftrightarrow2$ and $k+1\leftrightarrow 2(k+1)$; works for $\endgroup$ Oct 25 '17 at 22:11
  • $\begingroup$ @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. $\endgroup$ Oct 25 '17 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.