1
$\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
12
$\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

EDIT:

Now that almost one year passed, I would like to confess that the "extended the search to $n \leq 111111$" part was a joke...

Sadly nobody seems to find it funny ...

Or perhaps nobody ever cares (including the OP, who is probably busy conjecturing all kinds of things) ...

$\endgroup$

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.