DS OG 128

This topic has expert replies
Junior | Next Rank: 30 Posts
Posts: 22
Joined: Sun Nov 21, 2010 6:21 pm

DS OG 128

by zachlebo » Mon May 23, 2011 11:52 am
A school administrator will assign each student in a group of N students to one of M classrooms. if
3 < M < 13 < N, is it possible to assign each of N students to one of M classrooms so that each classroom has the same number of students assigned to it?

1)It is possible to assign each of 3N students to one of M classrooms so that each classroom has the same number of students assigned to it.

2) It is possible to assign each of 13N students to one of M classrooms so that each classroom has the same number of students assigned to it.


I am having trouble rephrasing the question. I am guessing it is dealing with factors of M and N, and are prime boxes the best way to set up the possible outcomes?

Answer:

B

User avatar
GMAT Instructor
Posts: 199
Joined: Tue May 17, 2011 6:06 am
Location: Cambridge, MA
Thanked: 192 times
Followed by:121 members
GMAT Score:780

by Ashley@VeritasPrep » Mon May 23, 2011 6:11 pm
This is a tough problem! But yes, I think what you suggest is on the right track. Rephrasing-the-question-wise, the question of whether you can divide N students fairly among M classrooms is indeed exactly the question, "Is N a multiple of M?"

An important concept here, which I think you also allude to, is that a number N is a multiple of another number M precisely when ALL the prime factors of M show up in the prime factorization of N (and if a particular prime factor shows up more than once in the prime factorization of M, it must show up at least that many times in the prime factorization of N).

Now, looking at statement (1) tells us that 3N is a multiple of M. This COULD mean that N itself is a multiple of M (in which case we'd know the answer to our question was "YES"). OR it could mean that N was essentially ALMOST a multiple of M, and all that it lacked was the additional factor 3 (such that when we give it that 3 in 3N, we suddenly wind up with a multiple of M). If this is the case, M must have required that 3 by containing one itself, so given our bounds 3 < M < 13, M might have been 6 or 9 or 12. Then, for instance, had M been 6 (2x3), N could have been 14 (2x7)... in which case N itself would not be a multiple of M, because N's factorization would lack the necessary 3, but 3N would get that 3 to make 3N (42 in this case) a multiple of M. This scenario -- M = 6, N = 14 -- then satisfies the condition required by statement (1), but answers the question "NO." So overall we land at a "MAYBE," and statement (1) is INSUFFICIENT.

Statement (2) lets us apply the same logic, so in this case, the fact that 13N is a multiple of M means that EITHER N itself is a multiple of M (which would result in a "YES") OR N is ALMOST a multiple of M, but isn't quite because it lacks the necessary factor 13. The 13 would only be a necessary factor if there were a 13 in the factorization of M. BUT, there CAN'T be a 13 in the factorization of M, because we are given M < 13. So this alternative is impossible, and we can conclude that N itself is for sure a multiple of N. So we give a definite "YES" and say SUFFICIENT.

So, all told, the answer is B.

Hope that's all intelligible!

Best,
Ashley Newman-Owens
GMAT Instructor
Veritas Prep

Post helpful? Mosey your cursor on over to that Thank button and click, please! I will bake you an imaginary cake.

Junior | Next Rank: 30 Posts
Posts: 22
Joined: Sun Nov 21, 2010 6:21 pm

by zachlebo » Tue May 24, 2011 8:35 am
I do understand. do you have suggestions on practice problems for using Primes and Prime boxes? I know i need more practice

User avatar
Newbie | Next Rank: 10 Posts
Posts: 3
Joined: Sat Apr 16, 2011 12:53 pm

by CanadaRep » Tue May 31, 2011 12:52 pm
wow..what an amazing explanation. Yes..how do we practice more questions of these type?!! Very tricky!

User avatar
GMAT Instructor
Posts: 199
Joined: Tue May 17, 2011 6:06 am
Location: Cambridge, MA
Thanked: 192 times
Followed by:121 members
GMAT Score:780

by Ashley@VeritasPrep » Wed Jun 01, 2011 9:24 am
Hey guys,

Sorry for the delay in response! Yeah, this type of problem is probably one that everyone (myself very much included!) struggles with. I don't personally know of a specific resource that consolidates a whole bunch of problems like this all in one place (though others may -- others, feel free to weigh in!), but most problems that deal with factors/divisibility/multiples will hone some element of this type of thinking.

Here is a challenging one (I'm just making this up) to start you off:

If m is a positive integer, does 24 divide m?
(1) 54 divides m^2.
(2) 32 divides m^2.

See what you come up with!
Ashley Newman-Owens
GMAT Instructor
Veritas Prep

Post helpful? Mosey your cursor on over to that Thank button and click, please! I will bake you an imaginary cake.

Legendary Member
Posts: 1448
Joined: Tue May 17, 2011 9:55 am
Location: India
Thanked: 375 times
Followed by:53 members

by Frankenstein » Wed Jun 01, 2011 9:49 am
Ashley@VeritasPrep wrote:Hey guys,

Sorry for the delay in response! Yeah, this type of problem is probably one that everyone (myself very much included!) struggles with. I don't personally know of a specific resource that consolidates a whole bunch of problems like this all in one place (though others may -- others, feel free to weigh in!), but most problems that deal with factors/divisibility/multiples will hone some element of this type of thinking.

Here is a challenging one (I'm just making this up) to start you off:

If m is a positive integer, does 24 divide m?
(1) 54 divides m^2.
(2) 32 divides m^2.

See what you come up with!
Hi,
From(1):if m^2=324(54*6), m=18 Not divisible by 24
if m^2=324*16(54*6*16), m=72 Divisible by 24
Insufficient
From(1):if m^2=64, m=8 Not divisible by 24
if m^2=64*9, m=24 Divisible by 24
Insufficient
Both(1)1&(2) m^2 is divisible by 54(2.3^3) and 32(2^5)
So m^2 is divisible by LCM(54,32) = 2^5.3^3
So m^2 = 2^6.3^4.p^2, where p is any positive integer
So, m= 2^3.3^2.p = 72p which is always divisible by 24
Sufficient

Hence, C
Cheers!

Things are not what they appear to be... nor are they otherwise

User avatar
Legendary Member
Posts: 1309
Joined: Mon Apr 04, 2011 5:34 am
Location: India
Thanked: 310 times
Followed by:123 members
GMAT Score:750

by cans » Wed Jun 01, 2011 4:20 pm
Ashley@VeritasPrep wrote:If m is a positive integer, does 24 divide m?
(1) 54 divides m^2.
(2) 32 divides m^2.

See what you come up with!
a)54 divides m^2
54=2*3^3 thus m^2 should be multiple of 2^2*3^4 (as m is an integer)
thus m is multiple of 2*3^2 = 18
now m=18 satisfies condition a but is not divisible by 24
m=72(=18*4) satisfies condition a but is divisible by 24.
Insufficient.

b)32 divides m^2
32=2^5
thus m^2 is divisible by 2^6 or m is multiple of 2^3 =8
now m=8 satisfies condition b, but not divisible by 24
m=24 satisfies condition b, but is divisible by 24
Insufficient

a&b together) 54 and 32 divide m^2
lcm of 54,32 = 2^5*3^3
thus m^2 is a multiple of 2^6*3^4
or m is a multiple of 2^3*3^2 = 72
as m is multiple of 72, it is also multiple of 24 (72=24*3)
Thus sufficient
IMO C

Senior | Next Rank: 100 Posts
Posts: 97
Joined: Sun May 15, 2011 9:19 am
Thanked: 18 times
Followed by:1 members

by SoCan » Wed Jun 01, 2011 4:50 pm
Ashley@VeritasPrep wrote: If m is a positive integer, does 24 divide m?
(1) 54 divides m^2.
(2) 32 divides m^2.

See what you come up with!
This has been answered a couple of times, but I'll restate things a bit.

If 24 divides m, then m must contain at least the same prime factors as 24. Prime factors of 24 are 2^3, 3, so m must contain at least three 2s and one 3.

1) 54's prime factors are 3^3, 2. Since m^2 is a squared integer, there must be even number of each prime factors, so m^2 must contain at least 3^4, 2^2, meaning m contains 3^2 and 2. This satisfies the condition for at least one 3, but not at least three 2s. It's possible that it contains another two 2s, but we don't know so this is insufficient.

2) 32's prime factors are 2^5. Since Since m^2 is a squared integer, there must be even number of each prime factors, so m^2 must contain at least 2^6, meaning m contains 2^3. This satisfies the condition for at least three 3s, but not at least one 3. It's possible that it contains at least one 3, but we don't know so this is insufficient.

Combined: we know that m contains at least three 2s and two 3s. Since it needed three 2s and one 3 to be divisible by 24, we know that it is indeed divisible, so sufficient.

Junior | Next Rank: 30 Posts
Posts: 22
Joined: Sun Nov 21, 2010 6:21 pm

by zachlebo » Wed Jun 01, 2011 8:04 pm
hi,
what do you mean that a squared integer has an even number of prime factors?

User avatar
GMAT Instructor
Posts: 199
Joined: Tue May 17, 2011 6:06 am
Location: Cambridge, MA
Thanked: 192 times
Followed by:121 members
GMAT Score:780

by Ashley@VeritasPrep » Wed Jun 01, 2011 8:30 pm
Hi there,

Good solutions, everyone! Right on.

Re:
what do you mean that a squared integer has an even number of prime factors?
the intended meaning is that a perfect square itself (not the integer you square to get there -- in case the wording is confusing) has an even number of prime factors. This is simply because you could break that perfect square (we'll call it x^2) down initially into x times x, and each of those two x's would shoot down an identical set of prime factors. So for every prime factor you had coming out of one of the x's, you'd have a duplicate of that prime factor coming out of the other x. So since every prime factor will get a duplicate, in total we'll definitely have an even number of prime factors.

WORD OF CAUTION! Even though the above is (a) totally true and (b) quite helpful to know, make super-sure you remember the word "prime" in that statement! Because if we were to drop that word, it'd be wrong -- since in fact, perfect squares are precisely the ONLY numbers that have an odd TOTAL number of factors, while all non-perfect-squares have an even total number of factors!
Ashley Newman-Owens
GMAT Instructor
Veritas Prep

Post helpful? Mosey your cursor on over to that Thank button and click, please! I will bake you an imaginary cake.

User avatar
Legendary Member
Posts: 1309
Joined: Mon Apr 04, 2011 5:34 am
Location: India
Thanked: 310 times
Followed by:123 members
GMAT Score:750

by cans » Wed Jun 01, 2011 8:37 pm
zachlebo wrote:hi,
what do you mean that a squared integer has an even number of prime factors?
the prime factors of a squared integer should have even powers
say 36 is square of 6 and 36 = 2^2*3^2
Notice the power of 2 & 3. both are 2 which is even.
now lets say 49, 49=7^2 (again power of 7 is 2 which is even)
suppose we have a no. 32 = 2^5. this is not square of integer because when you take square root of this number, root(2^5), you will get 4*root(2) which is not an integer.
This is because power of 2, which is 5, is not even.

User avatar
GMAT Instructor
Posts: 199
Joined: Tue May 17, 2011 6:06 am
Location: Cambridge, MA
Thanked: 192 times
Followed by:121 members
GMAT Score:780

by Ashley@VeritasPrep » Wed Jun 08, 2011 9:16 am
Also check out problem #142 in the Problem Solving section of the OG! Similar skill tested.
Ashley Newman-Owens
GMAT Instructor
Veritas Prep

Post helpful? Mosey your cursor on over to that Thank button and click, please! I will bake you an imaginary cake.

GMAT/MBA Expert

User avatar
GMAT Instructor
Posts: 2621
Joined: Mon Jun 02, 2008 3:17 am
Location: Montreal
Thanked: 1090 times
Followed by:355 members
GMAT Score:780

by Ian Stewart » Wed Jun 08, 2011 12:37 pm
Ashley@VeritasPrep wrote: the intended meaning is that a perfect square itself (not the integer you square to get there -- in case the wording is confusing) has an even number of prime factors.
I think the language here is potentially confusing, since many questions ask test takers to count distinct prime factors. If I ask, for example, how many divisors 9 has, the answer is three: 1, 3 and 9. There is no reason to count the '3' twice, even if 3*3 = 9. Similarly, if I ask how many prime divisors 9 has, the answer should be one: the only prime which is a divisor of 9 is 3. There is no logical reason to count the 3 twice, even if 3^2 = 9. That is, when number theorists talk about how many prime divisors a number has, they normally take that to mean how many *distinct* prime divisors that number has.

A perfect square can have any number of distinct prime divisors. For example, 9 = 3^2 has just one distinct prime divisor, 3, whereas 36 = (2^2)(3^2) has two distinct prime divisors, 2 and 3. However, if you write the prime factorization of a perfect square using exponents, grouping the same primes together, then *all* of the exponents will be even numbers. Thus (3^6)(7^4) is a perfect square (since it is the square of (3^3)(7^2)), while (3^5)(7^4) is not a perfect square, since one of our exponents is odd.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com

ianstewartgmat.com

User avatar
GMAT Instructor
Posts: 199
Joined: Tue May 17, 2011 6:06 am
Location: Cambridge, MA
Thanked: 192 times
Followed by:121 members
GMAT Score:780

by Ashley@VeritasPrep » Wed Jun 08, 2011 7:08 pm
True, good clarification. That the prime factors of any perfect square will come in couples is what I meant to be communicating.
Ashley Newman-Owens
GMAT Instructor
Veritas Prep

Post helpful? Mosey your cursor on over to that Thank button and click, please! I will bake you an imaginary cake.