Tuesday, March 1, 2016

Combinatorics and LCMs

Working through the problems in Niven's book on combinatorics, I came across the following one that cleverly introduces least-common-multiples without saying any of those words.  The book asks the following question:

How many numbers that are evenly divisible by 11 exist between 1 and 2000?  How many that aren't also evenly divisible by 3?  How many numbers that are evenly divisible by 6, but not by 4 exist between 1 and 2000?

The hastily scribbled answer can be seen below, with each of the answers boxed in succession down the screen.

By simply dividing 2000 by 11, we find out how many integers between 1 and 2000 are evenly divisible by 11.  In other words, we ask how many multiples of 11 can fit between 1 and 2000.  When we want to eliminate the multiples of 3, that's when the least common multiple comes in.  We already have the answer for all numbers divisible by 11, but how to eliminate those also divisible by 3?  By first asking what number divisible by 11 are also divisible by three, we arrive at an answer.  The first number divisible by both is 33, or 3 X 11.  Then next is 66, and then 99, and so on, (if you're working it out by hand, it's easier to count by 11's than 3's).  As it turns out, only multiples of the least common multiple (LCM) of 3 and 11, (33), are divisible by both 3 and 11.  Now, we just need to figure out how many copies of numbers divisible by 33 are between 1 and 2000, and then subtract that number from the total number of integers divisible by 11 we calculated earlier to get the answer to the 'divisible by 11, but not 3' question.

The divisible by 6, but not 4 questions is similar.  In this case, the lowest common multiple of 6 and 4, in other words, the smallest number they'll both divide evenly, is 12.  By removing all the numbers divisible by 12 from 1 to 2000 from the count of integers between 1 and 2000 that are divisible by 6, we wind up with the answer to "How many integers between 1 and 2000 are divisible by 6, but not by 4?"


No comments: