Markers and leftovers

Identity · 2007-10-21 01:57:59

If a set of markers if placed in rows of 4 each, there are 2 markers left over; if in rows of 5 each, there are 3 left over; and if in rows of 7 there are 5 left over. What is the smallest number of markers that the set could contain?

I dunno what to do next... I've heard it can be solved with chinese remainder theorem but I haven't learnt that yet.

Last edited by Identity (2007-10-21 02:01:07)

mathsyperson · 2007-10-21 02:34:05

Clearly, if there were 4x5x7 = 140 markers, then you would be able to place them into groups of 4, 5, or 7 without having any leftovers in each case.

In your problem though, the number of leftovers always needs two more markers to complete the set. Therefore, the amount of markers is 140-2 = 138.

That doesn't prove that 138 is the lowest answer, but I'm pretty sure it is.
I strongly suspect that each number from 1 to 140 will give a different set {a,b,c} defined by x=a (mod 4) = b (mod 5) = c (mod 7).

Thus, the set {2,3,5} would be unique to 138.

Identity · 2007-10-21 02:48:13

Thanks, I get it now! You see, instead of thinking, '2 more markers makes 4, 2 more markers makes 5, 2 more markers makes 7', I was thinking '2 less markers makes 0, 3 less markers makes 0, 4 less markers makes 0'! And of course that is futile!

mathsyperson · 2007-10-21 03:03:19

I was thinking that as well, to be honest.

I combined 2(mod 4) and 3(mod 5) into 18(mod 20), just by going through numbers that fit the first until I found one that fit the second, and then did a similar process to combine 18(mod 20) with 5(mod 7).

It's only when I found the answer that I realised the "easy" way.

JaneFairfax · 2007-10-21 07:36:17

You can do this step by step. First, concentrate on the first two congruences.

By inspection, k[sub]1[/sub] = k[sub]2[/sub] = −1 is one solution. (There are infinitely many solutions; we just take one of them, hopefully the simplest one.) Thus, x must be ≡ −2 (mod lcm(4,5)) = −2 (mod 20). (Never mind the negative number at the stage.) Now combine this with the other congruence and repeat the process.

Hence x ≡ −2 (mod lcm(20,7)) = −2 (mod 140). The smallest positive such x is is 138, so the answer is 138.

Identity · 2007-10-21 22:23:40

Thanks Jane I guess that works too

Math Is Fun Forum

#1 2007-10-21 01:57:59

Markers and leftovers

#2 2007-10-21 02:34:05

Re: Markers and leftovers

#3 2007-10-21 02:48:13

Re: Markers and leftovers

#4 2007-10-21 03:03:19

Re: Markers and leftovers

#5 2007-10-21 07:36:17

Re: Markers and leftovers

#6 2007-10-21 22:23:40

Re: Markers and leftovers

Board footer