All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 The farmer and the sheep (Posted on 2008-07-11)
A farmer has some number of sheep and needs to divide them into equal groups.

He tries groups of 2, but finds he has 1 left over.

Then he tries groups of 3, but has 2 left over.

Then he tries groups of 4, but has 3 left over.

And so on, until he gets to groups of 17, and the sheep fit perfectly.

What is the minimum number of sheep he has?

 See The Solution Submitted by pcbouhid Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 1 of 5

Let the number of sheep the farmer possesses be N. By the problem, dividing N by 2, 3, 4, ....., 15, 16 in turn, a remainder of -1 is obtained in each case.

Thus, N = m*LCM(2,3,4,.....,15, 16) - 1
0r, N = 720,720*m - 1, whenever m is a positive integer

Since by the problem, N is evenly divisible by 17, we must have:

720,720*m (mod 17) = 1
or, 5*m (mod 17) = 1(mod 17) = 35
or, m (mod 17) = 7
or, m = 17*p + 7, where p is a nonnegative integer.
or, N = 720,720(17*p + 7) - 1
= 12,252,240*p + 5,045,039

The minimum value of N occurs whenver p = 0, giving: N = 5,045,039

Consequently, the required minimum number of sheep is 5,045,039.

Edited on July 11, 2008, 11:38 am
 Posted by K Sengupta on 2008-07-11 11:37:09

 Search: Search body:
Forums (0)