A Number Theory PigeonHole Question

Question:
What is the least amount of numbers which is needed to be chosen from among the numbers 1, 2, 3 … 198, 199, 200 to ensure that either a multiple of 3 or 4 is chosen?

Solution

Consider the 200 hundred numbers as follows:

(i) How many numbers are multiples of 3 among them?

3(1) = 3
3(2) = 6
3(3) = 9
.
.
.
3(66) = 198

So, there are 66 multiples of 3 among these numbers

(ii) How many multiples of 4 are there among these numbers?

Consider similarly:

4(1) = 4
4(2) = 8
4(3) = 12
.
.
.
4(50) = 200

So, there are 50 multiples of 4 among these numbers

(iii) How many numbers occur on “both lists” in (i) & (ii)?

We have to count this because for any number which occurs in “both lists”, the “same” number is counted “twice” (overcounting has happened; we only need to count these numbers once & so we need to “subtract this overcounting accordingly”).

So, how do we determine which numbers occur on “both lists” previously?

Note that “any number” which occurs on “both lists” must be a “multiple” of “both 3 & 4”.

Since the LCM (least common multiple) of 3 and 4 is 12, it is equivalent to say that the “numbers” which occur on “both lists” are “every multiple of 12”.

So, how many “multiples” of 12 are there among these given numbers?

Consider likewise:

12(1) = 12
12(2) = 24
12(3) = 36
.
.
.
12(16) = 192

So, there are 16 multiples of 12 which occur on both lists.

Finally, we count:

How many numbers are “either multiples of 3 or 4” among the given numbers?

(number of multiples of 3) + (number of multiples of 4) – (number of multiples of 12)
= 66 + 50 – 16
= 100 numbers

We are given a total of 200 numbers (from 1 to 200).

Thus, the remaining (200 – 100) = 100 numbers are “not” multiples of 3 nor 4.

By the Pigeon Hole Principle (PHP), we need to choose at least (100 + 1) = 101 numbers to always ensure at least a multiple of 3 or 4 is chosen.

So,

Answer: 101