Southeastern Massachusetts Conference Math League: Set theory, gcf,lcm

[RubixRevenge]

Homework Statement

2.) if jimmy piles his baseball cards in stacks of 4, then there is 1 left over. if he piles them in stacks of 7, there are 4 left over. If he piles them in stacks of 9, there are 6 lefty over. If he piles them in stacks of 10, there are 7 left over. compute the smallest amount of baseball cards Jimmy could own.

Homework Equations

maybe using LCM?

The Attempt at a Solution

I spent 1 hour trying to figure out the solution and the only things I could figure out were that the ones digit has to be 7. I spent the rest of my time testing numbers with my calculator.
However, if this was the actual competition, I wouldn't have a calculator and I would only have 3-4 minutes to solve it. so I have no clue.

 

[Dick]

Homework Statement

2.) if jimmy piles his baseball cards in stacks of 4, then there is 1 left over. if he piles them in stacks of 7, there are 4 left over. If he piles them in stacks of 9, there are 6 lefty over. If he piles them in stacks of 10, there are 7 left over. compute the smallest amount of baseball cards Jimmy could own.

Homework Equations

maybe using LCM?

The Attempt at a Solution

I spent 1 hour trying to figure out the solution and the only things I could figure out were that the ones digit has to be 7. I spent the rest of my time testing numbers with my calculator.
However, if this was the actual competition, I wouldn't have a calculator and I would only have 3-4 minutes to solve it. so I have no clue.

There are systematic ways to do this. See for example, http://en.wikipedia.org/wiki/Method_of_successive_substitution. There's also http://en.wikipedia.org/wiki/Chinese_remainder_theorem for the case where your pile sizes are relatively prime (which yours aren't). To do it in 3-4 minutes without a calculator would probably take a lot of practice, and accurate arithmetic, but I'm guessing there are people would could do that.

 

[bigfooted]

This one is special. If you would never have any cards left (so you can pile them in stacks of 4,7,9,10), you would multiply the stack numbers: 4*7*9*10=2520
but note the sequence:
4 -> 1
7-> 4
9-> 6
10->7
You are always 3 cards short for the next stack!

 

[Dick]

This one is special. If you would never have any cards left (so you can pile them in stacks of 4,7,9,10), you would multiply the stack numbers: 4*7*9*10=2520
but note the sequence:
4 -> 1
7-> 4
9-> 6
10->7
You are always 3 cards short for the next stack!

Ooo. That's clever. So n=(-3) is an obvious solution. And you can add the product to get another. But that's not going to give you the smallest solution. I think you want an LCM instead of the product.

 

[bigfooted]

2517 is the smallest number of cards: 4*7*9*10 - 3

 

[Dick]

2517 is the smallest number of cards: 4*7*9*10 - 3

Really? Then why does 1257 cards work as well?

 

[bigfooted]

Yes, you're right, my mistake. But I don't know how you can see that actually 4*7*9*10/2 - 3 is the minimum.

 

[Dick]

Yes, you're right, my mistake. But I don't know how you can see that actually 4*7*9*10/2 - 3 is the minimum.

All that matters is that 4, 7, 9 and 10 divide the number you are adding to -3. So the smallest number to add is the least common multiple of 4, 7, 9 and 10. Which is only their product if they are relatively prime.

 

[Office_Shredder]

bigfooted, that's because if there were always zero cards left over you would want the least common multiple of 4,7,9 and 10, you wouldn't just multiply them all together.

 

[bigfooted]

Yes, I see that you shouldn't simply multiply because 4 and 10 are not prime. So when a and b are both divisible by 2, then the LCM is a*b/2? And when a and b are both divisible by prime p, then the LCM is a*b/p? And the LCM of a*b*p1*p2*p3 with prime numbers p1,p2,p3 is a*b/2*p1*p2*p3?

 

[Office_Shredder]

Yes to the first part, assuming that 2 (or p) is the only prime dividing a and b, and yes to the second part assuming furthermore that p1, p2 and p3 do not divide a or b. I recommend reading

http://en.wikipedia.org/wiki/Least_...least_common_multiples_by_prime_factorization

to get a better idea of how to compute them.

 

[Dick]

Yes, I see that you shouldn't simply multiply because 4 and 10 are not prime. So when a and b are both divisible by 2, then the LCM is a*b/2? And when a and b are both divisible by prime p, then the LCM is a*b/p? And the LCM of a*b*p1*p2*p3 with prime numbers p1,p2,p3 is a*b/2*p1*p2*p3?

No, it's not quite that simple. 4 and 8 are both divisible by 2 but LCM(4,8)=8, not 4*8/2=16. Maybe it would be simplest just to look at http://en.wikipedia.org/wiki/Least_common_multiple

 

[bigfooted]

No, it's not quite that simple. 4 and 8 are both divisible by 2 but LCM(4,8)=8, not 4*8/2=16. Maybe it would be simplest just to look at http://en.wikipedia.org/wiki/Least_common_multiple

True, but it works when a and b have only two prime factors with multiplicity 1, and in your example, 8 has multiplicity 2. For multiplicity 2 you have to divide by 2^2:
LCM(4,8)=4*8/2^2=8

I see in your wiki link that I should just multiply the prime factors with the highest multiplicities, so
LCM(4,7,9,10)=LCM(2^2, 7, 3^2, 2^1 * 5) = LCM(4,7,9,5) = 4*7*9*5=1260

OK, that makes sense now.