Q7. Consider
two circles with radii a, and b and centers at (b, 0), (a, 0)
respectively with b<a. Let the crescent shaped region M has a
third circle which at any position is tangential to both the inner
circle and the outer circle. Find the locus of center c of the third
circle as it traverses through the region M (remaining tangential to
both the circle.
Discussion:
Q8. Let S = {1, 2, ... , n}. Let \(f_1 , f_2 , ... \) be functions from S to S (one-one and onto). For any function f, call D, subset of S, to be invariant if for all x in D, f(x) is also in D. Note that for any function the null set and the entire set are 'invariant' sets. Let deg(f) be the number of invariant subsets for a function.
a) Prove that there exists a function with deg(f)=2.
b) For a particular value of k prove that there exist a function with deg(f) = \(2^k\)
Discussion:
(a)
Consider the function defined piecewise as f(x) = x - 1 is \(x \ne 1\) and f(x) = n if x = 1
Of course null set and the entire sets are invariant subsets. We prove that there are no other invariant subsets.
Suppose D = {\(a_1 , a_2 , ... , a_k \)} be an invariant subset with at least one element.
Since we are working with natural numbers only, it is possible to arrange the elements in ascending order (there is a least element by well ordering principle).
Suppose after rearrangement D = {\(b_1 , b_2 , ... , b_k \)} where \(b_1\) is the least element of the set
If \(b_1 \ne 1\) then \(f(b_1) = b_1 -1\) is not inside D as \(b_1\) is the smallest element in D. Hence D is no more an invariant subset which is contrary to our initial assumption.
This \(b_1\) must equal to 1.
As D is invariant subset \(f(b_1) = n \) must belong to D. Again f(n) = n-1 is also in D and so on. Thus all the elements from 1 to n are in D making D=S.
Hence we have proved that degree of this function is 2.
(b)
For a natural number 'k' to find a function with deg(f) = \(2^k\) define the function piecewise as
f(x) = x for \(1\le x \le k-1\)
= n for x=k
= x-1 for the rest of elements in 'n'
To construct an invariant subset the 'k-1' elements which are identically mapped, and the entirety of the 'k to n' elements considered as a unit must be considered. Thus there are total k-1 + 1 elements with which subsets are to be constructed. There are \(2^k\) subsets possible.
Discussion:
Join AC and BC. AC passes
through, \(T_1\) the point of tangency of the smaller circle with the circle
with center at (a, 0) and BC when extended touches \(T_2\) which is
the other point of the tangency.
Assume the radius of
the moving (and growing circle) to be r at a particular instance.
Then AC = a+r and BC = b-r.
Then AC+BC = a+b which
is a constant for any position of C. Hence C is a point whose some of
distances from two fixed points at any instant is a constant. This is
the locus definition of an ellipse with foci at (a, 0) and (b, 0).
Q8. Let S = {1, 2, ... , n}. Let \(f_1 , f_2 , ... \) be functions from S to S (one-one and onto). For any function f, call D, subset of S, to be invariant if for all x in D, f(x) is also in D. Note that for any function the null set and the entire set are 'invariant' sets. Let deg(f) be the number of invariant subsets for a function.
a) Prove that there exists a function with deg(f)=2.
b) For a particular value of k prove that there exist a function with deg(f) = \(2^k\)
Discussion:
(a)
Consider the function defined piecewise as f(x) = x - 1 is \(x \ne 1\) and f(x) = n if x = 1
Of course null set and the entire sets are invariant subsets. We prove that there are no other invariant subsets.
Suppose D = {\(a_1 , a_2 , ... , a_k \)} be an invariant subset with at least one element.
Since we are working with natural numbers only, it is possible to arrange the elements in ascending order (there is a least element by well ordering principle).
Suppose after rearrangement D = {\(b_1 , b_2 , ... , b_k \)} where \(b_1\) is the least element of the set
If \(b_1 \ne 1\) then \(f(b_1) = b_1 -1\) is not inside D as \(b_1\) is the smallest element in D. Hence D is no more an invariant subset which is contrary to our initial assumption.
This \(b_1\) must equal to 1.
As D is invariant subset \(f(b_1) = n \) must belong to D. Again f(n) = n-1 is also in D and so on. Thus all the elements from 1 to n are in D making D=S.
Hence we have proved that degree of this function is 2.
(b)
For a natural number 'k' to find a function with deg(f) = \(2^k\) define the function piecewise as
f(x) = x for \(1\le x \le k-1\)
= n for x=k
= x-1 for the rest of elements in 'n'
To construct an invariant subset the 'k-1' elements which are identically mapped, and the entirety of the 'k to n' elements considered as a unit must be considered. Thus there are total k-1 + 1 elements with which subsets are to be constructed. There are \(2^k\) subsets possible.
Please upload the solutions of other questions as soon as possible
ReplyDeleteCheck www.cheenta.com/forum for other solutions and discussions. We will post it in the blog very soon.
ReplyDeleteSolution of 3: Let i denote the row number and j denote the column number
ReplyDeleteThen by inspection,
elements in first row are given by formula
a_{1j}=(j(j+1))/2
in general any element of array is given by formula
a_{ij}=((i+j-1)(i+j-2))/2+j
If a_{ij}=20096
If we put j=196, we get i=5.
Therefore 20096 lies in 5th row and 196 column of array.
Remark: Solving problem by guessing is difficult. I myself could only figure formula in exam.
Regards,
Sumit Kumar Jha