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

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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.

Answer 4

What do we know about your numbers?

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.

Answer 5

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!!

Answer 6

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.

Answer 7

$$\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$$