CAT Online Class - Interesting one from Number Systems

Question
Actually, this is not a CAT preparation question. This is way tougher than what one can expect to see in CAT. I saw it on some Olympiad paper. But this is a wonderful question to think about one very interesting property. Anyway, let us get to the question -

A six-digit number has digits 'abcabd', where a, b, c, d take values from 0 to 9. Further we know that d = c + 1 and that this number is a perfect square. Find the number. If there is more than one number possible, find all such numbers.

Answer
183184, 328329, 528529, 715716

Explanation
This is a fabulous question. It bears repeating that this is far far tougher than what we are likely to see in CAT. Nevertheless we will look at this question in order to discuss one key idea.

Now, 'abcabd' is a perfect square. So, say, 'abcabd' = x^2
Now, 'abcabd' = 'abcabc' + 1. So, 'abcabc' = x^2 - 1

After this, we are halfway there to the solution

'abcabc' = (x +1) (x - 1)

Now, 'abcabc' = 'abc' * 1001. Or, 'abcabc' = 'abc' * 1001. This is the key idea that is very vital in a bunch of questions.

'abc' * 1001 = 'abc * 7 * 11 * 13 = (x - 1) (x + 1)

So, between x -1 and x + 1, we need to account for 7, 11 and 13 as factors. Wherever this works, we are through. Now, x - 1 or x + 1, either number alone cannot be a multiple of 7, 11 and 13. So, one of these two should be a multiple of one of the three primes and the other should be a multiple of the other two.

So, of the two numbers one can be a multiple of 7 and the other 143. or,
one can be a multiple of 11 and the other 91. or,
one can be a multiple of 13 and the other 77,

After this we are down to trial and error; but a very scientific form of trial and error.

Let us say, we are picking two numbers such that one is a multiple of 7 and the other of 143. Since 143 is the far larger number, it helps to look for multiples of  143 and see if we can spot the scenario where the other number is a multiple of 7.

If one number were 143, the other would have to  be 145 or 141. Neither is a multiple of 7. This does not work.

If one number were 286, the other would have to  be 284 or 288. Neither is a multiple of 7. This does not work either.

If one number were 429 (143 * 3), the other would have to  be 427 or 429. 427 is a multiple of 7. Houston, we have an answer!

(x -1) * (x + 1) = 427 * 429 works. 427 * 429 = 183183. Or, 183184 is a perfect square. 428 * 428.

Now, all we need to do is check out all other variants. But having said that, even this can be a very time-consuming process. So, let us see if we can fine-tune this a touch. If one number is a multiple of 143, the other number should be a multiple of 7. So, the first number  + 2 or first number -2 should be a multiple of 7. If we say the first number were k, then either k + 2 or k - 2 should be a multiple of 7. In that case, we are through. or, k divided by 7 should give us a remainder of 2 or 5.

Now, 143 divided by 7 gives us a remainder of 3. This is why this does not work

2 * 143 divided by 7 will give us a remainder of 6. This does not work either
3 * 143 divided by 7 will give us a remainder of 9, which is same as 2. This works. This is what gave us the solution 183184
4 * 193 gives us a remainder of 12, which is same as 5. This should also work. Let us check this out. 4 * 143 = 572. 574 is a multiple of 7. Or, 572 * 574 will be a multiple of 1001.
572 * 574 = 328328. or, 328329 = 573 *573. We have got our second possibility!!

183184 and 328329 are both perfect squares.

Now, let us move to 5 * 143. This divided by 7 gives us a remainder of 15, which is same as 1. This does not work either

Let us move to 6 * 143. This divided by 7 gives us a remainder of 18, which is same as 4. This does not work either

7 * 143 = 1001. That is a 4-digit number, so we do not have to worry about this.

So, we have got two solutions so far. With the numbers being divided as product of 143 and of 7. Let us move to the combination of the numbers being broken as product of 91 and 11.

Now, let us go directly to the remainder approach. 91 divided by 11 gives us a remainder of 3. We need to find some multiple of 91 that on division by 11 gives us a remainder of either 2 or 9. (Why? scroll up to see this. We are looking for numbers that differ by 2 which between them account for all factors of 1001)

1 * 91 divided by 11 will give us a remainder of 3. This does not work.
2 * 91 divided by 11 will give us a remainder of 6. This does not work.
3 * 91 divided by 11 will give us a remainder of 9. This should work. Let us check this out. 273 is a multiple of 91, 275 is a multiple of 11. 273 * 275 should be a multiple of 1001. 273 * 275 = 75075. 75076 is 274 * 274. But this does not count because it has only 5 digits. Close, but no cigar. Let us take this further

4 * 91 divided by 11 will give us a remainder of 12, which is same as 1 This does not work.
5 * 91 divided by 11 will give us a remainder of 15, which is same as 4 This does not work either
6 * 91 divided by 11 will give us a remainder of 18, which is same as 7 This does not work either
7 * 91 divided by 11 will give us a remainder of 21, which is same as 10 This does not work either
8 * 91 divided by 11 will give us a remainder of 24, which is same as 2. Hello, do we have our third number here?!

8 * 91 = 728. 726 is a multiple of 11. 728 * 726 should be a multiple of 1001. 726 * 728 = 528528. 528529 = 727*727. So, our third number is 528529.

Let us go further, but quicker from now on.

9 * 91 divided by 11 will give us a remainder of 27, which is same as 5 This does not work.
10 * 91 divided by 11 will give us a remainder of 30, which is same as 8 This does not work either.

We do not need to worry about 11 * 91 as that is 1001.

Now, let us move on to numbers that break as 77p * 13q.

We need a multiple of 77 that when divided by 13 gives a remainder of either +2 or + 11. 77 divided by 13 gives a remainder of 12, or -1.

77 * 2, on division by 13 will give us a remainder of -2. This should work. But this will be a waste of time as it will result in a 5-digit number.

So, let us evaluate 77 * 3. This gives a remainder of -3. Not good enough.
Straight away, we can sense that the next number that will work for us is 77 * 11, where we get a remainder of -11, which is nothing but + 2.

77 * 11 = 847. 845 is a multiple of 13. 845 *847 is a multiple of 1001. 847 * 845 = 715715. 846 *846 = 715716 is our fourth number. 

No other possibility exists.

There are 4 possible numbers - 183184, 328329, 528529 and 715716. Fantabulous question to nail down the fact that 1001 = 7 * 11 * 13. 

Since you have been brilliant and diligent enough to get through this far to the solution, I am going to leave you with another nugget. 'abcdabcd' = 'abcd' * 10001.

This 10001 is not prime. It is a product of two primes. Which two? It is not for nothing that we at 2iim say CAT preparation can be fun.

Again, for the nth time, let me reiterate that the above question is way tougher than what we will find in CAT. If you want questions (lots of them) at or around CAT level, visit the questionbank.

CAT Number Systems - Fun question based on Armstrong numbers

Question

A 3-digit Armstrong number is a three-digit number where the number is equal to the sum of the cubes of the three digits. Give a few Armstrong numbers.

Explanation

To start with, be clear that CAT does not ask questions like these. You do not need to know what Armstrong number are; nor do you need to know how to get these to crack these exam. This is just a fun question to do some trial and error with.

The 3-digit Armstrong numbers are 153, 370, 371 and 407, obtained mostly by trial and error (although a lil scientifically)

CAT Number Theory - Interesting Question from Factorial

Question

How many trailing zeroes will be present in the base 12 representation of 55!?

Explanation

The question can be restated as follows - "What is the highest power of 12 that divides 55!"

Now, 12 = 2^2 * 3. So, a number that is a multiple of 2^2 and 3 will be a multiple of 12.

So, in order to find the highest power of 12 that divides 55!, we need to look at the highest powers of 2 and 3 that divide 55!. 

Successive division by 2 will give us the highest power of 2 that divides 55!:

55/2 = 27, 27/2 = 13, 13/2 = 6, 6/2 = 3, 3/2 = 1.

Highest power of 2 that divides 55! = 27 + 13 + 6 + 3 + 1 =  50

Successive division by 3 will give us the highest power of  3 that divides 55!:

55/3 = 18, 18/3 = 6, 6/3 = 2.

Highest power of 3 that divides 55! = 18 + 6 + 2 = 26. 

So, 55! is a multiple of 2^50 and 3^26. What is the highest power of 12 that will divide 55!. Or, what is the highest value n can take such that (2^2 * 3)^n is a factor of 55!

We haev 26 threes's; but we can accommodate 2^2 only 25 times. Or, 12^25 will be a factor of 55!, while 12^26 will not, since we need 52 2's for 12^26. We have only 50 2's. 

Thus 12^25 will divide 55! - there are 25 trailing zeros in base 12 representation of 55!.

Inequalities - Interesting Question

Question
How many positive integer values can x take that satisfy the inequality (x - 8) (x - 10) (x - 12).......(x - 100) < 0?

Answer: 30

Explanation

Let us try out a few values to see if that gives us anything.

When x = 8, 10, 12, ....100 this goes to zero. So, these cannot be counted.
When x = 101, 102 or beyond, all the terms are positive, so the product will be positive. 

So, straight-away we are down to numbers 1, 2, 3, ...7 and then odd numbers from there to 99.

Let us substitute x =1,

All the individual terms are negative. There are totally 47 terms in this list (How? Figure that out). Product of 47 negative terms will be negative. So, x = 1 works. So, will x =2, 3, 4, 5, 6, and 7.

Remember, product of an odd number of negative terms is negative; product of even number of negative terms is positive. Now, this idea sets up the rest of the question.

When x = 9, there is one positive terms and 46 negative terms. So, the product will be positive. 
When x = 11, there are two positive terms and 45 negative terms. So, the product will be negative. 
When x = 13, there are three positive terms and 44 negative terms. So, the product will be positive. 

and so on.

Essentially, alternate odd numbers need to be counted, starting from 11.

So, the numbers that will work for this inequality are 1, 2, 3, 4, 5, 6, 7...and then 11, 15, 19, 23, 27, 31,..... and so.

What will be the last term on this list? 
99, because when x = 99, there are 46 positive terms and 1 negative term. 

So, we need to figure out how many terms are there in the list 11, 15, 19,....99. These can be written as 
4 * 2 + 3, 
4 * 3 + 3, 
4 * 4 + 3
4 * 5 + 3
4 * 6 + 3
...
4 * 24 + 3

A set of 23 terms. So, total number of values = 23 + 7 = 30. 30 positive integer values of x exist satisfying the condition. 

Number Theory Questions and Solutions

Question:

How many numbers with distinct digits are possible product of whose digits is 28?

A.  6

B.  4

C.  8

D.  12

Correct Answer: (C)

Explanation:

Two digit numbers; The two digits can be 4 and 7: Two possibilities 47 and 74

Three-digit numbers: The three digits can be 1, 4 and 7: 3! Or 6 possibilities.

We cannot have three digits as (2, 2, 7) as the digits have to be distinct.

We cannot have numbers with 4 digits or more without repeating the digits.

So, there are totally 8 numbers.

Answer Choice (C)

Difficulty Level 2

Number Theory

Question

What is the remainder when (13¹⁰⁰ +1 7¹⁰⁰) is divided by 25?

A. 2

B. 0

C. 15

D. 8

Correct Answer: Choice (A)

Explanation:

What is the remainder when (13¹⁰⁰ +1 7¹⁰⁰) is divided by 25?

(13¹⁰⁰ +1 7¹⁰⁰) = (15 – 2)¹⁰⁰ + (15 + 2)¹⁰⁰

Now 5² = 25, So, any term that has 5² or any higher power of 5 will be a multiple of 25. So, for the above question, for computing remainder, we need to think about only the terms with 15⁰ or 15¹.

(15 – 2)¹⁰⁰ + (15 + 2)¹⁰⁰

Coefficient of 15⁰ = (-2)¹⁰⁰ + 2¹⁰⁰

Coefficient of 15¹ = ¹⁰⁰C₁ * 15¹* (-2)⁹⁹ + ¹⁰⁰C₁ * 15¹* (-2)⁹⁹ . These two terms cancel each other.So, the sum is 0.

Remainder is nothing but (-2)¹⁰⁰ + 2¹⁰⁰ = (2)¹⁰⁰ + 2¹⁰⁰

2¹⁰¹

Remainder of dividing 2¹ by 25 = 2

Remainder of dividing 2² by 25 = 4

Remainder of dividing 2³ by 25 = 8

Remainder of dividing 2⁴ by 25 = 16

Remainder of dividing 2⁵ by 25 = 32 = 7

Remainder of dividing 2¹⁰ by 25 = 7²  = 49 = -1

Remainder of dividing 22⁰ by 25 = (-1)²  = 1

Remainder of dividing 2¹⁰¹ by 25 = Remainder of dividing 2¹⁰⁰ by 25 * Remainder of dividing 2¹ by 25 = 1 * 2 = 2

CAT Number Theory - Interesting question

This is an interesting question from Number Theory. Slightly unconventional, but interesting nevertheless.

Question

The sum of the factors of a number is 124. What is the number?

Correct Answer

Number could be 48 or 75

Explanatory Answer
This video gives the solution for this question. Given below the video is the explanation (in words)

Any number of the form p^aq^br^c will have (a+1) (b+1)(c+1) factors, where p, q, r are prime. (This is a very important idea)

For any number N of the form p^aq^br^c, the sum of the factors will be (1 + p¹ + p² + p³+ …+ p^a) (1 + q¹ + q² + q³+ …+ q^b) (1 + r¹ + r² + r³+ …+ r^c).

Sum of factors of number N is 124. 124 can be factorized as 2² * 31. It can be written as 4 * 31, or 2 * 62 or 1 * 124.

2 cannot be written as (1 + p¹ + p² …p^a) for any value of p.

4 can be written as (1 + 3)

So, we need to see if 31 can be written in that form.

The interesting bit here is that 31 can be written in two different ways

31 = (1 + 2¹ + 2²+ 2³ + 2⁴)

31 = ( 1 + 5 + 5²)

Or, the number N can be 3 * 2⁴ or 3 * 5². Or N can be 48 or 75.