You are a chinese general and you want to count your army. Your estimate is 790,000 - 810,000. Propose the counting to determine the result unambiguously.

The soldiers can only count from to 1 to 12.

As an example remainders for the task, this information is given: every even counting of the soldiers left the remainder of $0$ and odd counting left the remainder of $1$. However, @Sandeep Silwal suggested, that this is wrong and it could be the other way around.

I tried both. In Sage software I got the following results:

CRT_list([1,1,1,0], [5,7,11,12])


CRT_list([0,0,0,1], [5,7,11,12])


The first query is for even counting -> remainder $0$, odd counting -> remainder $1$.

The second one is the opposite.

Neither of the results is in the range $\langle 790000, 810000 \rangle$. What's more, according to the theorem, the number of the army should be $\le n_1 \cdot n_2 \cdot n_3 \cdot \dots$, where $n_i$ is the number in the modulo operation (am I right? I found this information in a few places). If the soldiers can count up to twelve, there is no possibility to find any coprime numbers that would multiply to give a result big enough for the range $\langle 790000, 810000 \rangle$.

How to approach this problem?


Just consider the remainder of the army modulo $2,3, \cdots, 12$. Then by CRT, we get an answer modulo $lcm(1,2, \cdots, 12) > 810,000-790,000$.

Edit: The added information makes no sense. If every even counting is $0$, then the number of solderer is a multiple of $6$. If every odd counting is $1$, then the number of soldiers is not a multiple of $3$ which is a contradiction.

  • $\begingroup$ I updated my question with more details. I tried to apply what you proposed in Sage software, but I got an error: No solution to crt problem since gcd(60,6) does not divide 16-0 for a query of CRT_list([0,1,0,1,0,1,0,1,0,1,0], [2,3,4,5,6,7,8,9,10,11,12]). What am I doing wrong? $\endgroup$ – vtvs Apr 13 '14 at 21:32
  • $\begingroup$ Ok, then there must be some mistake in the task. $\endgroup$ – vtvs Apr 13 '14 at 21:50
  • $\begingroup$ It would make sense if it was the other way around. $\endgroup$ – Sandeep Silwal Apr 13 '14 at 21:51
  • $\begingroup$ 1. Could you also explain why the number would be a multiple of $6$ or not a multiple of $3$? 2. The other way around I get an error: No solution to crt problem since gcd(60,6) does not divide 45-1 $\endgroup$ – vtvs Apr 14 '14 at 6:45
  • $\begingroup$ Ok, I forgot the numbers shoould be coprime. However, please take a look at the modified question. $\endgroup$ – vtvs Apr 14 '14 at 7:37

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.