Using Combinatorics to ‘count’ Divisors on the GMAT

Avi Gutman —  October 17, 2012 — 12 Comments

Are you ready for a challenge? Try to solve the following question in under two minutes:

How many different positive divisors does the number 147,000 have?

If you feel like two minutes are not nearly enough to solve the problem, you’re not alone. Even the most seasoned GMAT veterans might find the problem challenging, as it requires a deep level of understanding of two mathematical concepts:gmat grover Divisibility and Combinatorics (just a fancy word for ˜counting’).

If I replaced the number 147,000 with the number 24, many more people would be able to come up with an answer:

You could just pair up the divisors (factors) and count them. Start with the extremes (1×24) and work your way in:

1×24

2×12

3×8

4×6

A quick count will show the number 24 has exactly 8 different positive divisors.

The number 147,000 will have many more positive divisors “ too many to count This is a strong indication that we will need to use combinatorics.

Divisibility: Any positive integer in the universe can be expressed as the product of prime numbers.

A few examples:

gmat combinatorics

The number 24 gmat 24 factors is comprised of three factors of 2 and one factor of 3.

We should be able to ˜build’ any divisor of 24 using some combination of those prime factors; for example, we could choose to use none of them. What do you get if you use none of those prime factors?

Is 1 a divisor of 24? Absolutely!

What if we choose to use all of the prime factors that we have at our disposal?

Is 24 a divisor of 24? Of course!

I can use zero, one, two, or three factors of 2, and for each of those options, I can choose to use either zero or one factor of 3.

Combinatorics: When faced with several choices that are independent of each other, the total number of combinations will be the product of the number of choices in each decision point. For example, if you can choose among 3 appetizers, 2 mains, and 4 desserts when ˜building’ your 3-course meal, the number of different meals you could construct is 3 * 2 * 4 = 24

Intuitively, for each appetizer you could choose (out of 3), there are still 2 options for your main, and for each of those there are still 4 options for your dessert. As a rule of thumb, if you’re using the word each you should multiply the options.

Back to the number 24 allow me to repeat my last point here for your convenience: I can use zero, one, two, or three factors of 2 (four options total), and for each of those options, I can choose to use either zero or one factor of 3 (two options total).

Using combinatorics, we can now say there are exactly 4 * 2 =8 different positive divisors for the number 24.

Try to solve the original question again at this point, before you continue to read my solution.

.

.

.

gmat combinatorics

gmat divisors

There are four options for the number of 2 we will use (zero, one, two, or three), two options for the number of 3, four options for the number of 5, and three options for the number of 7.

In total, the answer to the original question is: gmat math

Is it just me, or is there a pattern here? You can just add 1 to each of the exponents of the prime numbers and then multiply them all together to get the total number of different positive divisors of any number!

This is a cool rule/formula to memorize, but as you guys know by now “ memorizing little tricks and formulae will only get you so far on the GMAT. In order to crush it you really have to understand why these formulae work, and that was my goal with this blog post Let me know in the comments whether you feel like you have a deeper level of understanding now!

Takeaways:

  1. No matter how complex the problem you’re facing is, you can always simplify it by picking a nicer number (e.g. 24 rather than 147,000).
  2. Any positive integer in the universe can be expressed as the product of prime numbers.
  3. When faced with several choices that are independent of each other, the total number of combinations will be the product of the number of choices in each decision point.

Avi Gutman

Posts

Avi Gutman earned his MBA at NYU’s Stern School of Business. While at Stern, he took on the position of teaching fellow and taught his classmates several courses including Operations, Foundations of Finance, and New Venture Financing. Avi has been teaching test prep since 2004 and has worked for several different companies before joining Manhattan GMAT.

12 responses to Using Combinatorics to ‘count’ Divisors on the GMAT

  1. Great article, Avi! I love learning to simplify problems and find this skill can be applied to many other areas in life. Keep it coming!

  2. Explained so well, inspired me to delve deeper into math concepts

  3. This is really an important concept and you have explained it well…Can you please write something on Probability especially for those problems where we need to decide whether to add or multiply the probabilities of individual occurances.

  4. Hey folks, thanks for the compliments – I’m glad you found this article useful!
    Amar, we will learn about probability this Wednesday in class, but I might write an article about it as well in the near future ;)
    Cheers,
    Avi

  5. the lord i really like your model

  6. Thanks for the comment. I just got online for the first time 2 monthsago. I am an addict, but enjoying the new found discovery. Thanks again.

  7. Im not sure why but this site is loading extremely slow for me. Is anyone else having this problem or is it a issue on my end? Ill check back later and see if the problem still exists.

  8. Things have unquestionably advanced in the past month or two regarding eReaders. I remember only a short time back that everybody was speaking about the Sony eReader but since then we now have seen the likes of Amazon introduce Kindle devices and swiftly followed by the ipad from apple. The growth of the gadget is in my mind fueled through the development of the e-book products themselves these days there are several thousand quality books on the market that are suitable for a good number of brands. I finished up purchasing a Kindle machine considering the price of the apple ipads at present are beyond reach, like i said previously, Amazon have grabbed this market by way of the neck and dramatically decreased their price tags in order to be competitive, we as shoppers need to take advantage dont we!

  9. I love the game Dark Messiah of Might and Magic: Elements ,what is your favorite game?. I have a xbox 360

  10. Thank you for an additional fantastic blog.Where else could I get this sort of details written in such an incite full way? I have a project that I am just now functioning on, and i am certain this can aid me a lot..and Ive been trying to find this kind of information and facts since from few days.Thanks!!!!!

  11. Nice and Easy… I love this shortcut, resourceful thinking

Leave a Reply