How Many Eggs
Math brain teasers require computations to solve.
Once upon a time, an old lady went to sell her vast quantity of eggs at the local market.
When asked how many she had, she replied:
Son, I can't count past 100 but I know that 
If you divide the number of eggs by 2 there will be one egg left.
If you divide the number of eggs by 3 there will be one egg left.
If you divide the number of eggs by 4 there will be one egg left.
If you divide the number of eggs by 5 there will be one egg left.
If you divide the number of eggs by 6 there will be one egg left.
If you divide the number of eggs by 7 there will be one egg left.
If you divide the number of eggs by 8 there will be one egg left.
If you divide the number of eggs by 9 there will be one egg left.
If you divide the number of eggs by 10 there will be one egg left.
Finally, if you divide the number of eggs by 11 there will be NO EGGS left!
What's the minimum number of eggs that the old lady could have?
HintRecall that if n is a prime number, (n1)!+1 is divisible by n.
Hide
Answer
10!+1=3628801 eggs. This is an answer, but not the minimum.
The least common multiple of 1 to 11 is 27720.
3628801=27720*130+25201.
Therefore, the old lady had at least 25201 eggs.
Hide
Comments
RedAngle65
Mar 14, 2006
 GOOD ONE!
I
L O V E D IT! 
Jimbo
May 06, 2006
 Except the answer is incorrect.
Div by 2 min is 2 + 1 = 3
Div by 3 min is 2 x 3 + 1 = 7
Div by 4 min is 2 x 6 + 1 = 13 (already have 2)
Div by 5 min is 5 x 12 + 1 = 61
Same for 6 as already have 2 and 3
Div by 7 min is 60 x 7 + 1 = 421
Div by 8 min is 420 x 2 + 1 = 841
(Already have 4)
div by 9 min is 840 x 3 + 1 = 2521
div by 10 same as already have 5 and 2. Answer 2521. 
Jimbo
May 06, 2006
 Oops! My apologies. I did not see that last bit about being evenly divisible by 11. Sorry! 
stil
May 11, 2006
 I prefer something more direct and forward. Look first for a number which is divisible by 2,3,...,9,10. Its factors are 7,5,3,3,2,2,and 2. (three 2's account for 8 and 4 as well as 2; two 3's for 9 and 3; the 5 and a 2 for 10; a 3 and a 2 for 6.) This number is 2520. Some integer multiples of this number incremented by 1 will be multiples of 11.
2520 * i + 1 = N = n * 11
(229 1/11) * i + 1/11 = n
The next goal is to get a nice whole from elevenelevenths, and i = 10 clearly takes you there, and quickly to N = 25201.
(And you don't have to work backward eliminating the cases where i={21,32,43,54,65,76,...}) 
stil
May 11, 2006
 Forgot to say how much I like factorial thing.
I would spent less time deciphering 3628801=27720*130+25201 if written 3628801/27720=130 r. 25201 or 3628801(MOD27720)=25201. 
qwertyopiusa
Nov 27, 2006
 Stil: could you explain where is the 229 coming from, and why i=10 is so "obvious"? It took me more than 1 hour to prove that i=10 gives you the minimum... 
stil
Nov 28, 2006
 qwertyopiusa: It is not twohundredtwentynine. It is the mixed fraction twohundredtwentynineandoneeleventh. (Also read/use your Private Messages. You'll find shortcut to them in column at left.) 
javaguru
Jan 23, 2009
 Very clever solution using the factorial!
I did it similar to Stil:
8x9x5x7=2520
Now the answer will be 2520 * n + 1 where n is the smallest positive integer that satisfies ((2520 % 11) * n) % 11 = 11  1
At this point since 2520 % 11 = 1 the answer 2520 * 10 + 1 was pretty obvious.
If 2520 % 11 = 2, then (2 * n) % 11 = 10 gives n = 5 and the answer would be 5 * 2520 + 1.

saska
Mar 06, 2017
 Here is a tiny liitle model to solve this puzzle with glpsol (a free linear and mixed integer programming solver, available for most platforms).
Run
glpsol glp m HowManyEggs.mod
to get the solution
# HowManyEggs.mod
var eggs integer, >=1;
set divs := 2 .. 11;
var m{i in divs} integer, >=1;
s.t. cd{i in 2 .. 10}: eggs = m[i] * i + 1;
s.t. c11: eggs = m[11]*11 + 0;
minimize obj: eggs;
solve;
printf "%d\n", eggs;
end; 
Back to Top
 
