Last Non Zero Digit Of a factorial

This is an oft repeated concept in different examinations but if you can grasp the following algorithm solving problems is a one min task

Concept

Lets say D(N) denotes the last non zero digit of factorial, then the algo says

D(N)=4*D[N/5]*D(Unit digit of N)[If tens digit of N is odd]

D(N)=6*D[N/5]*D(Unit digit of N)[If tens digit of N is even]; Where [N/5] is greatest Integer Function

#Problem 18

Find the last non zero digit of 26!*33!.

Solution Scheme and Approach

D(26)=6*D[26/5]*D(6)=6*D(5)*D(6)=6*2*2=4[D(5) means last non zero digit of 5!=120 which is 2, same for D(6)]

D(33)=4*D[33/5]*D(3)=4*D(6)*D(3)=4*2*6=8

Hence last non aero digit of 26!*33!=4*8=2

Remember

D(1)=1 D(2)=2 D(3)=6 D(4)=4 D(5)=2 D(6)=2 D(7)=4 D(8)=2 D(9)=8

Now solve:

(1)Last Non Zero Digit of 99!*26!.

(2)How many zeros are at the end of 13!+14!+15!+16!+17!+18!

After One Year

#Problem 17

If a,b,c,d are positive real numbers then find a possible value of a/(a+b+d)+ b/(b+c+a) + c/(b+c+d) + d/(a+c+d)

(a)11/5 (b)17/3 (c)2 (d)11/9

Solution Scheme And Approach:

a/(a+b+d)+ b/(b+c+a) + c/(b+c+d) + d/(a+c+d)>a/(a+b+d+c)+ b/(b+c+a+d) + c/(b+c+d+a) + d/(a+c+d+b)=1

a/(a+b+d)+ b/(b+c+a) + c/(b+c+d) + d/(a+c+d)<a/(a+b)+ b/(a+b)+ c/(c+d)+ d/(c+d) =2

Hence the range of the expression is (1,2)

Only option (d) suffice the condition.

Digital root

^{#Problem 16
Prove any perfect number ,except 6, has digital root 1.}  

^{Solution scheme and approach:}

^{We already know that what is digital root(look under concept of number theory) and we also learned that dividing any number by 9 we get digital root.} 

^{Let, the number is}  

^dk^dk-1^dk-2^…….d2^d1

^Now,

^dk^dk-1^dk-2^…….d2 ^d₁                                                                                                                          ^{= d}k ^{*10^(k-1)+ d}k-1^{*10^(k-2)+d}k-2^{*10^(k-3)…….d}2^{*10 + d}1^{(mod 9)                                            =d}k ^+dk-1^+dk-2^…….+d2^+d1^{(mod 9) [As 10^k=1(mod9)]}                                                                                                                                       All perfect numbers can be written as 2^p-1(2^p-1) [Where p is a prime number]                  for p=3, 2^p-1(2^p-1)=28 which is a perfect square and 28=1(mod9)..(i)                                                                                                                          for p>3, we can write p=6k+1 or p=6k+5                                                                      Case 1: p=6k+1

As 2^6k=1(mod 9) and 2^6k+1-1=1(mod 9) we can write,                                                              

2^6k(2^6k+1-1) =1(mod 9)….(ii)

Case 2: p=6k+5

As 2^6k+4= 2⁴(mod 9)=7(mod 9) and 2^6k+5-1=2⁵-1(mod 9)= 4 we can write,

2^6k+4(2^6k+5-1) =7*4(mod 9)=1(mod 9)……….(iii)

From (i),(ii) and (iii) we can conclude any perfect number ,without 6, will be having digital root 1.(Q.E.D.)

Breaking a long overdue

#Problem 15
Find the total number of solutions of | [x] - 2x |=4.
(a)1,(b)2,(c)4,(d)6,(e)None of these [Where [x] is Greatest Int Func]
Solution scheme and approach:
Case 1 :( x is a whole number)
so [x]=x
=>|-x|=4 =>x=4 or x=-4
Case 2: ( x is a fraction)
so x=a+f (f is the fractional portion)
then the equation gets converted into
|a-(2a+2f)|=4
=>|-a-2f|=4
=>a=4-2f =>a=3 (when f=1/2) =>x=3.5
or a=-4-2f =>a=-5(when f=1/2)=>x=-4.5
Total four solutions.

Hence option (c)

Polynomial

#Problem 14

Let f be a polynomial of degree 98, such that f(k)=1/k. [k=1,2,3,4...99]. Find the value of f(100).[USAMath Talent Search 2009]

Solution scheme and approach
Consider a function g(k) such that
g(k)=kf(k)-1
As f(k) is a polynomial of deg 98 g(k) should be a polynomial of deg 99.
=>g(k)=C*(k-1)*(k-2)*(k-3)*...*(k-99)
=>kf(k)-1=C*(k-1)*(k-2)*(k-3)*...*(k-99)............(1)
by putting k=0
=>C=1/99!
=>kf(k)-1=[(k-1)*(k-2)*(k-3)*...*(k-99)]/99!
If k=100
=>100f(100)-1=1
=>f(100)=1/50

Number Of Solutions

This is a typical pattern. If you can remember different formats of this specific problem, cracking questions is just a matter of few seconds. Let's have a look.

#Problem 13.1

Let n ≥ 1 be an integer and let t denote the number of positive integer divisors of n^2. Show
that the number of positive integer solutions (a, b) of the equation 1/a−1/b = 1/n is precisely
equal to (t − 1)/2.

Solution scheme and approach:
1/a-1/b=1/n..............(1)
From the above equation it's clear that 1/a>1/n =>n>a
Now we can consider an integer x such that
a=n-x
From equation number (1) we can also write
1/b=1/(n-x)-1/n=x/(n-x)*n
=>b=(n^2-nx)/x=n^2/x-n
To count the total number of solutions we have to count total numbers of possible values of x.
As b is an integer x has to be an integer which must be a factor of n^2 such that x
Now think, n^2 is a perfect square which has a total of t divisors. out of these factors one is n another (t-1)/2 is less than n each of them is paired with other (t-1)/2 number of factors which are greater than n.
[Suppose for 16=4x4=2x8=1x16]
Hence, Total number of solutions are (t-1)/2. Q.E.D.
[N.B: Total number of ordered pair(a,b) would be (t-1)]

Food for thought: 
Let n ≥ 1 be an integer and let t denote the number of positive integer divisors of n^2. Show that the number of positive integer solutions (a, b) of the equation 1/a+1/b = 1/n is precisely equal to t /2.

#Problem 13.2

Find the smallest positive integer n with the property that the equation 1/a − 1/b = 1/n has exactly 2010 different solutions in positive integers a and b.

(a)6^2010,(b)2^2010,(c)1,(d)10^2010,(e)Cannot be determined  

Solution scheme and approach

From the above equation it's clear that 

n^2 should have t number of divisors where (t-1)/2=2010=>t=4021

Suppose 

n=p1^a*p2^b*p3^c*...

=>n^2=p1^2a*p2^2b*p3^2c*...pn^2n

It has (2a+1)*(2b+1)*(2c+1)*....*(2n+1)=4021 number of divisors 

Now the catch is 4021 is a prime number.=>n^2=p1^2a

=>(2a+1)=4021

=>a=2010

As we need to find out smallest possible value of p1 that means p1=2

So the required number is 2^2010

Hence, option (b) is the right option. 

#Problem 13.3

If Ramu and Krishna work on alternate days to complete a work, then the work gets completed in exactly 24 days. If R and K denote the number of days required by Ramu and Krishna respectively to complete the work independently, then how many ordered pairs of integral values of R and K are possible? 
(a)14, (b)8, (c)15, (d)7,(e)16                                                [Career Launcher Mock CAT]
Solution scheme and approach
Ramu and Krishna work 1/R and 1/K th work per day respectively
According to the question as they are working on alternative day.We may say if they work together work must be completed on 12th day
=>12(1/R+1/K)=1
=>(1/R+1.K)=1/12
As, 12^2=2^4*3^2 has [(4+1)*(2+1)]/2=15/2 number of solutions.So total number of ordered pair(R,K) solutions are 15. (refer Food for thought) 
Hence, Option (c). 

Hope, this session has helped you a little bit to clear these things.
All the best!!

Powered Modulo

When we need to calculate the modulus (or remainder) of a nth powered number, we have to find out out the pattern. 

#Problem 12.1
if a^2+b^2 is a multiple of 7^2009 then prove that ab is a multiple of 7^2010.[USA Math Talent Search]
 Solution scheme and approach
a^2+b^2=7^2009*k 
As right hand side is divisible by 7 left hand should be divisible by 7.
Now we can deduce the the following table 
Number-----Square-------remainder (modulo 7)
0-------------0-------------0
1-------------1-------------1
2-------------4-------------4
3-------------9-------------2
4------------16-------------2
5------------25-------------4
6------------36-------------1
From the table it's clear that as sum of two numbers (>=1) gives 7 so both of them should be divisible by 7.
Let a=7a1,b=7b1. 
=>a^2+b^2=7^2009*k
a1^2+b1^2=7^2007*k
Likewise, let a1=7a2 and b1=7b2
a2^2+b2^2=7^2005*k
=>a=7^2*a1 and b=7^2*b1
and so on ...................
at last we get 
a1004^2 + b1004^2=7k
=>a=7^1005*a1 and b=7^1005*b1
=>ab=7^2010*(a1b1)
=>ab is a multiple of 7^2010. Q.E.D.

#Problem 12.2

A set consists of 143 natural numbers each of them is a perfect cube. If they are divided by 13, how many maximum numbers within the set are possible, such that one will get the same reminder in each case.

(a)11, (b)31, (c)33, (d)36, (e)29 [AIMCAT]

Solution scheme and approach 
When any cube(0^3,1^3,2^3,...,12^3) divides by 13 it generates 5 different numbers 0,1,5,8,12. Now at least [143/5]+1=29 numbers are possible which will generate same remainder.
Hence, option (e) is the answer 

CAT CLASSIC : Number Theory

Today I talked to one of my Pagalguy friend. He was right in saying that my blog is not good for all. I agree. What I try to discuss, here, is obviously not for all and sometimes the concept becomes too tough to understand. And there are a lot of people who are unable to attend coaching classes due to different reasons. So being a pagalguy member I should help them. And if this section can help you a little, I will consider myself blessed. There will be two sections CAT CLASSIC and CAT SHOT, which will only concentrate on cracking CAT. Though this is, once I have written in my another blog The Unfinished Evening
Here it goes.

Introduction
In ancient Babylon, a sexagesimal(base 60) was in use.In India a decimal system was in place during Harappan period.
It is generally acknowledged that concept of zero,crucial to development of science,is India’s contribution to the world, which was given to Europe through the Arabs.The ancient India astronomer Brahmagupta is credited with having put forth the concept of zero first time.
Another famous Indian mathematician developed the concept of pi as 3.1416(circa 500 AD) claiming,for the first time it was an approximation.Pi represents the number reflecting how many times a circle’s diameter may be divided into its circumference

In the following problem we may get confused:
1+a+a^2+….n terms = (a^n-1)/(a-1) ; if a=1 then 0/0=n, so where lies the pitfall?
No man! It’s correct. 0/0 takes any given value for different n. So it is undefined.We can say something either exists, or it doesn’t. If it exists, then it has a quality that we call number associated with it, and if it doesn’t exist we call this absence, zero.

145 = 1! + 4! + 5! only number which can be expressed as the factorial summation of it’s individual digit.

————————————————————————————————————————————————————Number theory is playing a pivotal role so far as management entrance examinations like CAT/XAT/JMET/IIFT/MAT are concerned. So it’s imperative that good grasp on this topic is essential to ace quantitative section. The whole chapter is divided into three topics.
Topic 1: Numbers and Divisibility


Divisibility Fundamentals
(i)Any composite number N=a^m * b^n * c^p [a,b,c all are prime numbers] has number of factors equals to (m+1)*(n+1)*(p+1)
 (ii)sum of it’s divisors is given by (a^m+1 – 1)/(a-1)*(b^n+1 – 1)/(b-1)*(c^p+1 – 1)/(c-1)
(iii)Product of it’s divisors equals to N^[(m+1)*(n+1)*(p+1)/2]
(iv)The number of ways in which the number can be resolved into two factors are (m+1)*(n+1)*(p+1)/2 and if the number is a square number then number of ways would be [(m+1)*(n+1)*(p+1)+1]/2

Condition for two divisors of any number n to be co-prime to each other
(i)Let N=a^m*b^n has (m+1)(n+1)-1+mn numbers of factors which are co-prime to each other. If N=12, then as 12=2^2*3,so it has (2+1)*(1+1)-1+2=7 sets which are co-prime to each other.They are: (1,2),(1,3),(1,4),(1,6),(1,12),(2,3),(3,4).
(ii)Similarly we can deduce the formula for higher orders.If N=a^m*b^n*c^p then it will have (m+1)(n+1)(p+1)-1+mn+np+mp+3mnp co prime factors.Actually it is a deduction of previous formula.As N=a^m*b^n has (m+1)(n+1) -1+mn number of factors So N=d^[(m+1)(n+1)-1+mn]*c^p has[(m+1)(n+1)+mn-1+1](p+1) -1+[(m+1)(n+1)-1+mn]p number of factors which is equal to (m+1)(n+1)(p+1)-1+mn+np+mp+3mnp.

The number of ways to express a number by means of product of two co-prime numbers

2^(n-1) ways; where ‘n’ represents number of prime factors of that number. Let N=12=2^2 x 3.Therefore it can be expressed as 2^(2-1)=2 ways as the product of two co-prime numbers.They are (1,12) and (3,4).

Euler’s Function and it’s application
Euler function is related to prime numbers counting theorem.By using this we can count number of co-primes less than of a number.It is denoted by φ(N). φ(N) is known as Euler’s function of number N. N=a^m*b^n*c^p then φ(N) = N(1 – 1/a)(1 – 1/b)(1 – 1/c) and so on for any higher terms.[N.B.:a,b,c all are prime numbers] Let, we have to count all numbers which are co-prime to 12 and less than 12.Therefore we have to count φ(12).As 12=2^2*3, So φ(12)=12(1 – 1/2)(1 – 1/3)=12*(1/2)*(2/3)=4 and obviously pairs are (1,12),(5,12),(7,12),(11,12) or in simple terms 1,5,7,11 are those numbers which are less than 12 and co-prime to 12.

Dirichlet’s theorem
If a is positive and hcf(a,b)=1,then there are infinitely prime numbers in the form of an+b.

Elucid’s Theorem 

If p is a prime number and it divides ab(product of two integers a&b) then either p divides a or p divides b.This proposition is known by Elucidian’s lemma.

Prime Number 

Till now, all attempts made to arrive at a single formula to represent all prime numbers proved to be fruitless.The main reason behind of it is all because there is no symmetricity between the differences among them.One standard notation for prime number is N^2+N+41 where -39=<39.Some properties of prime number are elucidated here.

(i)All prime numbers end in 1,3,7 or 9.(except 2,5).

(ii)Fermat’s little theorem

if p is prime then a^p leaves a remainder a when divided by p or in other words a^p-a=0(mod p)

(iii)Wilson’s theorem 

an integer p will be prime only when (p-1)!+1 is divisible by p.

(iv)Bertrand’s Postulate says, if n is a positive integer greater than 1, then there is always a prime number p n

<2n.

(v)All prime numbers greater than 3 can be expressed as 6K+1 or 6K-1. But converse is not true always.eg.:13(6*2+1) is prime but 25(6*4+1) is not prime.

(vi)1/p (p is prime other than 2 &5 ) always a recurring decimal of period (p-1).It is true for other bases q, provided p is not a prime factor of q.

Perfect Number 
Perfect number is defined as a positive integer which is the sum of its proper positive divisors, that is, the sum of the positive divisors excluding the number itself.First four perfect numbers can be generated by 2ⁿ⁻¹(2ⁿ − 1).[Where 2ⁿ − 1 is a prime number].This are all even perfect numbers.All even perfect numbers (except 6) digital root 1.

Armstrong Number 
Armstrong numbers are the sum of their own digits to the power of the number of digits. example:153 = 1³ + 5³ + 3³[as sum of the digits are 3], 1⁴ + 6⁴ + 3⁴ + 4⁴ = 1634.

Rare Number

The numbers, which gives a perfect square on adding as well as subtracting its reverse are rare and hence termed as Rare Numbers.If R is a positive integer and R1 is the integer obtained from r by writing its decimal digits in reverse order, then R + R1 and R – R1 both are perfect square then R is termed as Rare Number. For example: R=65, R1=56 we can write R+R1 = 65+56 = 121 = 11² & R-R1 = 65 – 56 = 9 = 3².So 65 is a Rare Number.

Properties of co-prime numbers
(i)The numbers a and b are coprime if and only if there exist integers x and y such that ax + by = 1.
(ii)If a and b are coprime and bx = by (mod a), then x = y (mod a).
(iii)Two natural numbers a and b are coprime if and only if the numbers 2^a-1 and 2^b-1 are coprime.

Fermat’s last theorem
If x, y, z and n are integers, there are no solutions of x^n+y^n=z^n with n>2 and x,y,z>0.

Topic 2:Cyclicity, Factorial and Modulo Arithmetic


Cyclicity :
The last digit of the exponents of all nubers have a cyclicity.That is,every Nth power of the base shall have the same digit.Now we can consider the following table to reveal the pattern.

Consider exponents of 2. 2^1=2|2^2=4|2^3=8|2^4=16|2^5=32|2^6=64.So the same unit digit 2 comes again when the exponent is increased by 4.Same pattern is followed for other exponents also.So cyclicity or period of 2 is 4.

Similarly we can conclude: 0,1 5,6 have cyclicity 1, 2,3,7,8 have cyclicity 4,4,9 have cyclicity 2.

We can take an easy example to illustrate it.

Problem: 

Find the unit digit of 7^23 x 4^21

7^23=7^(4*5+3)=7^4*5 x 7^3=(..1) x (343)=…3[As 7 has cyclicity 4, so 7^4n always yields unit digit 1.] Similarly 4^21=4^(2*10+1)=4^(2*10)*4=..1*4=..4[As 4 has cyclicity 2, so 4^2n always produces unit digit 1.] 7^23*4^21=(..3)x(..4)=…2. Required unit digit is 2.

How to find last two digits of a number 

(x+a)^n= x^n+ nc1*x^n-1*y+nc2*x^n-2*y^2+….+y^n. By application of binomial expansion we can do any problem under this category. We can do this kind of problem by using modular arithmetic or by pattern method too.Barring all of these there is also another process to solve.I hope that procedure will help us to solve any problem in lesser time.So I think it would be better to discuss them in another page.

Factorial 

Factorial is another important part of Number System.Generally question comes from either pattern recognition or from determining highest power diving a factorial number.

Thus approach to finding highest power of p(p is prime) in y! is [y/x]+[y/x^2]+[y/x^3]+…….where [] represents greater integer function or gint function.Which determines just integral part of [].It can be used to determine number of zeros in a factorial number.

P.S.:1!+2!+3!+4!+5!=1+2+6+24+120=153 so 1!+2!+3!+4!+…..+n! always yields unit digit 3 and it does not depend on n.Where n can be infinitely any.As 5! is the first number which gives unit digit 0. 10! is the first number which has last two digits 0 and so on & so forth.


Modulo Arithmetic And Remainder Theorems
Suppose n divides a and gives a remainder b then it can be expressed in the format of modulo arithmatic. a=b(mod n). Modular arithmetic follows addition, subtraction and multiplication rule.
If a1=b1(mod n) and a2=b2( mod n) then; (i)(a1+a2)=(b1+b2)(mod n) (ii)(a1-a2)=(b1-b2)(mod n),(iii)(a1.a2)=(b1.b2)(mod n).
 

Euler’s Remainder Theorem:
We alrealdy know what is Euler’s function.Now according to this theorem a^ φ(N)=1(mod N) where a and N are co prime to each other.φ(N) is also known as ORDER of a modulo N.
Corollary:
(a) 1/a=a^ [φ(N)-2](mod N) when a & N are co prime to each other.

(b) a and b are relatively prime positive integers,
then there exist integers m and n such that a^m + b^n = 1 (mod ab)

(ii)Fermat’s Little Theorem:
If p is a prime number,then a^(p-1)=1(mod p)

(iii)Chinese Remainder Theorem:
If N=a*b where a & b are co prime,M is such that M=r1(mod a) and M=r2(mod b) then M=a*r2*x+b*r1*y(mod N) where ax+by=1.

More concepts:
(1)gcd(a^m – 1,a^n – 1)=a^gcd(m,n) – 1 for all positive integers m,n & a>1.
(2)ax+by =n has an non negative integer solution if gcd(a,b)=n.

(3) 1/x+1/y=1/n is a equation where x,y,n are positive integers & n>1.Now we have to determine the number of ordered pairs of (x,y). For this at first we have to do prime factorization of n=a^p1*b^p2*c^p3*….Therefore the number of positive solution se would be (2p1+1)(2p2+1)(2p3+1)….. (4)Divisibility by 7, 11, and 13
Let a number be ….kjihgfedcba where a, b, c, d, are respectively units digits, tens digits, hundreds digits, thousands digits and so on. Starting from right to left, we make groups of three digit numbers successively and continue till the end. It is not necessary that the leftmost group has three digits.
Grouping of the above number in groups of three, from right to left, is done in the following manner 0kj,ihg,fed,cba. Groups are denoted as (4,3,2,1).
We add the alternate groups (1 ^st , 3 ^rd , 5 ^th etc.. and 2 ^nd , 4 ^th , 6 ^th , etc..) to obtain two sets of numbers, N ₁ and N ₂ .
In the above example, N ₁ = cba + ihg and N ₂ = fed + kj
Let D be difference of two numbers, N ₁ and N ₂ i.e. D = N ₁ – N ₂ .
If D is divisible by 7, then the original number is divisible by 7.
If D is divisible by 11, then the original number is divisible by 11
If D is divisible by 13 then the original number is divisible by 13.

Corollary: 
Any six-digit, or twelve-digit, or eighteen-digit, or any such number with number of digits equal to multiple of 6, is divisible by EACH of 7, 11 and 13 if all of its digits are same .
For example 666666, 888888888888 etc. are all divisible by 7, 11, and 13.

(5)Divisibility by 9
Sum up all digits of a number, divide it by 9.The remainder is equal to the remainder when the original number is divided by 9.

Properties of squares

(1)Any square number can be expressed as 3k or 3k+1.

(2)Square of an odd number can be expressed as 4k+1,square of an even number can be expressed as 4k.

(3)Last digit of a square number cannot be 2,3,7,8.

(4)Square of any prime number can be expressed as 6K+1(p>3)

(5)If last digit of a number is odd the previous number would be even.

(6)A square number cannot be a perfect number.

Seed Number or Digital Root

If we sum up all the digits of a number till then single digit is arrived, then that single digit would be the seed of that number

Properties:

(i)To determine a seed we have to divide the number by 9.The remainder obtained will be the seed. If the number becomes perfectly divisible 9 then seed number would be 9.

(ii)A perfect square cannot have any seed number among 2,3,5,6,8.

(iii)6! onwards all number has equal seed number 9.

(iv)The difference between one number and it’s sum of the digits is always divisible by 9.

e.g.:For 68 it’s sum of digit is 15. So difference is 68-14=54.Divisible by 9.

Hope these concepts would help us to open the knot of problems

Concept 3: CATLAN numbers

Can you tell me what is the next number of this series?
1,2,5,14,42,?

You may face trouble in finding though. But here is the formula
Tn=1/(n+1)*2nCn=(2n)!/[(n+1)!*n!] [For n>=1]
So T5=132.
The number of this series is popularly known as CATLAN numbers. And in different counting problems. I will try to explore some of them.

(A)Mountain Ranges and Diagonal Avoiding Paths

(i)How many mountain ranges you can draw using n upstrokes(/) and n downstrokes{\)
   Drawing the above phenomenon would reduce our burden.
n=1: /\ =>1 way
n=2: /\/\,  /\ => 2 ways
               /   \                                     /\
n=3: /\ /\ /\,  /\          /\     /\/\        /   \  => 5 ways
                    /   \/\, /\/  \, /      \,    /     \

Going like this it will generate nothing but the series of CATLAN numbers. For n=4 obviously we will get 14 distinct mountain ranges and so on.

(ii)Diagonal Avoiding Paths

In a grid of n×n squares, how many paths are there of length 2n that lead from the upper right corner
to the lower left corner that do not cross the diagonal dotted line from upper right to lower left? In
other words, how many paths stay on or above the main diagonal.



Again answer is noting but 4'th CATLAN numbers of the series. i.e. 14. And look it's not different than the arrangement of mountain ranges. [Follow the arrowhead paths]

(B)Triangulation of a convex polygon

 

For a convex ploygon having n sides (n>=4) total number of triangulation will be T(n-2) th term of the CATLAN series.

For n=6 obviously we will get 14 triangulations.

(C)Handshaking Lemma
If, 2n people are seated around a circular table, then in Tn ways they can shake their hands simultaneously such that at no instance the arms will cross each other.
Application
If 16 people are sitting in a circular table,in how many ways can all of them be simultaneously
shaking hands with another person at the table in such a way that none of the arms cross each other?Solution:
2n=16 =>n=8
Total ways T8 =16!/9!*8!=1430.

Hope you have enjoyed this concept session.

Again a perfect square

#Problem11

49=7^2

4489=67^2

444889=667^2

............................

Now prove that if we insert 48 in the middle of the previous term of this series, like this way, in each case it will produce a perfect square.

Solution scheme and approach 
Number is in this format
[4444...4](n+1 numbers)[8888...8](n numbers)9
So we can write the number in the following way
[4*10^(2n+1)+4*10^2n+4*10^(2n-1)+....4*10^(n+1)] + [8*10^n+8*10^(n-1)+8*10^(n-2)+...8*10]+9
=4*10^(n+1)*[10^(n+1)-1]/9+8*10*(10^n-1)/9+9
=1/9[4*10^(n+1)*{10^(n+1)-1}+80*(10^n-1)+81]
=1/9[{2*10^(n+1)}^2-4*10^(n+1)+8*10^(n+1)-80+81]
=1/9[{2*10^(n+1)}^2-4*10^(n+1)+1]
=1/9[2*10^(n+1)-1]^2
=>a perfect square for n>=0 Q.E.D.

 

CAT SHOT-1

This section is dedicated to CAT. Here we deal with the problems which often appears in mocks and actual cat as well.Fasten your belt. Here we go.

(1)2^y+2*(3^y)>3*(4^y) and y=3x^2+2x-2

Which of the following is a possible value of x?

(a)-1.5 (b)-2.5 (c)-0.5 (d)0.7 (e)1.2

(2)For N values of t, where t<=250, the highest power of t in t! is t^5. Then which of the following is true? (a)N<=4 (b)N=6 (c)N=8 (d)N=10 (e)N>=12

Concept 2:Diophantine Equations

Diophantine equation is an equation of polynomials where variables are integers only.

Linear Diophantine Equation


from the name it's clear that it's an equation of degree 1.
ax+by=g.c.d.(a,b)=d ...(I)
is also an linear Diophantine equation.According to Bézout's identity if equation number (I) holds true.i.e. gcd(a,b)=d satisfies then, there should be an integer solution of this equation.It's true for more than two variables as well.
Lets take an example
14x+35y=7
As, gcd(14,35)=7 hence Bézout's identity holds true.
Now we can verify it.(x,y)::(-2,1) is an integer solution set of this equation.

Fermat's Last Theorem


 If n=2 this equation becomes x^2+y^2=z^2 nothing but Pythagorian triplets of (x,y,z). Infinite numbers of solution exist.
But if n>=3 no solution exists. This is known as Fermat's Last Theorem

Pell's Equation




this equation is known as Pell's equation, Where n is a non square integer.Trivially x=1, y=0 is one of the solutions of this equation.But there could be other values ,till infinity, as well.

Now by squaring we can write
(x^2-ny^2)^2=1
=>(x^2+ny^2)^2-n(2xy)^2=1
=>(2x^2+1)^2-n(2xy)^2=1 [If x^2-ny^2=-1]...(I)
or, (2x^2-1)^2-n(2xy)^2=1[If x^2-ny^2=1]....(II)
(I) and (II) are also another form of Pell's equation.

Erdős–Straus conjecture


For n>=2, 4/n can be expressed as the summation of three fractional numbers.
Wacław Franciszek Sierpiński generalized this equation and stated that,
for any positive k there exists a number N such that, for all n ≥ N, there exists a solution in positive integers to k/n =1/x+1/y+1/z

Infinite primes

#Problem 10
Prove that infinitely many prime numbers are possible.

Solution Scheme and approach
Let if possible there are a1,a2...an number of finite primes.
Consider another number
N=(a1*a2*a3*...*an)+1
Now we can say,
N is such a number which can be divide by all primes but always gives a remainder 1. Hence, contradiction.
Because any number>1 should be divisible by at least one prime number.

=>Infinite primes are possible. Q.E.D.

Maximum value of a variable

#Problem 9

a+b+c+d+e=8

a^2+b^2+c^2+d^2+e^2=16. [a,b,c,d,e are real numbers]

Find the maximum value of e.

Solution Scheme and approach:

This problem can easily be done with Cauchy-Schwartz  inequality. But will explain this in my next topic. Let's do it without Cauchy.

(a-r)^2+(b-r)^2+(c-r)^2+(d-r)^2+(e-r)^2

=(a^2+b^2+c^2+d^2+e^2)-2r(a+b+c+d+e)+5r^2

=16-16r+5r^2[ By putting the values]

we can write

(e-r)^2<=16-16r+5r^2

=>(e-r)=root[16-16r+5r^2] [equality holds when a=b=c=d=r]

=>e=root[16-16r+5r^2]+r=f(r)

as this function is increasing we have only local minima

f'(r)=0

=>(10r-16)/root(16-16r+5r^2)=0...(i)

=>r=2 or 6/5

but r=2 is extraneous solution.Does not satisfy eqn number (i)

So r=6/5

=>e is maximum when a=b=c=d=6/5

=>max(e)=f(6/5)=16/5.

 

PROBLEM OF THE WEEK-1

Here I start a new section called problem of the week. Solution of this question will be posted in the coming week. Till then have fun.

Alphonse and Beryl are back! They are playing a two person game with the following
rules:
• Initially there is a pile of N stones, with N >= 2.
• The players alternate turns, with Alphonse going first. On his first
turn, Alphonse must remove at least 1 and at most N −1 stones from
the pile.
• If a player removes k stones on their turn, then the other player must
remove at least 1 and at most 2k − 1 stones on their next turn.
• The player who removes the last stone wins the game.
(a) Determine who should win the game when N = 7, and explain the winning
strategy.[Easy]
(b) Determine who should win the game when N = 8, and explain the winning
strategy.[Medium]
(c) Determine all values of N for which Beryl has a winning strategy. Explain this
strategy.Where N<=100[Difficult]

e is irrational

#Problem 8

Prove that e is irrational

Solution scheme and approach
e=1+1/1!+2/2!+3/3!+.....(i)
Let e is rational so e=p/q
multiplying equation number (i) by q! we get
q!*e=q!+q!/1!+q!/2!+q!/3!+....+q/q!+ other terms
Now as q!+q!/1!+...+q!/q! is an integer and q!*e is also an integer
So we can say other terms should be an integer. Let I signifies the rest terms whose summation is an integer.
I=q![1/(q+1)!+1/(q+2)!+1/(q+3)!+...]
=1/(q+1)+1/(q+1)*(q+2)+1/(q+1)*(q+2)*(q+3)+.....
<1/(q+1)+1/(q+1)^2+1/(q+1)^3+....=1/(q+1)/[1-1/(q+1)]=1/q<1
=>I< 1
Hence contradiction.
So, e should be an irrational number. Q.E.D.
[This solution has been proposed by Fourier]

Number's application

#Problem 7
Show that there is no integer a such that a^2-3a-19 is divisible by 289.[R.M.O. 2009]
Solution Scheme and Approach
a^2-3a-19
=a^2-3a-70+51
=(a+7)(a-10)+51 ...(i)

Now as (i) divides by 289 it should be divisible by 17 as well. So, it is clear at least one of (a+7) and (a-10) should be divisible by 17.
Let, a-10=17k =>a=10+17k therefore a+7=17(k+1)
Hence we can write a^2-3a-19=289k(k+1)+51
As 289k(k+1) is divisible by 289 so 51 has to be divisible by 289 as well..
Not possible, Hence Contradiction
There is no integer a such that a^2-3a-19 is divisible by 289.Q.E.D.

Cubic Equation

#Problem 6  
The cubic equation x^3+2x-1 = 0 has exactly one real root r. Note that 0.4 < r < 0.5.

(a)Prove that an increasing sequence of positive integers a1,a2,a3,.....exists, such that 1/2=r^a1+r^a2+r^a3+.... is possible

(b) Prove that the sequence that you found in part (a) is the unique increasing sequence
with the above property.

Solution Scheme and approach
(a)
As r is a root then we may write
r^3+2r-1=0 =>1-r^3=2r=>r/(1-r^3)=1/2=>r*(1-r^3)^-1=1/2
By expanding
r*(1+r^3+r^6+r^9+....)=1/2
As |r|<1 the series converges
=>r+r^4+r^7+r^10+....=1/2 equating with r^a1+r^a2+r^a3+..=1/2
we can write {a1,a2,a3....}::{1,4,7....}

(b)Proof by contradiction
If possible let another for another series b1,b2,b3....               r^b1+r^b2+r^b3+...=r^a1+r^a2+r^a3+...=1/2                                                                                                       canceling equal terms
r^x1+r^x2+r^x3+...=r^y1+r^y2+r^y3+...=N [N>0]............(1)
without losing the generality we can consider y1>x1 =>r^y1>r^x1
r^x1<=r^x1+r^x2+r^x3+..=r^y1+r^y2+r^y3+....
Dividing both sides by r^x1
1<=r^p1+r^p2+r^p3+......[yi-xi=pi]...........(2)
As 0<1/2 =>1<1/(1-r)<2 and p1>=1 then,                                                                                                  From (2)
1<=r^p1+r^p2+r^p3+...<=r+r^2+r^3+....=r/1-r=1/(1-r)-1<1
A contradiction.
Hence only one sequence exists.

Perfect square

This is one of the important topics which often comes in various competitive exams.

#Problem 5(A)

Find the total number of values of n for which n^2 + 24n + 21 is a perfect square.Where n is natural number.

Solution scheme and approach
Let n^2+24n+21 is a perfect square.Hence we can write
n^2+24n+21=k^2
=>n^2+2*n*12+12^2-12^2+21=k^2
=>(n+12)^12-k^2=123
Case I
(n+12+k)(n+12-k)=3*41=(-3)*(-41)
So, (n+12+k)+(n+12-k)=3+41
=>2(n+12)=44 =>n=10
or,
2(n+12)=-44=>n=-34
Case II
(n+12+k)(n+12-k)=1*123=-1*-123
So, 2(n+12)=124=>n=49
or,
2(n+12)=-124=>n=-73
Therefore total 4 values of n ::{-73,-34,10,49} are possible.
Food for thought

Find the total number of values of n for which n^2+24n+21 is square of a prime number.Where n is natural number.

What would be the answer then.Understand the difference

#Problem 5(B) 
Find all positive integers n such that n^2 + n + 2009 is a square.[Pomona-Wisconsin Math Talent Search 2009]
Solution scheme and approach
Let, n^2+n+2009=k^2
=>(n+1/2)^2-k^2=1/4-2009[Follow the same method as stated in 5(A)]
=>(n+1/2+k)(n+1/2-k)=-8035/4
=>[2*(n+1/2+k)][2*(n+1/2-k)]=-8035
 (PS:As n is an integer we need to maintain the symmetry. So don't consider [4(n+1/2+k)]*(n+1/2-k) or (n+1/2+k)*[4(n+1/2-k)]. Each of the cases LHS becomes fraction hence contradicts)
 =>(2n+1+2k)(2n+1-2k)=-8035
Now as 2n+1+2k>2n+1-2k
therefore, (2n+1+2k)(2n+1-2k)=1607*-5=8035*-1
=>2(2n+1)=1607-5=1602
=>n=400
or,
2(2n+1)=8034=>n=2008
Two values of n are possible.

Concept 1 :KiSsInG cIrClEs

Descartes' theorem (1964)

If four mutually tangent circles have curvature k_i (for i = 1,...,4), (ki=1/ri, Where ri is radius)

(1)

When trying to find the radius of a fourth circle tangent to three given kissing circles, the equation is best rewritten as:

(2)

The ± sign reflects the fact that there are in general two solutions. Ignoring the degenerate case of a straight line, one solution is positive and the other is either positive or negative; if negative, it represents a circle that circumscribes the first three (as shown in the diagram above).
Other criteria may favor one solution over the other in any given problem.

Special case
If one of the three circles is replaced by a straight line, then one k_i, say k₃, is zero and drops out of equation (1). Equation (2) then becomes much simpler:

(3)

Example:

If three circles of radius 1 touches one another then find the radius of the circle which can be inserted within these circles, touching all the three.[CAT]

Solution:
k4=3+2root(3)[positive for inscribed circle] therefore radius=1/[3+2root(3)]=[2-root(3)]/root(3)

PS:One can use conventional method too.

How many primes

#Problem 4
How many primes among the positive integers, written as usual in base 10, are such that their digits are altenating 1’s and 0’s, beginning and ending with 1? [Putnam]

Solution scheme and approach
Let,
X=1010101…1=1+10^2+10^4+…+10^2n=(10^2n-1)/99=(10^n+1)*(10^n-1)/99

For n=2 X=101 which is a prime number
For n>=3
If n is even
{
As (10^n+1)>99
(10^n-1)=(9+1)^n -1=0(mod 9) So,(10^n-1)=9a
(10^n-1)=(11-1)^n -1=0(mod 11)So (10^n-1)=11b
therefore we can write X=99*a*b*(10^n+1)=>Composite
}
If n is odd
{
As (10^n-1)>99
(10^n-1)=(9+1)^n -1=0(mod 9) So, (10^n-1)=9a[a>1]
(10^n+1)=(11-1)^n +1=0(mod 11) So,(10^n+1)=11b[b>1]
therefore X=99*a*b=>composite
}

So, there is only one prime number, 101, exists.Q.E.D.

Ultimate Divisibility

This is one of the famous puzzles. Try it.

#Problem 3

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number should satisfy the following requirements:

a. The number should be divisible by 9.

b. If the most right digit is removed, the remaining number should be divisible by 8.

c. If then again the most right digit is removed, the remaining number should be divisible by 7.

d. etc. until the last remaining number of one digit which should be divisible by 1.

Have fun.

Infinite descent

If x, y, z and n are integers, there are no solutions of x^n+y^n=z^n with n>2 and x,y,z>0.This is known as Fermat's last theorem.

This problem can be an extension of Fermat's Infinite Descent

#Problem2

Find all solutions to c² + 1 = (a² − 1)(b² − 1), in integers a, b, and c.

Solution Scheme and approach
Clearly a = b = c = 0 is one integer solution.
Also, if c = 0, a^2 − 1 = ±1, and so a = 0; similarly b = 0.
Without loss of generality, we now seek a solution with c > 0.
Assume such a solution exists.
Consider the equation, modulo 4.
Since the square of any integer is either 4k or 4k+1

we have, in mod 4, (a^2 − 1) and (b^2 − 1) = −1 or 0(mod 4),So (a^2-1)(b^2-1)=0 or 1 and (c^2 + 1) =1 or 2(mod 4).
As, L.H.S cant be 2, Hence (a^2 − 1) = (b^2 − 1) = −1 (mod 4), and (c^2 + 1) = 1 (mod 4); that is, a, b, c are even.
Set a = 2x, b = 2y, c = 2z.
Then 4z^2 + 1 = (4x^2 − 1)(4y^2 − 1).
Simplifying, we have z^2 = 4x^2y^2 − x^2 − y^2.

Again considering mod 4, z^2=1 or 0(mod 4) and x^2=y^2=0,1(mod 4) So, R.H.S. can be -2,-1 or 0. Considering R.H.S we can decide z,x,y all are multiple of 4 i.e. even.

Now set z=2s, x=2r, y=2t. Then 16s^2+1=(16r^2-1)(16t^2-1) =>s^2=-16r^2t^2-r^2-t^2. Following the previous modulo 4 method again we can conclude that s,r,t all are even.
And this series continues till infinity. But as c>z>s>...>0 that means c is bounded. Which contradicts. Hence our assumption was wrong. There is no solution exists if c>0.

Therefore the only integer solution to c² + 1 = (a² − 1)(b² − 1) is a = b = c = 0.Q.E.D.

Number of solutions

Here I start my blog with a very interesting problem.

#Problem 1

Find the value of x and y. x^3+y^3=7163.[Where x and y are positive integers]

Solution scheme and approach 1

First of all one number should be even another is odd. Let, x=(2n+1) and y=2m
So,
x^3+y^3=7163
=>(2n+1)^3+(2m)^3=7163.....(i)
=>8n^3+12n^2+6n+1+(2m)^3=7163
=>2n(4n^2+6n+3)+8m^3=7162
=>n(4n^2+6n+3)+4m^3=3581

As RHS is odd ans 4m^3 is even therefore n(4n^2+6n+3) must be odd =>n is odd=>n=2a+1

From eqn (i) we can write
(4a+3)^3+(2m)^3=7163
=>64a^3+144a^2+108a+27+8m^3=7163
=>64a^3+144a^2+108a+8m^3=7136
=>a(16a^2+36a+27)+2m^3=1784

As 2m^3 is even therefore a(16a^2+36a+27) should be even=>a is even

Now by trial and error we have to move forward.
If a=2
then a(16a^2+36a+27)=326 =>m^3=729 =>m=9

So (a,m)::(2,9) =>(x,y)::(4*2+3,2*9)=>(x,y)::(11,18)

Solution scheme and approach 2

x^3+y^3=(x+y)(x^2-xy+y^2)=7163=13*19*29

As x and y are positive integers therefore x+y=1,x+y=7129 should be rejected. and we can also write that x^2+y^2-xy>x+y

3 cases are possible
(i)If x+y=13
then, x^2-xy+y^2=(x+y)^2-3xy=169-3xy=19*29=>3xy=-382 (impossible)

(ii)If x+y=19
then (x+y)^2-3xy=13*29=>361-3xy=13*29 =>3xy=-16(impossible)

(iii)If x+y=29
the (x+y)^2-3xy=29^2-3xy=13*19=>3xy=841-247=>3xy=594=>xy=198=11*18

(x,y)::(11,18)

Hope you have enjoyed the problem :)

Problem for practice:

If =4721. Then find the sum of all values of (a+b).

(a)9, (b)11, (c)13, (d)15, (e)None of the foregoing [Source of this question is totalgadha.com/rmo]