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$
2
  • $\begingroup$ If $m$ is smaller than the last prime before $n$, then this prime appears in the denominator. $\endgroup$
    – WhatsUp
    Commented Nov 27, 2018 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$ Commented Nov 27, 2018 at 13:15

1 Answer 1

13
$\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$
0

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