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.
Publishing original scientific research in a peer-reviewed journal is an achievement many scholars work toward for years. Achieving this feat early in one's academic journey requires exceptional intellectual rigor, creativity, and persistence. Aaditya Punatar and Muskan Sadana have reached this remarkable milestone, successfully publishing their collaborative research paper in the prestigious Journal of Emerging Investigators […]
Her project on quantum-accelerated Steiner trees for 15-minute cities earned a place among the finalists at the world's largest pre-college STEM competition. Prishaa Shrimali of Marymount School of New York, was selected as a Grand Finalist at the 2026 Regeneron International Science and Engineering Fair (ISEF) in Phoenix, Arizona. Her project was Optimizing Urban Accessibility: […]
In 2026, the following Cheenta students have been successful for Indian Statistical Institute's M.Stat Entrance. They ranked within the first 50 in the entire country in these entrances. I.S.I. M.Stat Entrance
In 2026, the following Cheenta students have been successful for Indian Statistical Institute's B.Stat Entrance and Chennai Mathematical Institute's B.Sc. Math Entrance. They ranked within the first 200 in the entire country in these entrances. Most of these students attended the problem solving workshops regularly, which happen 5 days every week. CMI B.Sc. Math Entrance […]
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.