1
$\begingroup$

Let $n \in \{1,2,\ldots 9\}$. We've to find the number of such $n$, for which there is at least one permutation of the digits $1,2,\ldots,n$ which is divisible by $11$.

I tried to check for each value of $n$. For $n=1,2$, not possible. (I am checking through the divisibility test for $11$)

For $n=3$, $\color{blue} {132}$ is possible.

For $n=4$, $\color{blue}{1342}$ is possible.

But, now as $n$ grows larger and larger, it's difficult to check all the cases.

Although I tried making cases, and have finally found out the answer to be 5. But, Is there any quick way to solve the above problem?.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ The test for divisibilty by 11 is that the sum of the digits in the odd places minus the sum of the digits in the even places is a multiple of 11. $\endgroup$ – Gerry Myerson Nov 29 '17 at 8:13
  • $\begingroup$ $\frac{n(n+1)}{2}$ is sometimes even and sometimes odd. Note that $152638497$ is one of many solutions for $n=9$ $\endgroup$ – Henry Nov 29 '17 at 8:25
  • $\begingroup$ @GerryMyerson Yes, I know that, and I have used it too. That's the way I got the answer to be 5. $n=3,4,7,8,9$ satisfy given condition. $\endgroup$ – Jaideep Khare Nov 29 '17 at 8:27
  • $\begingroup$ You should tell us what you know when you post the question, Jaideep, otherwise, how can we tell whether there's a quicker way to solve it than the one you already know? $\endgroup$ – Gerry Myerson Nov 29 '17 at 8:29
  • 1
    $\begingroup$ @GerryMyerson I have already written that. See in second paragraph, last line. $\endgroup$ – Jaideep Khare Nov 29 '17 at 8:38
2
$\begingroup$

Let $\overline{a_1a_2\cdots a_n}$ be the number we want.

We have to have $$a_1+a_3+a_5+\cdots \equiv a_2+a_4+a_6+\cdots\pmod{11}$$


For $n=3$, we have to have $$a_1+a_3=a_2$$ It is easy to notice $(a_1,a_2,a_3)=(1,3,2)$.


For $n=4$, we have to have $$a_1+a_3=a_2+a_4$$ It is easy to notice that $\{a_1,a_3\}$ is either $\{2,3\}$ or $\{1,4\}$.


For $n=5$, since $(5+4+3)-(2+1)=9\lt 11$ and $(1+2+3)-(5+4)=-3\gt -11$, we have to have $$a_1+a_3+a_5=a_2+a_4$$ If RHS has two even, then RHS is even while LHS=odd+odd+odd=odd.

If each side has one even, then LHS=odd+odd+even=even while RHS=odd+even=odd.

If LHS has two even, then LHS=even+even+odd=odd while RHS=odd+odd=even.

So, there are no solutions for $n=5$.


For $n=6$, since $6+5+4-(3+2+1)=9\lt 11$, we have to have $$a_1+a_3+a_5=a_2+a_4+a_6$$ If LHS has three even, then LHS is even while RHS=odd+odd+odd=odd.

If LHS has only two even, then LHS=even+even+odd=odd while RHS=even+odd+odd=even.

So, there are no solutions for $n=6$.


For $n=7$, let us consider the case where $$a_1+a_3+a_5+a_7=a_2+a_4+a_6$$ You can start whatever you choose, say $$1+4+5+6\not=2+3+7$$ Since $(1+4+5+6)-(2+3+7)=4$ (this is always even, see below), we can exchange $5$ with $3$ (the difference $2$ is the half of $4$) to have $$1+4+3+6=2+5+7$$ which holds and $1245376$ is divisible by $11$.

The difference between LHS and RHS is always even since there are only four possibilities as follows :

  • odd+odd+odd+odd=even+even+even

  • even+odd+odd+odd=even+even+odd

  • even+even+odd+odd=even+odd+odd

  • even+even+even+odd=odd+odd+odd

(The only problem here is that we don't know if we can always find such two numbers to be exchanged. If you cannot find such numbers for an example you chose, you can try another exmaple. One good idea should be to "make each side have both odd and even".)


For $n=8$, let us consider the case where $$a_1+a_3+a_5+a_7=a_2+a_4+a_6+a_8$$ You can start whatever you choose, say $$1+4+5+6\not=2+3+7+8$$ Since $(1+4+5+6)-(2+3+7+8)=-4$ (this is always even, see below), we can exchange $7$ with $5$ (the difference $2$ is the half of $|-4|$) to have $$1+4+7+6=2+3+5+8$$ which holds and $12437568$ is divisible by $11$.

The difference between LHS and RHS is always even since there are only three possibilities as follows :

  • odd+odd+odd+odd=even+even+even+even

  • even+odd+odd+odd=even+even+even+odd

  • even+even+odd+odd=even+even+odd+odd


For $n=9$, we see that $$a_1+a_3+a_5+a_7+a_9=a_2+a_4+a_6+a_8$$ is impossible since the difference between LHS and RHS is always odd :

  • If RHS has four even, then RHS is even while LHS=odd+odd+odd+odd+odd=odd.

  • If RHS has only three even, then RHS=even+even+even+odd=odd while LHS=even+odd+odd+odd+odd=even.

  • If RHS has only two even, then RHS=even+even+odd+odd=even while LHS=even+even+odd+odd+odd=odd.

  • If RHS has only one even, then RHS=even+odd+odd+odd=odd while LHS=even+even+even+odd+odd=even.

  • If RHS has no even, then RHS=odd+odd+odd+odd=even while LHS=even+even+even+even+odd=odd

So, let us consider the case where $$a_1+a_3+a_5+a_7+a_9=a_2+a_4+a_6+a_8+11$$

You can start whatever you choose, say $$4+5+6+7+8\not=1+2+3+9+11$$ Since $(4+5+6+7+8)-(1+2+3+9+11)=4$ (this is always even since the difference without $11$ is odd as we've already seen), we can exchange $5$ with $3$ (the difference $2$ is the half of $4$) to have $$4+3+6+7+8=1+2+5+9+11$$ which holds and $413265798$ is divisible by $11$.

$\endgroup$
  • 1
    $\begingroup$ More or less, I did this question the same way as you did. But, as this was a question from a competitive exam, I thought that there must be a small way to do, but now I think this is the quickest way. Therefore, accepting. Thanks for your time. $\endgroup$ – Jaideep Khare Dec 2 '17 at 8:51

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.