# Aside from brute force, how can I solve this puzzle?

Once upon a time, and 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!

How many eggs did the old lady have?

Source (with solution): BrainBashers

From reading the puzzle, some easily-indentifiable properties of the total number of eggs are:

• it's a multiple of 11 (remainder of 0 if divided by 11)

• it's odd (if divided by 2 there's one egg remaining)

I haven't been able to come up with any other clues, so the only way I can see to solve this puzzle is to brute-force it (that is, start listing odd multiples of 11 and manually check if x modulo 3->10 = 1.

11, 33, 55, 77, 99, 121, 143...


At this point I got bored of brute-forcing it and decided there had to be a better way.

Is there? Can I use the other clues to build more rules to make it easier to find the correct number? (I started to think that maybe combining two clues would lead to a nugget of information, but then I couldn't figure out how to do that.) What math can I use to solve this other than brute-forcing the set of odd multiples of 11?

• The link you gave didn't turn up the same puzzle for me. But Google found a permalink, and there is a solution there (which is largely what I wrote, but less clear IMO and not completely correct). May 30, 2014 at 2:48
• I found a suitable answer really quickly with just 10!+1 May 30, 2014 at 14:40
• This is a version of the chinese remainder theorem problem. Take a look here for a general solution: en.wikipedia.org/wiki/Chinese_remainder_theorem Aug 1, 2014 at 13:39
• She couldn't count past 100 yet she had 25201 eggs? Did she have a chicken farm or something? Aug 10, 2015 at 7:34

Remove one egg. Now the number of eggs is divisible by 2, 3, 4, 5, 6, 7, 8, 9, 10. Therefore it is divisible by their least common multiple. There are algorithms to compute the LCM; for example you can write the prime factor decompositions and take the maximum for each factor. Here the result is 7*5*9*8 = 2520. So the original number of eggs is of the form 2520*x+1.

2520 divided by 11 is 229 with a remainder of 1. The successive values of the remainder of 2520*x+1 modulo 11 for x=1,2,3,… are 1+1, 2+1, 3+1, … so x=10 gives the smallest possible number of eggs: 2520*10+1 = 25201.

25201 is not the only answer: if you add 11 to x, you get another answer. The set of possible answers are all the numbers of the form 2520*(11*y+10)+1, i.e. 25201 plus any multiple of 27720.

• I'm pretty sure the LCM of 2,3,4,5,6,7,8,9,10 is 8*9*5*7=2520.
– user251
May 30, 2014 at 10:32
• @Arthur: Indeed it is. It's just a simple prime factorization after all: 2*2*2*3*3*5*7 = 2520. For the remainder of the solution we just need to solve 2520x + 1 mod 11 = 0 using modular math if we don't just want to try different x's until one works.
– Voo
May 30, 2014 at 15:32
• @ArthurFischer That teaches me not to write it out or check it. Thanks. May 30, 2014 at 18:22
• Hmm, this makes the statement "I can't count past 100" irrelevant, I was expecting that that statement limits the result to be below 100. Anyway, +1! Jul 14, 2014 at 5:06
• @justhalf I think it means the exact opposite, that the answer must be greater than 100. He can't count past 100, BUT he knows these other facts. Oct 24, 2014 at 16:57

Gilles certainly has the right idea, find the LCM of 2..10, +1. To take it a but further, here's the method I find easiest to find the LCM of relatively low (and/or easy-to-factor) numbers.

First, find the prime factors of all the numbers:

number factors
2 2
3 3
4 2, 2
5 5
6 2, 3
7 7
8 2, 2, 2
9 3, 3
10 2, 5

Now go through that list and find the highest count of each factor in any of the numbers. It may be easiest to make a table

number 2 3 5 7
2 2
3 3
4 2, 2
5 5
6 2 3
7 7
8 2, 2, 2
9 3, 3
10 2 5
max 2,2,2 3,3 5 7

Now just multiply all the numbers in the $$max$$ row and you have your number. If you rearrange and combine numbers in the right way it might be easier to multiply out in your head.

$$2\times2\times2\times3\times3\times5\times7 = 7\times9\times4\times10 = 63\times4\times10 = 2520$$

So we need to find a number of the form $$2520\times k+1 \equiv 0\mod11$$. Since $$2520 \equiv 1 \mod 11$$, we want the smallest $$k$$ such that $$1\times k + 1 \equiv 0\mod11$$. Conveniently, we can easily see that that will be $$k = 10$$, for a final answer of $$25201$$.

• May I also suggest adding the general solution $\forall\ n \in N: 2520 \times (11n + 10) + 1$? I mean sure it's obvious to you or me, but I'm not sure how common congruent math is in math classes. '
– Voo
May 30, 2014 at 16:08

As shown in Gilles' answer and others, it is straightforward to find answer E by noticing that E is divisible by 11, and E-1 is divisible by each of 2 through 10, hence by the LCM of 2 through 10, or 2520.

If the remainders were not all 1, a more-general approach would be needed. The Chinese remainder theorem (see Wikipedia) is good for such problems. The calculations below show an application of the constructive algorithm given in the Wikipedia article.

First, the method applies to pairwise coprime integers. For the present problem, we can work with 11, 9, 8, 7, 5 and ignore the other numbers because if the remainder is 1 when dividing by 8, then it's 1 when dividing by 4 or by 2; similarly for 9 vs 3. If it's 1 when dividing by 2 or 5, then it's 1 when dividing by 10; similarly for 2 and 3 vs 6. So it's adequate to work with {11, 9, 8, 7, 5}, members of which are pairwise coprime.

Next, N = 11·9·8·7·5 = 27720; and dividing N by members of {11, 9, 8, 7, 5} gives {2520, 3080, 3465, 3960, 5544}.

Now we apply the extended Euclidean algorithm to each nᵢ, N/nᵢ pair and obtain:

gcd 11, 2520 = 1 =  -229 * 11 +  1 * 2520
gcd  9, 3080 = 1 =  1369 *  9 + -4 * 3080
gcd  8, 3465 = 1 =  -433 *  8 +  1 * 3465
gcd  7, 3960 = 1 = -1697 *  7 +  3 * 3960
gcd  5, 5544 = 1 =  1109 *  5 + -1 * 5544


The products at the right are eᵢ; as a set, {2520, -12320, 3465, 11880, -5544}. Now we compute x = Σ(aᵢ·eᵢ) where the aᵢ are from the set of desired remainders, {0,1,1,1,1} for respective members of {11, 9, 8, 7, 5}. That is, x = 0*2520-12320+3465+11880-5544 = -2519, and we find that -2519 is indeed a solution, although negative.

At this point, we have -2519 as a result of applying the Chinese Remainder Theorem; now we need to observe that adding the LCM of {11, 9, 8, 7, 5}, or 27720, produces another solution, giving us the solution -2519+27720 = 25201, the same as mentioned in previous answers.

Well it's 1 greater than a multiple of 2.
1 greater than a multiple of 3.
1 greater than a multiple of 4.
...
1 greater than a multiple of 10.
a multiple of 11.

The first 9 properties are easy. 10! + 1 will cover that. The only question is, is it divisible by 11? Well, a quick check with a calculator reveals that it is.

therefore 3628801 is a possible answer.

The question doesn't seem to ask for the smallest solution, and in fact this puzzle has an infinite number of solutions.

• Actually, by Wilson's Theorem, n! + 1 will always be divisible by n+1 when n+1 is prime, so it's not necessary to check explicitly.
– user251
May 31, 2014 at 7:49
• @ArthurFischer Cool! Learn something new every day! After seeing that it was divisible by 11, I was wondering if it worked in general. Tried it for 11!+1 and it wasn't divisible by 12 and stopped there. I didn't consider that the primality would be that important here. Thank you Jun 2, 2014 at 13:17
• @ArthurFischer After reading a little bit on the theorem, it appears to go both ways actually. If n+1 is prime, then n!+1 is divisible by n+1. But also that if n!+1 is divisible by n+1, then n+1 is prime. Jun 2, 2014 at 13:48

You can use the Least Common Multiple of all the numbers from 2 to 10, inclusive, which is 2520, then add 1, which would be 2521. Then take 2521 mod 11, which is congruent to 2 mod 11. Then you add another 2520, and take 5041 mod 11, which is congruent to 3 mod 11. Noticing that it increases by 1 mod 11 each time, and since you want 0 mod 11, or 11 mod 11, you'll need to add $2520*8$ to 5041, which gives us the desired $25201$.

By the way, 25201 eggs will weigh over 3000 pounds!!

Here are some ideas for constructing such a number (x):

• X mod 10 = 1: This means that the ones digit of X is 1.
• X mod 9 = 1: This means that the sum of all of the digits except the ones digit is 9. I know this because the sum of the digits of all numbers divisible by 9 is 9 (549 -> 5 + 4 + 9 = 18 -> 1 + 8 = 9)
• X mod 4 = 1: This is important because numbers divisible by 4 have a property that the last two digits of the number are divisible by 4. (I know that 46382648462984624 is divisible by 4 because the last two digits, 24, are divisible by four)
• Let's look at what this means. Take the number 331. Subtract 1 to get 330. The last two digits of 330 are not divisible by 4, therefore X <> 331. In fact we can say that the last two digits of X cannot be 31. So X <> 531, and X <> 75873631, you get the idea.
• From the previous point, you can see that the last two digits of X must be one of { 01, 21, 41, 61, and 81 }

This should narrow down your search space. Let's try some numbers:

• 110: While divisible by 11, the ones digit is not 1, the digits don't sum to 10, and 09 is not divisible by 4. X <> 110
• 121: The ones digit is 1, but the digits don't sum to 10, and 20 is not divisible by 4. X <> 121:
• 281: The ones digit is 1, the digits sum to 10, and 80 is divisible by 4. X is a candidate.

Now you just have to check is 281 is divisible by 11, and that 280 is divisible by 8, 7, and 6. You know it's divisible 5 because it's divisible by 10. Same thing for 4 -> 8, 3 -> 9, and 2 -> 8.

$$\begin{array} LLCM(2,3,4,5,6,7,8,9,10)&=2\times3\times2\times5\times7\times2\times3\\ &=2520\end{array}$$ Let $x+1$ be the solution
And $x,n,k\in\mathbb{N}$ $$x\equiv0\mod2520$$ $$x=2520n$$ $$x+1\equiv0\mod11$$ $$2520n+1\equiv0\mod11$$ $$2520n\equiv10\mod11$$ $$2520\equiv1\mod11$$ $$n\equiv10\mod11$$ $$n=11k+10$$ $$x+1=2520(11k+10)+1$$

• Why the down vote? Dec 9, 2014 at 5:56
• Probably because this question has been answered multiple times before, and there is no point for another answer. Aug 10, 2015 at 7:34