|
Question 329670: A man went to the zoo and visited the monkey house, carrying a bag of nuts. He found that is he divided them equally among the seven monkeys in the first cage he would have one nut left over. If he divided them equally among the eleven monkeys in the second cage there would be eight left over. If he divided them equally among the thirteen monkeys in the last cage there would be three left over.
He also found out that if he divided them equally among the monkeys in all three cages, or among the monkeys in any two cages, there would always be some left over.
What is the smallest number of nuts the man could have had in his bag? In general, how many nuts must he have? Explain
Answer by galactus(183)   (Show Source):
You can put this solution on YOUR website! Have you heard pf the Chinese Remainder Theorem?.
This is how I do it. There are other waays to go about it though.
Distributing the nuts among 7 monkies evenly gives:
x=1(mod 7)
Distributing the nuts among 11 monkies evenly gives:
x=8(mod 11)
Distributing the nuts among 13 monkies evenly gives:
x=3(mod 13)
We have the 3 congruency equations:
x=1(mod 7)........[1]
x=8(mod 11).......[2]
x=3(mod 13).......[3]
From [1], we have x=7t+1
Sub into [2]:
7t+1=8(mod 11)
7t=7(mod 11)
t=1(mod 11)
t=11s+1
x=7(11s+1)+1=77s+8
sub this into [3]:
77s+8=3(mod 13)
77s=-5(mod 13)
"Casting out 13's" gives:
-s=8(mod 13)
s=-8(mod 13)
s=13u-8
x=77(13u-8)+8
x=1001u-608
Now, lets check 1001u-608 by letting u=1. That will give the smallest amount.
Because if let x=0, we get -608. That is no good.
1001(1)-608=393
Check:
(393-1)/7=56
(393-8)/11=35
(393-3)/13=30
Yep, those constraints check out.
Now, there were two other constraints regarding all 3 cages. There are 31 monkies in all 3 cages. Does 31 leave some remainder when divided into 393?.
Yep, it does.
Any two cages can be 18 monkies, 20 monkies, or 24 monkies.
Do these numbers leave a remainder when divided into 393?.
Yep, they do.
The minimum amount of nuts he can have is 393.
|
|
|
| |
