As a student, I had a collection of erasers. One day, Dave came to me. He asked me how many erasers had I collected and I proposed a riddle.
Dave smiled and claimed to know the number of erasers I had.
So, how many erasers did I have?
Try more of my fundamental problems here .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Relevant wiki: Chinese Remainder Theorem
Let the number of erasers be n . We can solve the problem using the Chinese remainder theorem (CRT) as follows.
n 2 a + 1 2 a 6 b + 5 2 b + 1 2 b 2 4 c + 1 1 4 c + 1 4 c ⟹ n ≡ 1 (mod 2) ≡ 2 (mod 3) ≡ 1 (mod 3) ≡ 3 (mod 4) ≡ 3 (mod 4) ≡ 2 (mod 4) ≡ 4 (mod 5) ≡ 4 (mod 5) ≡ 3 (mod 5) ≡ 2 4 ( 2 ) + 1 1 = 5 9 ⟹ n ≡ 2 a + 1 where a is an integer. ⟹ a = 2 ⟹ n ≡ 2 × 3 b + 2 a + 1 = 6 b + 5 ⟹ b = 1 ⟹ n ≡ 2 4 c + 1 1 ⟹ c = 2
@Chew-Seong Cheong Thanks for your neat solution. Chinese Remainder Theorem is indeed a powerful theorem when it comes to dealing with remainders.
Log in to reply
Yes, it is useful for this type of problems.
Problem Loading...
Note Loading...
Set Loading...
If you add 1 eraser to the erasers that I had by far, the new number of erasers can be grouped into groups of 2 , 3 , 4 , 5 .
The lowest common multiple(lcm) of 2 , 3 , 4 , 5 = 3 ⋅ 4 ⋅ 5 = 6 0
So the minimum number of erasers that I can have = 6 0 − 1 = 5 9
The next number that meet the requirements = 6 0 ⋅ 2 − 1 = 1 1 9
But 1 1 9 > 1 0 0
So the answer we are looking for is indeed 5 9
Generalisation: The number of erasers that meet the requirements can be written as 6 0 k − 1 for positive integers k .
Proof:
See Modular Arithmetic
Let the number of erasers be n
n − 1 ≡ 0 ( m o d 2 )
⇒ n ≡ 1 ( m o d 2 )
⇒ n ≡ 2 − 1 ( m o d 2 )
⇒ n ≡ − 1 ( m o d 2 )
⇒ n + 1 ≡ 0 ( m o d 2 )
n − 2 ≡ 0 ( m o d 3 )
⇒ n ≡ 2 ( m o d 3 )
⇒ n ≡ 3 − 1 ( m o d 3 )
⇒ n ≡ − 1 ( m o d 3 )
⇒ n + 1 ≡ 0 ( m o d 3 )
n − 3 ≡ 0 ( m o d 4 )
⇒ n ≡ 3 ( m o d 4 )
⇒ n ≡ 4 − 1 ( m o d 4 )
⇒ n ≡ − 1 ( m o d 4 )
⇒ n + 1 ≡ 0 ( m o d 4 )
n − 4 ≡ 0 ( m o d 5 )
⇒ n ≡ 4 ( m o d 5 )
⇒ n ≡ 5 − 1 ( m o d 5 )
⇒ n ≡ − 1 ( m o d 5 )
⇒ n + 1 ≡ 0 ( m o d 5 )
∴ n + 1 ≡ 0 ( m o d 6 0 )
n + 1 = 6 0 k such that k is positive integer.
Hence, we have n = 6 0 k − 1