950 views
0 votes
0 votes
There are 1000 villages and 1000 salesmen. 1st salesman visits every village. 2nd salesman visits every 2nd village starting from the second village. 3rd salesman visits every 3rd village starting from the third village. This process goes on till 1000th salesman visits the 1000th village (i.e. last village). Which of the following villages is visited by maximum number of salesman?

(a) 384  (b) 720

(c) 490  (d) 900

2 Answers

1 votes
1 votes
if we solve using finding factor method i think it should 720 because salesman only visit a village if it divides completely that village number according to question.
 

so 384 = 2^7 * 3 -> factors((7+1)*(1+1)=16)

     720 = 2^4 * 3^2 * 5 factors((4+1)(2+1)(1+1)=30)

     490 = 2 * 5 * 7^2 factors((1+1)(1+1)(2+1)=12)

     900 = 2^2 * 3^2 * 5 ^2 factors((2+1)(2+1)(2+1)=27)

so 720 has highest no. of factors among all.
1 votes
1 votes
Correct answer is 840.

A village $v$ is visited by salesman $s$ if $v$ is a multiple of $s$.

So a village which is visited by maximum number of salesman has largest number of multiples (between 1 and 1000).

We can find the required village by finding L.C.M. of first few numbers until it crosses 1000. We will stop when L.C.M. goes beyond 1000. So required village will be largest L.C.M (or its multiple) of first few numbers which is just smaller than 1000.

L.C.M. of 1 is 1.

L.C.M. of 1,2 is 2.

L.C.M. of 1,2,3 is 6.

L.C.M. of 1,2,3,4 is 24.

L.C.M. of 1,2,3,4,5 is 120.

L.C.M. of 1,2,3,4,5,6 is 120.

L.C.M. of 1,2,3,4,5,6,7 is 840.

L.C.M. of 1,2,3,4,5,6,7,8 is 840.

We can't go beyond 840 because L.C.M. of 1,2,3,4,5,6,7,8,9 is 2520 which is beyond 1000.

So correct answer is 840. Here is the code to verify : http://ideone.com/nzaAzI

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
0 answers
2
1 votes
1 votes
2 answers
3
Devshree Dubey asked Oct 9, 2018
576 views
What is the smallest number that when divided by 12, leaves 10, when divided by 16, leaves 14 and when divided by 24, leaves 22 as a remainder?