GATE CS 2014 Set 3 — Question 59
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+2 / -0.67HardSets, Relations & FunctionsSets & CombinatoricsEngineering Mathematics
Engineering Mathematics → Sets & Combinatorics → Sets, Relations & Functions
Last updated
Question
Consider the set of all functions such that , for all . Consider the following statements:
. For each such function it must be the case that for every .
. For each such function it must be the case that for some .
. Each such function must be onto.Which one of the following is CORRECT?
. For each such function it must be the case that for every .
. For each such function it must be the case that for some .
. Each such function must be onto.Which one of the following is CORRECT?
Correct answer
(B) Only Q and R are true
Solution
The domain is . The size of the set is (an odd number).
The condition is for all . This means is an involution.Statement R: Since , has an inverse (which is itself). Any invertible function is a bijection, and thus must be onto. So, R is true.Statement Q: The condition implies that the permutation structure of consists of disjoint cycles of length 1 (fixed points where ) or length 2 (swaps where and ).
Let be the number of 2-cycles and be the number of 1-cycles.
The total number of elements is .
Since is always even and 2015 is odd, must be odd. Therefore, . This means there is at least one element such that . So, Q is true.Statement P: Does have to hold for every ? No. We can construct a function where some elements are swapped. For example, , and for . This satisfies but is not the identity function. So, P is false.Conclusion: Only Q and R are true.
The condition is for all . This means is an involution.Statement R: Since , has an inverse (which is itself). Any invertible function is a bijection, and thus must be onto. So, R is true.Statement Q: The condition implies that the permutation structure of consists of disjoint cycles of length 1 (fixed points where ) or length 2 (swaps where and ).
Let be the number of 2-cycles and be the number of 1-cycles.
The total number of elements is .
Since is always even and 2015 is odd, must be odd. Therefore, . This means there is at least one element such that . So, Q is true.Statement P: Does have to hold for every ? No. We can construct a function where some elements are swapped. For example, , and for . This satisfies but is not the identity function. So, P is false.Conclusion: Only Q and R are true.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Sets & Combinatorics
2026 Set 2 Q3A day can only be cloudy or sunny. The probability of a day being cloudy is , independent of…2026 Set 2 Q5‘When it is raining, peacocks dance.’ Based only on this sentence, which one of the following…2026 Set 2 Q8Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the…2026 Set 1 Q10An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice…2026 Set 2 Q10An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice…