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

Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
12 replies · 3K views
RubixRevenge
Messages
1
Reaction score
0

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.
 
Last edited:
Physics news on Phys.org

Discussion

RubixRevenge said:

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.
 
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!
 
bigfooted said:
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.
 
2517 is the smallest number of cards: 4*7*9*10 - 3
 
bigfooted said:
2517 is the smallest number of cards: 4*7*9*10 - 3

Really? Then why does 1257 cards work as well?
 
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.
 
bigfooted said:
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.
 
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.
 
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?
 
bigfooted said:
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
 
Dick said:
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.