0
$\begingroup$

Let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$. Recall that a permutation $\sigma\in S_n$ is called a derangemnt if $\sigma(k)\not=k$ for all $k=1,\ldots,n$.

Motivated by the well-known result that $\sum_{k=m}^n\frac1k\not\in\mathbb Z$ whenever $n\ge m>1$ (Kurschak, 1918), here I ask the following question.

QUESTION: Is it true that whenever $n\ge m\ge1$ we have $$\sum_{k=m}^n\frac{\sigma(k)}k\not\in\mathbb Z$$ for all derangements $\sigma\in S_n$?

If $n$ is a prime number $p$ and $\sum_{k=m}^n\frac{\sigma(k)}k\in\mathbb Z$ with $\sigma\in S_n$, then $\sigma$ is not a derangement since $\sigma(p)=p$. Thus the question has a positive answer if $n$ is prime. I conjecture that the question always has a positive answer, and I have verified this for every $n=1,\ldots,11$. For $n=4$, note that $$\frac41+\frac12+\frac33+\frac24\in\mathbb Z$$ but the permutation $(4,1,3,2)$ of $\{1,2,3,4\}$ is not a derangement since it fixes the number $3$.

$\endgroup$
  • $\begingroup$ If $m$ is smaller than the last prime before $n$, then this prime appears in the denominator. $\endgroup$ – WhatsUp Nov 27 '18 at 13:09
  • $\begingroup$ I think that this approach based on Bertrand's postulate shows that your conjecture is true as long as the interval contains a prime (then $\sigma$ does not fix the largest prime $p$ in the interval so you can split the sum into one with $p$ in the denominator and one without). $\endgroup$ – Nathaniel Johnston Nov 27 '18 at 13:15
9
$\begingroup$

I extended the search to $n \leq 111111$ and find this: $$ \frac{10090}{110990} + \frac{36997}{110991} + \frac{15856}{110992} + \frac{6529}{110993} + \frac{8538}{110994} + \frac{22199}{110995} + \frac{55498}{110996} + \frac{36999}{110997} + \frac{55499}{110998} + \frac{95142}{110999} + \frac{55500}{111000} + \frac{100910}{111001} + \frac{55501}{111002} + \frac{74002}{111003} + \frac{27751}{111004} + \frac{88804}{111005} + \frac{55503}{111006} + \frac{102468}{111007} + \frac{27752}{111008} + \frac{74006}{111009} + \frac{104480}{111010} = 10. $$

In case you want to verify this more efficiently, here is the "code version":

10090/110990 + 36997/110991 + 15856/110992 + 6529/110993 + 8538/110994 + 22199/110995 + 55498/110996 + 36999/110997 + 55499/110998 + 95142/110999 + 55500/111000 + 100910/111001 + 55501/111002 + 74002/111003 + 27751/111004 + 88804/111005 + 55503/111006 + 102468/111007 + 27752/111008 + 74006/111009 + 104480/111010
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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