Solution to Problem 3

Congratulations to this week's winners

Kevin Bourrillion, Jon Dickmann,
Robert Krause, Daniel Reeves.

who will share the prize of $5.00. (Hey, it's a buck and quarter more than you had yesterday!)

There were 17 solutions received. Correct solutions were also received from Joshua Beenders, Dan Bradshaw, Jennifer Chong, John Dahlstrom, Jeff Decker, Mike Fitzpatrick, Mike Lepley, Steven Noto, Matt Rickert, Joshua McMinn, Tyler Scarlata and two from Math Department faculty! (They can play, but they can't win!)

The answer is: The cook got (at least) 4003 cows!

Some of you recognized the Chinese Remainder Theorem at work. Most solutions consisted of checking one number after another for the right conditions. A bit of preparation makes that task much less daunting. The following explanation is an amalgam of various solutions received.

Let n denote the number of cows in the herd. Then n leaves a remainder of 3 upon division by 25, a remainder of 7 upon division by 18, and a remainder of 10 upon division by 11. A common notation for this is

(1) n=3(mod 25)
(2) n=7(mod 18)
(3) n=10(mod11)

Let's start with the first equation. It gives as possible values of n the numbers 28, 53, 78,103,... The second equation says that n is 7 more than a multiple of 18, and so, since all multiples of 18 are even, n must be odd. This allows us to eliminate half of the possibilities from our first list; in particular, n is one of the numbers 53, 103, 153,... You quickly see that 153 satisfies both conditions (1) and (3). It follows that any other solution must be 153 more than a multiple of 275 (275 = 11x25). So

n = 153 + 275k, for some positive integer k.

Now look at the second condition. It gives us that n - 7 = 146 + 275k is divisible by 18. Factoring out as many 18's as we can, we get 146 + 275k = 18(8 + 15k) + (7 + 5k). Since the left hand side is divisible by 18, then 7 + 5k must be divisible by 18, too. Now you only have to check a very few numbers. The smallest possible solution is k = 14. Therefore, n = 153 + 275(14) = 4003. Of course, 4003 plus any multiple of 4950 (4950 = 25x18x10) will satisfy the three conditions just as well. But since a herd of 4003 cattle is already pretty big (in fact, it's huge!) it's safe to assume that this smallest solution is probably the right number.

You are visitor number 3533 to this page.
Page last updated 28 February 1997.