Lovely Erasers

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.

  • I have no more than 100 erasers.
  • If you take 1 eraser from me, I am able to group the remaining into groups of 2.
  • If you take 2 erasers from me, I am able to group the remaining into groups of 3.
  • If you take 3 erasers from me, I am able to group the remaining into groups of 4.
  • If you take 4 erasers from me, I am able to group the remaining into groups of 5.

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 .


The answer is 59.

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.

2 solutions

Donglin Loo
Jun 19, 2018

If you add 1 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 2,3,4,5 .

The lowest common multiple(lcm) of 2 , 3 , 4 , 5 = 3 4 5 = 60 2,3,4,5=3\cdot4\cdot5=60

So the minimum number of erasers that I can have = 60 1 = 59 =60-1=59

The next number that meet the requirements = 60 2 1 = 119 =60\cdot2-1=119

But 119 > 100 119>100

So the answer we are looking for is indeed 59 \boxed{59}

Generalisation: \textbf{Generalisation:} The number of erasers that meet the requirements can be written as 60 k 1 60k-1 for positive integers k k .

Proof:

See Modular Arithmetic

Let the number of erasers be n n

n 1 0 ( m o d 2 ) n-1\equiv0(mod2)

n 1 ( m o d 2 ) \Rightarrow n\equiv1(mod2)

n 2 1 ( m o d 2 ) \Rightarrow n\equiv2-1(mod2)

n 1 ( m o d 2 ) \Rightarrow n\equiv-1(mod2)

n + 1 0 ( m o d 2 ) \Rightarrow n+1\equiv0(mod2)


n 2 0 ( m o d 3 ) n-2\equiv0(mod3)

n 2 ( m o d 3 ) \Rightarrow n\equiv2(mod3)

n 3 1 ( m o d 3 ) \Rightarrow n\equiv3-1(mod3)

n 1 ( m o d 3 ) \Rightarrow n\equiv-1(mod3)

n + 1 0 ( m o d 3 ) \Rightarrow n+1\equiv0(mod3)


n 3 0 ( m o d 4 ) n-3\equiv0(mod4)

n 3 ( m o d 4 ) \Rightarrow n\equiv3(mod4)

n 4 1 ( m o d 4 ) \Rightarrow n\equiv4-1(mod4)

n 1 ( m o d 4 ) \Rightarrow n\equiv-1(mod4)

n + 1 0 ( m o d 4 ) \Rightarrow n+1\equiv0(mod4)


n 4 0 ( m o d 5 ) n-4\equiv0(mod5)

n 4 ( m o d 5 ) \Rightarrow n\equiv4(mod5)

n 5 1 ( m o d 5 ) \Rightarrow n\equiv5-1(mod5)

n 1 ( m o d 5 ) \Rightarrow n\equiv-1(mod5)

n + 1 0 ( m o d 5 ) \Rightarrow n+1\equiv0(mod5)


n + 1 0 ( m o d 60 ) \therefore n+1\equiv0(mod60)

n + 1 = 60 k n+1=60k such that k k is positive integer.

Hence, we have n = 60 k 1 n=60k-1

Chew-Seong Cheong
Jun 24, 2018

Relevant wiki: Chinese Remainder Theorem

Let the number of erasers be n n . We can solve the problem using the Chinese remainder theorem (CRT) as follows.

n 1 (mod 2) n 2 a + 1 where a is an integer. 2 a + 1 2 (mod 3) 2 a 1 (mod 3) a = 2 n 2 × 3 b + 2 a + 1 = 6 b + 5 6 b + 5 3 (mod 4) 2 b + 1 3 (mod 4) 2 b 2 (mod 4) b = 1 n 24 c + 11 24 c + 11 4 (mod 5) 4 c + 1 4 (mod 5) 4 c 3 (mod 5) c = 2 n 24 ( 2 ) + 11 = 59 \begin{aligned} n & \equiv 1 \text{ (mod 2)} & \small \color{#3D99F6} \implies n \equiv 2a+1 \text{ where }a \text{ is an integer.} \\ 2a+1 & \equiv 2 \text{ (mod 3)} \\ 2a & \equiv 1 \text{ (mod 3)} & \small \color{#3D99F6} \implies a = 2 \implies n \equiv 2\times 3 b + 2a+1 = 6b+5 \\ 6b+5 & \equiv 3 \text{ (mod 4)} \\ 2b+1 & \equiv 3 \text{ (mod 4)} \\ 2b & \equiv 2 \text{ (mod 4)} & \small \color{#3D99F6} \implies b = 1 \implies n \equiv 24c + 11 \\ 24c+11 & \equiv 4 \text{ (mod 5)} \\ 4c+1 & \equiv 4 \text{ (mod 5)} \\ 4c & \equiv 3 \text{ (mod 5)} & \small \color{#3D99F6} \implies c = 2 \\ \implies n & \equiv 24(2) + 11 \\ & = \boxed{59} \end{aligned}

@Chew-Seong Cheong Thanks for your neat solution. Chinese Remainder Theorem is indeed a powerful theorem when it comes to dealing with remainders.

donglin loo - 2 years, 11 months ago

Log in to reply

Yes, it is useful for this type of problems.

Chew-Seong Cheong - 2 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...