Broken Eggs

Date: 12/12/96 at 18:46:01
From: Chris Walker
Subject: Broken eggs

I have had this problem for a month and I can't figure out what to do.
Maybe you can help.

A farmer is taking her eggs to the market in a cart, but she hits a 
pothole, which knocks over all the containers of eggs.  Though she is 
unhurt, every egg is broken.  So she goes to her insurance agent, who 
asks her how many eggs she had.  She says she doesn't know, but she 
remembers somethings from various ways she tried packing the eggs.

When she put the eggs in groups of two, three, four, five, and six 
there was one egg left over, but when she put them in groups of seven 
they ended up in complete groups with no eggs left over.

What can the farmer figure from this information about the number of 
eggs she had?  Is there more than one answer?

I have already tried multiples of seven, but I can't figure the 
answer out.  Could you please tell me how to get the answer and also 
tell me what it is?

Thanks for your help.

Date: 12/12/96 at 19:41:38
From: Doctor Wilkinson
Subject: Re: Broken eggs

This kind of problem is pretty tricky if you've never seen anything
like it before.  

What you're looking for is a number that leaves a remainder of 1 when
divided by 2, 3, 4, 5, or 6, but that is evenly divisible by 7. So as
you already noticed, you only need to look at multiples of 7. Let's
try 7. We get off to a good start. 7 leaves a remainder of 1 when
divided by 2, 3, or 6. Unfortunately it doesn't work for 4. So let's 
see what we would have to do to get to a number which leaves a 
remainder of 1 when you divide it by 4, without losing what we've 
already got.

Well, if you take a number that leaves a remainder of 1 when you 
divide by 2 and add 2 to that number, you get another number that 
leaves a remainder of 1. So if you add any multiple of 2, you still 
get a number that leaves a remainder of 1 when you divide by 2.

Simliarly, if you take a number that leaves a remainder of 1 when you
divide it by 3 and add any multiple of 3 to it, you get another number 
that leaves a remainder of 1 when you divide it by 3.

Anything that leaves a remainder of 1 when divided by 2 or 3 
automatically leaves a remainder of 1 when you divide by 6, so we get 
that for free.

So if you take 7 and add anything which is a multiple of 2 and 3 and 7 
to it, you get another multiple of 7 which leaves a remainder of 1 
when you divide it by 2 or 3.  So we don't lose anything if we add a 
multiple of 42 (that's 2 x 3 x 7) to 7.  So lets' see if we can 
satisfy another of our conditions.

7 + 42 = 49.  Hey, that's good!  We've got a number that leaves a
remainder of 1 when you divide by 4.  It still doesn't work for 5,
though.  Can we use the same trick again?

If we add a multiple of 4 we still get a number that leaves a 
remainder of 1 when you divide by 4.  So if we add a multiple of
3 x 4 x 7, we'll get another number that satsifies all the conditions
so far.  There's only one to go!

Okay,  49 + 84 = 133.  No good.
      133 + 84 = 217.  No good.
      217 + 84 = 301.  Bingo!!

So 301 is a possible solution.  Are there any others?  Well, yes, 
because you can add a multiple of 3 x 4 x 5 x 7 to get another one.  
But usually what you're looking for is the smallest solution, so 301 
is probably the answer you want.

-Doctor Wilkinson,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 08/05/97 at 18:03:26
From: Rachel
Subject: Word problem - algebra?

The problem: A woman with a basket of eggs finds that if she removes 
either 2, 3, 4, 5, or 6 at a time from the basket, there is always one 
egg left over. If she removes 7 eggs at a time from the basket, there 
are no eggs left over. If the basket holds up to 500 eggs, how many 
eggs does she have?

I've solved the problem using trial and error. I found multiples of 7, 
and divided 2, 3, 4, 5, and 6 into all the multiples of 7. 301 seemed 
to be the answer because it is a multiple of 7, and when divided by 
2, 3, 4, 5, 6, there was always a remainder of one.  Is there a 
simpler and quicker way of solving this problem?

Date: 08/12/97 at 09:09:34
From: Doctor Rob
Subject: Re: Word problem - algebra?

More systematic, perhaps, but simpler?  You be the judge.

Let N be the number. Since it leaves a remainder of 1 on division 
by 6, it must be of the form N = 6*M + 1, where M is an integer.  
(We willassume that all variables below are integers, too.)  
This also takes care of division by 2 and 3, since

   N = 6*M + 1 = 2*(3*M) + 1 = 3*(2*M) + 1.

Since N leaves a remainder of 1 on division by 5, it must be of the
form N = 5*L + 1 = 6*M + 1, so 5*L = 6*M, so L = 6*K and M = 5*K. 
Thus N = 30*K + 1. (This uses the fact that 5 and 6 have no common 
factor.)

Furthermore, N leaves a remainder of 1 on division by 4, so
N = 4*J + 1 = 30*K + 1, so 4*J = 30*K, or 2*J = 15*K. This means that
J = 15*I and K = 2*I, so N = 60*I + 1. (This uses the fact that 2 and
15 have no common factor.)

At this point, you could try values of I = 0, 1, ..., until you found
a solution. Alternatively, you could continue in the following vein.

Finally N leaves a remainder of 0 on division by 7, so

            N = 7*H = 60*I + 1 = (7*8 + 4)*I + 1,
        7*(H - 8*I) = 4*I + 1,
     7*(2*H - 16*I) = 8*I + 2,
 7*(2*H - 17*I) - 2 = I,

so put   2*H - 17*I = G, and I = 7*G - 2, so H = 60*G - 17.  Then

                  N = 420*G - 119.

A number is of the above form if and only if it satisfies the
divisibility conditions of the problem. The smallest positive answer
occurs when G = 1, N = 301, which is the answer you found the long 
way.

If you ever learn modular arithmetic, you will find that there is a
systematic way of solving all such problems using the Chinese 
Remainder Theorem.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/