math
posted by tom on .
A peddler is taking eggs to the market to sell. The eggs are in a cart that holds up to 500 eggs. If the eggs are removed from the cart 2,3,4,5, or 6 at a time, one egg is always left over. If the eggs are removed 7 at time, no eggs are left over. How many eggs are in the cart?

First solve the simple problem of removing 2 and 3 eggs at a time, and there is nothing left over. The answer is therefore the LCM (Lowest Common Multiple) of 2 and 3, or 6.
If one egg is left over, we simply add one more to make 7 (or 1 to 12 to make 13, etc.)
Having done this, we are ready to find the number of eggs that has one left over when taken 2,3,4,5,6 at a time, namely the LCM of 2,3,4,5,6 (or its multiple) and add one.
This gives 60 as the LCM, or the multiples, such as 120, 180, 240, etc.
We will add one to these numbers to give 61, 121, 181, 241, etc. which will all satisfy the first five conditions (and less than 500).
However, the additional condition says that the number of eggs has to be divisible by 7. So by trying the numbers 61, 121, 181, 241, ... up to 421, we will find one that is divisible by 7, which is the answer required. 
A more often quoted version of this problem is:
A farmer taking her eggs to the market hits a pothole. The eggs all wind up broken. She then goes to her insurance agent who tells the farmer how many eggs did you have? She doesn't remember but she does remember how she placed them. She knew for a fact that when she put them in groups of 2,3,4,5 and 6 she had one egg left over but when she put them in groups of 7, she had none left over. What is the minimum number of eggs that the farmer could have had?
The simple approach
The L.C.M. (Lowest Common Multiple) of the numbers 2 through 6 inclusive is 2^2x3x5 = 60. The smallest number satisfying the divisors of 2 through 6 with remainders of 1 is therefore 60 + 1 = 61. Clearly, any multiple of 60 plus a 1 will satisfy these limited requirements. However, we are looking for a specific value of (60n + 1) that is evenly divisible by 7.or (60n + 1)/7. Dividing by 7, we get (60n + 1)/7 = 8n + 4n/7 + 1/7 or 8n + (4n + 1)/7 telling us that (4n + 1) must be a multiple of 7. Through observation, we can see that n = 5 is clearly the smallest integral value of n that will satisfy the condition. Therefore, the least number of eggs is (60x5 + 1) = 301.
Checking:
301/2 = 150 + 1
301/3 = 100 + 1
301/4 = 75 + 1
301/5 = 60 + 1
301/6 = 50 + 1
301/7 = 43
If we were not interested in the minimum amount of eggs, you can logically ask the question, "What other values of n will produce other answers?" Well, very quickly, 12 and 19 work. N(n=12) = 60(12) + 1 = 721. Thus, 721/2 = 360 + 1, 721/3 = 240 + 1, 721/4 = 180 + 1, 721/5 = 144 + 1, 721/6 = 120 + 1, and 721/7 = 103. N(n=19) = 60(19) + ! = 1141. Do you see the pattern in the additional values of n, 5, 12, 19,.......? The soluton is rather straight forward when the remainders are constant. If the remainders are all different however, the solution takes on a quite different challenge and is most easily solved by means of the Chinese Remainder Theorem.
An algebraic approach evolves as follows:
1We seek the smallest number N that meets the requirements specified above.
2We already know that the number 61 satisfies all the divisions and remainders up through the divisor of 6.
3What we now seek is N = 7A = 61 + 60n or 7A  60n = 61
4Dividing through by the smallest coefficient yields A  8n  4n/7 = 8 + 5/7 or (4n + 5)/7 = A  8n  8
5(4n + 5)/7 must be an integer as does (8n + 10)/7
6Dividing by 7 again yields n + n/7 + 1 + 3/7
7(n + 3)/7 is also an integer k making n = 7k  3.
8For the lowest value of k = 1, n = 4 making N = 61 + 60(4) = 301.
Again, higher values of N are derivable by letting k = 2, 3, 4,...etc. For k = 2, n = 11 making N = 721 and k = 3 leads to n = 18 or N = 1141.
The lengthy approach
The solution of this type of problem can also be solved algebraically.
Letting N be the number of eggs being sought, we can write
N/2 = A + 1/2 or N = 2A + 1
N/3 = B + 1/3 or N = 3B + 1
N/4 = C + 1/4 or N = 4C + 1
N/5 = D + 1/5 or N = 5D + 1
N/6 = E + 1/6 or N = 6E + 1
N/7 = F or N = 7F
Equating 2A + 1 = 3B + 1, B = 2A/3
A...3...6...9...12...15...18...21...24...27...30...33...36...39...42...45...48...51...54...57...60...63...66...69...72...75
B...2...4...6....8....10...12...14...16...18...20...22...24...26...28...30...32...34...36...38...40...42...44...46...48...50
A...78...81...84...87...90...93...96...99...102...105...108...111...114...117...120...123...126...129...132...135...138
B...52...54...56...58...60...62...64...66....68.....70.....72....74.....76.....78.....80....82.....84.....86....88.....90.....92
A...141...144...147...150
B....94.....96.....98...100
Equating 3B + 1 = 4C + 1, C = 3B/4
B...4...8...12...16...20...24...28...32...36...40...44...48...52...56...60...64...68...72...76...80...84...88...92...96...100
C...3...6...9....12....15...18...21...24...27...30...33...36...39...42...45...48...51...54...57...60...63...66...69...72....75
Equating 4C + 1 = 5D + 1, D = 4C/5
C...5...10...15...20...25...30...35...40...45...50...55...60...65...70...75...80...85...90...95...100
D...4....8....12...16...20...24...28...32...36...40...44...48...52...56...60...64...68...72...76....8
Equating 5D + 1 = 6E + 1, E = 5D/6
D...6...12...18...24...30...36...42...48...54...60...64...68...72...76...80
E...5...10...15...20...25...30...35...40...45...50...55...60...65...70...75
Equating 6E + 1 = F, F = (6E + 1)/7
E...1...8...15...22...29...36...43...50...57...64...71...78...85...92...99
F...1...7...13...19...25...31...37...43...49...55...61...67...73...79...85
Equating F = 2A + 1, A = (7F  1)/2
F..1...3....5....7...9...11...13...15...17...19...21...23...25...27...29...31...33...35....37....39....41....43...45....47...49
A..3..10..17..24..31..38...45...52...59...66...73...80...87...94..101.108.115..122..129..136..143..150..157..164..171
A tedious review of the data finds the highlighted set of numbers consistent throughout the data leading to
N = 2(150) + 1 = 3(100) + 1 = 4(75) + 1 = 5(60) + 1 = 6(50) + 1 = 7(43) = 301. 
301 eggs

I don't know