MathOratory - Quant notes - Set 2
IIM Lucknow | MathOratory
What is the number removed from 1!, 2!, 3!, ..., 200! such that the product of the remaining 199 numbers is a perfect square?
Before I share my approach, I'd like to say that I always prefer numbers over algebra. So my first attempt on these type of questions are always numerical. And it always works.
The identity that we have here is
1! * 2! *3! * 4! *…200!
Now, we are attempting to make this a perfect square. Few things worth pointing out right away:
- In a perfect square, if one part (in terms of factor) is a perfect square, the other part should also be a perfect square.
- Any factorial will have any lower factorial as its factor.
Now let's break our identity in the following pairs:
200!∗199! = 200 ∗ (199!)^2
198!∗197! = 198 ∗ (197!)^2
196!∗195! = 196 ∗ (195!)^2
2! ∗ 1! = 2 ∗ (1!)^2
If we multiply all of these, we get:
[(1!)^2 ∗ (3!)^2 ∗... (199!)^2] ∗ (2 ∗ 4 ∗ ... 200)
Now, the first part (in the box bracket) is definitely a perfect square, so the rest part must also be a perfect square.
Now, the second part is
2 ∗ 4 ∗ .. 200 = =2^100 ∗ 100!
out of which 2^100 is a perfect square.
So, we are left with 100!
As asked in the question, we should be removing one factorial and the product of the remaining factorials must be a perfect square. Thus (1! ∗ 2! ∗ 3! ∗ ...200!)/n! must be a perfect square.
Now, we already know that in the numerator, everything except 100! Is DEFINITELY a perfect square.
Thus in order to make the identity a perfect square, our aim should be to make 100!/n! a perfect square
Now, the highest prime number in 100! is 97, which occurs only once in 100! Thus we must remove the 97, in order to get a perfect square. So, the ’n’ must be at least 97.
If we divide 100!/97!, we are left with 98 * 99 * 100, which isn't a perfect square
If we divide 100!/98!, we are left with 99 * 100, which isn't a perfect square
If we divide 100!/99!, we are left with 100, which is a perfect square
If we divide 100!/100!, we are left with 1, which is a perfect square
Thus there are two possibilities: either we can remove 99! or 100!
Find the no. of numbers between 300 to 400, that are not divisible by 2, 3, 4 & 5?
First of all the constraint regarding 4 is redundant here. We are already looking for numbers which are not divisible by 2 and if a number is not divisible by 2, it can anyhow not be divisible by 4.
Rephrasing the question how many numbers between 300 and 400 are not divisible by 2, 3 and 5.
The easiest way to solve this question would be apply the concept of Euler’s number. Euler’s number of a number tells how many positive integers less than the number are also co prime to the number. In this case we are looking for numbers not divisible by 2, 3 or 5; so first let's multiply 2 * 3 * 5 = 30. Now, I'm not going into details of calculating euler’s (you may refer Wikipedia).
But simply put Euler’s number of 2 * 3 * 5 will be (2–1) * (3–1) * (5–1) = 8 [this is applicable in cases of pure products of primes only]
So, the Euler of 30 being 8 tells us that from 1–29 there are 8 numbers co-prime to 30; implying not divisible by 2, 3 or 5. And 30 can't be co-prime to 30, we can infer that 1–30 there are 8 numbers which are not divisible by 2,3,5
Extending the logic: Let ‘x’ be a number which isn't divisible by 2, then ‘x+30’ must also not be divisible by 2. Same logic applies for the divisors 3 & 5 as well. So, we can infer from 31–60 there should be another 8 numbers not div by 2,3,5. [Adding 30 to each number of the first set] . So, we can infer that in any group of 30 consecutive numbers, there will be exactly 8 numbers not divisible by 2,3,5 (8 being the Euler of 30)
Getting back to the question: we need to test between 300 & 400. There are 99 numbers between them. Out of them 3 groups of 30 will give us 3*8 numbers not divisible by 2,3,5.
We are left with 9 numbers. Now, as any 30 consecutive numbers will give us 8 numbers, we can eliminate the consecutive groups from higher end, and be left with the lowest 9 numbers
301, 302, … 309
Test these separately … Even numbers eliminated … 303, 309 eliminated (multiples of 3) …. 305 eliminated ( multiple of 5)
Left with 2 more numbers : 301, 307
So we have a total of 3 * 8 + 2 = 26 numbers in this range not divisible by 2, 3, 5
How many 3 digit numbers have all their digits in an ascending order?
The easiest way to look at this question would be look back into the basics of counting. People often tend to take cases and what not to over complicate a problem at hand.
But always remember the few basic principles of counting:
Corresponding cases get multiplied, different cases get added.
Arrangement = Selection * Ordering
That’s it. No more basics.
In this question, let's use point number 2
Arrangement = Selection * Ordering
Let's first select the digits. But before we do, let us understand whether the digit 0 would be required or not. We cannot have 0 in the leftmost position and as we require the digits in increasing order, we cannot use it in any other position as well. So, the digit 0 is not required at all.
So, we need to select 3 digits out of the remaining 9, which can be done in 9C3 ways
Now, how many ordering for a given selection. As, we have a fixed order that is “in increasing order”, for any selection of 3 digits we can order those digits in only 1 way, i.e. in increasing order.
So the number of arrangements = 9C3 * 1 = 9C3 ways = 84 ways
In how many ways can 5 persons at a time among 10 persons sit on a circular table?
First step in this question would be the selection part. We don't need all 10 people, we just need 5 out of them. This can be done in: 10C5 ways.
Once, the 5 people are selected, they can be seated in 4! ways around a circular table.
Remember: Arrangement = Selection * Ordering
So, the number of arrangements here will be 10C5 * 4!
PS: I hope you remember the number of ways of seating ’n’ people on a circular table is (n-1)!
This is because, till anyone is seating on it all the seats are symmetrical. So, the first person (whoever that is) can be seated in only 1 way.
In a group of 6 boys and 4 girls, four children are to be selected. In how many different ways can they be selected such that at least one boy should be there?
Simplest way to look at it is subtract those cases where no boys are selected.
We have 10 children in total. Selecting 4 of them (without any constraint) would be in 10C4 ways.
Out of these cases, selecting no boy would be basically selecting only girls, which can be done in 4C4 ways.
Thus, our answer would be 10C4 - 4C4 = 209 ways
How many integers between 1000 and 9999 have exactly one pair of equal digits, such as 4049 or 9902, but not 4449 or 4040?
So, basically you are looking for number of 4 digit numbers having exactly one digit repeated once. Or in other terms, one digit occurring twice and two other distinct digits.
First let us forget the implicit condition that the leftmost digit can't be 0. So, we take the following steps:
Select the digit that would be repeated. 10C1 = 10
Select the two places the repeated digit would take, 4C2 = 6
Occupy the remaining two places by two other digits, 9 * 8 = 72
So, these are 10 * 6 * 72 = 4320 possibilities
Now, let us subtract those cases where 0 is occupying the leftmost position. There are a further of two cases here.
'0' repeated: the other 0 takes one of the 3 remaining places (in 3 ways) and the remaining two places in 9 * 8= 72. So, total of 3 * 72=216 cases
Some other digit repeated: which digit, in 9C1 = 9, which two places in 3C2 = 3 ways. The remaining place in 8 ways. So, total of 9 * 3 * 8 = 216 cases
Take ke these two cases off, we have
4320 - 216 * 2 = 3888 possibilities
What is the sum of the coefficients of the polynomial [(x-1) ^2] × [(x-2) ^4] × [(x-3) ^6]?
If I have a certain polynomial P(x) = 3x^5 - 4x^4 + 12x^3 - 10x^2 + x -2
The sum of coefficients will be : 3-4+12-10+1-2
Notice that this is also same as P(1). So, simply substituting x =1 in the polynomial, we can have the sum of coefficients.
In our question, putting x=1, we have the sum of coefficients = 0
How many numbers are there from 1 to 1000 which are not divisible by the digits 2, 3 and 5?
A ) 166
B ) 266
C ) 375
D ) 366
Euler totient function for a natural number N, gives us the number of positive integers which are less than N and co-prime to N.
In this case we'll take a two step approach to get the answer. But understandings first. 2 * 3 * 5 = 30. And Euler of 30 is 1 * 2 * 4 = 8. So what does that mean ? It means that from 1 to 30, there are 8 numbers which are co-prime to 30, and hence not divisible by 2, 3 or 5. Now, if we take a certain number X which is not divisible by 2, X+30 must also be not divisible by 2. Same thing for 3&5. So, we can modify and say that from 31 to 60, there are another 8 numbers which are not divisible by 2, 3 or 5. Or, in short we can say that in any group of 30 consecutive numbers, there are 8 numbers which are not divisible by 2, 3 or 5.
Now, the second step. We have a group of consecutive 1000 numbers in our problem. So, we can select any 33 groups of consecutive 30 numbers and each group shall provide 8 numbers which are not divisible by 2, 3 or 5. So that's 33*8=264 numbers. And as we are dealing with any 33 groups: we can take the higher ones. So we have found there are 264 numbers in the higher 990 numbers which are not div by 2, 3 or 5. So, test the first 10 numbers separately. 1, 7 are the only two numbers that satisfy the criteria.
So, we have a total of 264 + 2 = 266 numbers
With options, we can arguably avoid the second step, if the options aren't very close to each other.
We'd again take the idea of Euler. But, in this case we are going to apply it over the whole group of 1000, instead of sub-groups of 30.
1000 * (1- 1/2) * (1- 1/3) * (1- 1/5) = 266.66
The only close option that we have here is 266
Reiterating on the fact that this is applicable only when the options aren't too close. Otherwise you've the first method. Which will always work for prime divisors.
What is the number of times the digit 8 will be written when listing the integers from 1 to 1000?
There's a simple way to solve this. Firstly, let us simplify the question. In other words, we need to find the number of 8s required to write numbers up to 3 digits.
If, we fix the units digit at 8 the hundreds and tens digit can be occupied in 10 * 10=100 ways
Similarly, when we fix 8 at the tens place, the remaining two places can be occupied in 10 * 10=100 ways. Same for fixing 8 at the hundreds place.
So, total number of 8s required = 3 * 100 = 300
How many numbers from 1 to 2000 are not divisible by 3, 8 and 9?
If a number is not divisible by 3, it can anyhow not be divisible by 9.
So, we need to find those numbers which are neither divisible by 3 nor by 8.
Here's the short process for the remaining part.
- First take the LCM of 3&8 = 24
- Divide 2000/24, quotient = 83, remainder = 8
- Calculate the Euler of 24 = 8
Euler tells us that for any consecutive 24 numbers, 8 numbers would be co-prime to 24. But we can have numbers of the form 8k+2, 8k+4, & 8k+6 which are not co-prime to 24 but isn't divisible by 8. In 8 consecutive numbers, there would be 3 such numbers(of the three forms discussed), out of which 1 has been counted as it will be a multiple of 3. Thus, in 24 consecutive numbers, there would be 3*2= 6 additional numbers.
So, we can conclude that in 24 consecutive numbers, 8+6 = 14 numbers which are not div by 3 and 8.
As understood by the step 2 above, in 83 whole groups, there would be a total of 83*14 = 1162 numbers.
Let us look at the remaining 8 numbers. We can take the lower 8 or higher 8 numbers.
1,2,4,5,7 are not divisible by 3 or 8.
So total of 1162+5= 1167 numbers