Solutions – two remainder puzzles
January 11, 2008 pm31 5:12 pm
- I tried to divide my collection of rocks into two equal piles, but there was one left over. Then I tried to divide it into three equal piles, but there was one left over. When I tried to divide it into four equal piles, there were three left over. When I tried to divide it into five equal piles, there were three left over. When I tried to divide it into six equal piles, there was one left over. Then I divided it into seven equal piles. Can you imagine doing all this dividing with almost a thousand rocks? How many did I have?
- This (I believe) is not classic: Consider the sum of the remainders when a number is divided by 1, 2, 3, 4, and 5. Under what conditions will the number be a multiple of this sum?
Add solutions below.
Add comments and questions by clicking this.
JD2718 
JD I figure 763. I trial and errored it using primes greater than 7 with a 9 in the ones place until reaching 109. I can’t reason out the second half of your question. 7 works, 8 does not. Since your example gives an answer that also does not work I with say that a multiple of 7 works up to 7 squared b/c the first prime greater that 7 fails, ie 11.
Buffaloed.
Matt
Austin
One can write down all integers from 0 to 1000 and do 6 steps of stiking some of them off:
1) strike off all integers dividing by 2;
2) strike off all integers giving a remainder 0 or 2 when dividing by 3;
…
6) strike off all integers not dividing by 7.
When this is done, only 343 and 763 have left out (so it would probably be 763 if it is `almost 1000`). I guess, that have something common with the sieve of Eratosthenes.
Or in C++:
#include
int main() {
for (int i=0;i<1001;i++)
if (i%2==1 && i%3==1 && i%4==3 && i%5==3 && i%6==1 && i%7==0) std::cout <<i<<“\n”;
system(“Pause”);
return 0;
}
Another way of approaching the classic puzzle (apart from brute force): we know that X will be one greater than a multiple of 2, 3, and 6, but 6 is 2×3, so X will be in the form N*6+1. X is also M*5+3 and L*4+3 (or M*5-2 and L*4-1). I’m not sure where to go from there, but I have a headache, and it’s my daughter who’s in an MAO competition this morning…
For the second puzzle: For all positive numbers, a modulo 1 = 0, so we can ignore that and ask when a is a multiple of (a modulo 2) + (a modulo 3) + (a modulo 4) + (a modulo 5), or a modulo ((a modulo 2) + (a modulo 3) + (a modulo 4) + (a modulo 5)) = 0. Oooh, my headache’s just doubled. I’m sure there’s some part of abstract algebra that would help… well, obviously, it’s true if a is just the plain sum… so let’s see if a prime number will work. 7 works (as the exact sum), but neither 11 nor 13 works, and I suspect 7 would be the only prime that works.
And at this point I give up…
The solution to the first puzzle is fairly straightforward. You can actually start out with N = 4x+3 this gives you a remainder of 1 mod 2 and 3 and a remainder of 3 mod 4. As N has a remainder of 3 mod 5 as well it follows that x is divisible by 5. So N = 20y+3. Now as N still has to give a remainder of 1 mod 3 and 20 = 2 mod 3 it follows that y has to be 2 mod 3. So y = 3z + 2. Now N = 60z+43. Reducing this mod 5 we get N’ = 4z’+1. This has to be 0 mod 7 so z is 5 mod 7.
From this it follows that the number of stones is of the form N = 420z+343.
Todd Trimble said:
JBL is right about the Chinese remainder theorem, and it applies to the second problem as well. I am happy to explain the details behind my solution to the second problem, but it involves a fair bit of analysis.
Without the details, here’s my answer. If you think I made a mistake, please let me know!
The number n must be of one of the following forms:
0
12m but not of the form 60m (m nonzero)
60m + r where r is one of 6, 16, 20, 21, 28, 30, 32, 40, 54, 55
420m + r where r is one of 7, 49, 63, 98, 154, 371, 413.
Todd,
how did you arrive at your answer? Did you consider the 8 cases, or did you do something fancier?
Nothing too fancy, really. (By 8 cases, I am guessing you mean those remainder sums for which there exists a solution, namely where the remainder sums are in the range 0, 1, …, 7). I just worked out which quadruples (a, b, c, d) [of remainders mod 2, 3, 4, 5] could possibly yield a solution, and then (implicitly) used the Chinese Remainder Theorem to work those solutions out. There are some tricks here and there which shorten the work, but nothing extremely clever.
I am happy to write out details, but it would make for a somewhat lengthy comment :-).
It sounds like the same approach, although I am curious how you streamlined yours. We do differ slightly, so I am busy testing…
I guess I’ll go ahead then. Hopefully what I write will be understandable for a large readership (some slight acquaintance with modular arithmetic is assumed).
**Spoilers follow**
We are trying to characterize those integers n for which the remainders a mod 2, b mod 3, c mod 4, and d mod 5 yield a sum s = a + b + c + d which divides n (is 0 mod n). Since the remainder mod p of an integer is by definition in the range 0, 1, …, p-1, we see that the minimum remainder sum a + b + c + d is 0, and the maximum remainder sum s is 1 + 2 + 3 + 4 = 10.
If s = 10, then s cannot divide n: otherwise 2 and 5 divide n, so that the remainders a mod 2 and d mod 5 are 0, whence the remainder sum s cannot exceed 0 + 2 + 3 + 0, contradiction. By similar reasoning, if s = 8 or s = 9, then s cannot divide n (otherwise consider, respectively, the remainders mod 4 or mod 3, and derive a contradiction as before).
So solutions exist only in the cases where s is in the range 0 to 7. The case s = 7 is somewhat handled slightly differently from the remaining cases, essentially because 7 is relatively prime to the moduli 2, 3, 4, 5. I will treat the remaining cases first. It is helpful to bear in mind that the remainder c mod 4 determines a mod 2: if c = 0 or 2, then a = 0; if c = 1 or 3, then a = 1.
If s = 0 and n is a multiple of s, then of course n = 0. Henceforth we ignore this case.
If s = 1, then c cannot be 1 (since then a = 1), 2, or 3. So a and c are 0. There are thus two possibilities for (a, b, c, d): (0, 1, 0, 0) and (0, 0, 0, 1).
If s = 2, then n is even. This means either c = 2 (yielding (0, 0, 2, 0), or c = 0, where there are three possibilities: (0, 1, 0, 1), (0, 2, 0, 0), and (0, 0, 0, 2).
If s = 3, then b = 0. We cannot have c = 3, since there a = 1. Looking at c, we have three possibilities: (0, 0, 0, 3), (1, 0, 1, 1), and (0, 0, 2, 1).
If s = 4, then c = 0 and a = 0. The possibilities are either (0, 0, 0, 4), (0, 1, 0, 3), or (0, 2, 0, 2).
If s = 5, then d = 0. The sum s = a + b + c + 0 is less than 5 unless c = 3, whence a = 1 and b = 1: (1, 1, 3, 0) is the only possibility.
If s = 6, then a = 0 and b = 0. The sum s = c + d is less than 6 unless c = 2 or 3; it must be 2 since s is even. So (0, 0, 2, 4) is the only possibility.
That exhausts the possible quadruples for s = 1 to 6. Again, since c determines a, it is enough to consider the corresponding triples (b, c, d) of remainders mod 3, 4, and 5, and to solve for each such triple from the list above the corresponding n. Since any two of 3, 4, and 5 are relatively prime, the Chinese Remainder Theorem guarantees that each such triple has a solution, and that all such solutions for a given triple have the same remainder r modulo 3 x 4 x 5 = 60. That is, once we determine r, all solutions for that triple are of the form 60m + r.
It is useful to solve for the special triples (b, c, d) = (1, 0, 0), (0, 1, 0), and (0, 0, 1) [whether these triples belong to the list above is immaterial]. A solution for (1, 0, 0) is 40; a solution for (0, 1, 0) is 45, and a solution for (0, 0, 1) is 36. Then, for each triple (b, c, d) in the list above, it suffices to compute (b x 40) + (c x 45) + (d x 36), and take its remainder r mod 60. This can be done quickly on a hand calculator. I will exhibit each (b, c, d) from the list above together with the desired remainder r.
(1, 0, 0): 40
(0, 0, 1): 36
(0, 2, 0): 30
(1, 0, 1): 16
(0, 0, 2): 12
(0, 0, 3): 48
(0, 1, 1): 21
(0, 2, 1): 6
(0, 0, 4): 24
(1, 0, 3): 28
(2, 0, 2): 32
(1, 3, 0): 55
(0, 2, 4): 56
Notice the cases r = 12, 24, 36, 48 are covered where I considered numbers of the form 12m but not 60m.
Finally, we have the case s = 7. Here, the condition that 7 divides n does not put any extra constraints on a, b, c, d besides the fact that they add to 7 [and as usual c determines a]. The case c = 0, a = 0 is impossible. The case c = 1, a = 1 yields (1, 1, 1, 4) and (1, 2, 1, 3). The case c = 2, a = 0 yields (0, 1, 2, 4) and (0, 2, 2, 3). The case c = 3, a = 1 yields (1, 0, 3, 3), (1, 1, 3, 2), and (1, 2, 3, 1).
This time we have to solve for n where the remainders (b, c, d) are given by the 7 possibilities above, and where the remainder e mod 7 is 0. Again we solve for the special cases where (b, c, d, e) are (1, 0, 0, 0), (0, 1, 0, 0), and (0, 0, 1, 0) [working now mod 420 = 3 x 4 x 5 x 7]. A solution for (1, 0, 0, 0) is 280. A solution for (0, 1, 0, 0) is 105. A solution for (0, 0, 1, 0) is 336. Then, as before, for each triple (b, c, d) in the list for s = 7, we compute (b x 280) + (c x 105) + (d x 336) and compute the remainder r mod 420. Here are the results I got:
(1, 1, 4): 49
(2, 1, 3): 413
(1, 2, 4): 154
(2, 2, 3): 98
(0, 3, 3): 63
(1, 3, 2): 7
(2, 3, 1): 371
This completes my solution.
Thanks. We did have the same thing (I missed your 60m +12, +24, +36, +48 through careless reading).
I checked the sum of the residues for each number from 1 – 60
0: 60
1: 36, 40
2: 12, 16, 20, 30, 45
3: 6, 10, 21, 25, 48, 52, 56
4: 1, 5, 15, 24, 28, 32, 42, 46, 50, 57
5: 4, 8, 18, 22, 26, 33, 37, 41, 51, 55
6: 2, 9, 13, 17, 27, 31, 35, 44, 54, 58
7: 3, 7, 11, 34, 38, 49, 53
8: 14, 29, 39, 43, 47
9: 19, 23
10: 59
From there it was easy where the divisor is a factor of 60. Eg since 4 divides 60, 4 divides 60m + k iff 4 divides k, so we can pull 24, 28, and 32 off the list.
For divisors 7,8, and 9 there was a bit more work.
9|(60m + k) –> 3|k, so nothing there.
8|(60m + k) –> 4|k, so nothing there, either
and then 7, computed differently from you, but with the same result.