Brain Teasers
How Many Eggs
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?
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?
Hint
Recall that if n is a prime number, (n-1)!+1 is divisible by n.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 Hint Show Hint Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
GOOD ONE!
I
L O V E D IT!
I
L O V E D IT!
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.
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.
Oops! My apologies. I did not see that last bit about being evenly divisible by 11. Sorry!
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 eleven-elevenths, 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,...})
2520 * i + 1 = N = n * 11
(229 1/11) * i + 1/11 = n
The next goal is to get a nice whole from eleven-elevenths, 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,...})
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.
I would spent less time deciphering 3628801=27720*130+25201 if written 3628801/27720=130 r. 25201 or 3628801(MOD27720)=25201.
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...
qwertyopiusa: It is not two-hundred-twenty-nine. It is the mixed fraction two-hundred-twenty-nine-and-one-eleventh. (Also read/use your Private Messages. You'll find shortcut to them in column at left.)
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.
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.
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;
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;
To post a comment, please create an account and sign in.
Follow Braingle!