gmatt1476 wrote:
Let S be the set of all positive integers having at most 4 digits and such that each of the digits is 0 or 1. What is the greatest prime factor of the sum of all the numbers in S ?
A. 11
B. 19
C. 37
D. 59
E. 101
PS41661.01
GIVEN:- S is a set of ALL positive integers having at most 4 digits.
- Set S can have 1-digit, 2-digit, 3-digit, and 4-digit integers.
- Each digit of an integer in set S is either 0 or 1.
TO FIND: - The greatest prime factor of the sum of all integers in S.
- Say, the sum of all integers of set S is ‘X’. Then, we need to find the greatest prime factor of X.
APPROACH: Based on the
CONSTRAINT that each digit can be either 0 or 1, first let us find all the integers in S (that is, all 1-digit, 2-digit, 3-digit, and 4-digit integers that can be formed using 0 and 1 as digits). We will then proceed to find
X, followed by its prime factors.
WORKING: Single digit integers in S:As the only possibilities for the digits of any integer in S are 0 and 1, the only
possible single-digit integers in set S are
0 and 1 themselves.
- BUT the question also states that set S has positive integers. Hence, 0 is also not a possibility. Thus, the only single-digit integer in set S is 1.
IMPORTANT: Since our goal is to find the sum of all integers in S, it will be very helpful to have the same number of digits in all the integers. We will rewrite each integer we get using 4 digits, filling 0s when we do not have 4 digits already. (You will see how simple addition becomes once we get to it – Hang on and trust the process! 😊)
So, 1 can be rewritten this way:
2-digits integers in S: Possible digits for ten’s place are 0 and 1.
Observe: Can a 2-digit number have 0 at its tens place?
NO! Because 01 is again just the single-digit number 1!
- So, to have a 2-digit integer, the tens digit can be filled in only ONE way: Ten’s digit = 1.
- Now, for the one’s place, both 0 and 1 are possible. So, one’s place can be filled in TWO ways.
Therefore, total number of 2-digit integers in S = 1 × 2 = 2. These are
10 and 11.
And again, the 4-digit representation of both these numbers are:
3-digits integers in S: Possible digits for hundred’s place are 0 and 1. But again, just as we saw in the 2-digit case, the hundred’s digit cannot be 0.
Hence, the hundred’s place can be filled in only
ONE way: Hundred’s digit = 1.
Then, the remaining two places, ten’s place, and one’s place,
EACH can be filled in two ways (by 0 or 1). Therefore, total number of 3-digits integers in S = 1 × 2 × 2 = 4. Check out the possibilities below:
So, the 3-digit integers are 100, 101, 110, 111. And again, we’re going to take these to their 4-digit representations. Here we go:
4-digits integers in S: Same analysis as above will confirm that the only possible digit for thousand’s place is 1. And the remaining three places, hundred’s place, ten’s place, and one’s place,
each can be filled in two ways (by 0 or 1). Therefore, total number of integers = 1 × 2 × 2 × 2 = 8. Check out all possibilities below:
Now, we can easily see that the 4-digit integers are 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. Since they are already 4-digit integers, we do not need any extra work to write them in their 4-digit representations. Let me just re-write them just as I did for all above integers:
Sum of all integers = X: In total, set S has a total of 15 integers. That is,
Observe that at every place, the digit ‘0’ comes 7 times (marked in different colors at each place) and ‘1’ comes 8 times.
- Note: If we had included 0 as a single-digit integer, then we would have had 16 total numbers in S. Then, the number of 0s and the number of 1s at every place would have been 8 each. That is, you would have had half 1s and for half 0s at every place.
For our situation, when you try to add the digits at each place, you get:
7 times (0) + 8 times (1) = 8. So, the digit at each place in the sum, X, is 8.
Required prime factored form of X: The prime factored form of X: 8888 = \(2^3\) × 11 × 101.
So, the GREATEST PRIME FACTOR of X is 101.
Correct answer: OPTION E.
Hope this helps!
Best,
Aditi Gupta
Quant expert,
e-GMAT