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 $(f)° $ be the number of invariant subsets for a function.
a) Prove that there exists a function with $(f)°=2 $.
b) For a particular value of k prove that there exist a function with $ (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 ${(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
from where...
What do you mean?
Check cheenta.com/forum for other solutions and discussions. We will post it in the blog very soon.
Solution of 3: Let i denote the row number and j denote the column numberThen by inspection,elements in first row are given by formulaa_{1j}=(j(j+1))/2in general any element of array is given by formulaa_{ij}=((i+j-1)(i+j-2))/2+jIf a_{ij}=20096If 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
Could we solve it this way?
Let us assume that f is a many-one function that assumes exactly K values out of the set of n Natural numbers for x=1,2,3....n. Thus we have (n-k) values that do not feature in the range of f. Now , we do an interesting operation . We consider all subsets of these (n-k) elements ( 2^(n-k)) and insert the range set of f into each. thus all these subsets are now invariant under f. Therefore, Deg(f) =2^n-k
Replacing k by (n-1), we have a function whose degree is 2.
Replacing k by (n-k) ,we have afunction whose degree is 2^k.