4
$\begingroup$

I came across this puzzle:

A wayfarer asks a shepherd how many sheep he has. He replies that if he numbered them two and two, or three and three, or four and four, or five and five, or six and six, there was always one over. If he numbered them by seven and seven there was none over. How many sheep had he?

It is relatively easy to find a solution using constraints that you can construct from the information in the puzzle (hints):

Constraint 1: The number of sheep must be a multiple of seven. This one is obvious.
Constraint 2: The number of sheep minus 1 must be a multiple of 60. This is the lowest number that has 2, 3, 4, 5 and 6 as divisors.

and using a little bit of trial and error (solution):

1 x 60 + 1 = 61, but is not a multiple of seven
2 x 60 + 1 = 121, but is not a multiple of seven
3 x 60 + 1 = 181, but is not a multiple of seven
4 x 60 + 1 = 241, but is not a multiple of seven
5 x 60 + 1 = 301 and is a multiple of seven. It is the lowest number of sheep that solves the puzzle

My questions now are:
1. Can this puzzle be solved without trial and error, using calculations or reasoning?
2. Is there only one solution?

I don't know the answers to these questions.

$\endgroup$
  • $\begingroup$ I got 721 first. $\endgroup$ – Joe Z. Aug 25 '15 at 17:37
  • $\begingroup$ @JoeZ. There is one smaller value that satisfies the conditions... $\endgroup$ – NZD Aug 25 '15 at 20:34
  • $\begingroup$ I noticed. I read the answers at the bottom. $\endgroup$ – Joe Z. Aug 26 '15 at 0:37
6
$\begingroup$

This is a system of equivalences. You may want to check the Chinese Remainder Theorem (which says that there is just one solution modulo 420): https://en.wikipedia.org/wiki/Chinese_remainder_theorem and the Extended Euclidean algorithm (which gives you a way to compute such systems in general): https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

$\endgroup$
1
$\begingroup$

Well, you did solve it with calculations and reasoning - you didn't try every number one-by-one! There's no faster way to do it, though.

And no, there isn't only one solution - you can always add the least common multiple of 2 through 7 (420) to get another valid answer. So 721, 1141, 1561... will all also be correct. The number you got is the smallest though - by the Chinese Remainder Theorem, all solutions are congruent modulo 420 (they give you the same remainder when divided by 420) so any possible answer less than 420 is the smallest (unless you're including negative sheep, of course).

$\endgroup$
  • $\begingroup$ You mean 1141, 1561, ... $\endgroup$ – Duncan Aug 25 '15 at 16:52

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.