The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

Let $f$ be a function with both input and output in the set $\{0,1,2, \dots ,9\}$, and let the function $g$ be defined as $g(x) = f(9-x)$. The function $f$ is non-decreasing, so that $f(x) \geq f(y)$ for $x \geq y$. Consider the following statements:

  1. There exists $x \in \{0, \dots ,9\}$ so that $x = f(x)$
  2. There exists $x \in \{0, \dots ,9\}$ so that $x = g(x)$
  3. There exists $x \in \{0, \dots ,9\}$ so that $x = (f(x) +g(x)) \text{mod }10$

Which of the above statements must be TRUE for ALL such functions $f$ and $g$ ?

  1. Only $(i)$ 
  2. Only $(i)$ and $(ii)$
  3. Only $(iii)$
  4. None of them
  5. All of them
in Set Theory & Algebra by Veteran (421k points)
edited by | 448 views

Given ans. is B.

Let's say we take f(x) = x, which is a non-decreasing function.

So, according to statement I, there exists at least one x such that x = f(x). So, statement I is true.

Now for the statement II, the g(x) is defined as f(9-x). There is no x in {0,1,2,...9} that satisfies x=g(x) = f(9-x). So, this statement isn't true for our case here.

Now, for Statement III, it is true, for our case here, for x=1 which belongs to {1,2,...9}.

Can someone explain why option B is correct?


Edit : Official Answer Key


#unrelated @Arjun Sir ,    any good source to learn skills required to solve various sequences and series ??

1 Answer

+3 votes
Option A.

We have $10$ elements for the domain set to map to. If we want to ensure $x \neq f(x)$ lets do as follows:

$f(0) = 1, f(1) = 2, f(2) = 3, \ldots, f(8) = 9.$ Now the only option is for $f(9) = 9$ or else we will break the non-decreasing condition.

Like this for any mapping we will get at least one $x$ such that $x = f(x).$

Now consider $f(0) = 0, f(1) = 0, f(2) = 0, \ldots  ,f(8) = 0, f(9) = 1.$ This implies, $g(9) = g(8) = g(7) = \ldots =g(1) = 0, g(0) = 1.$ That is we have a non-decreasing $f$ and for no $x,$ $x = g(x).$ So, (ii) is FALSE.

Let $f(0) = f(1) = f(2) = \ldots =f(8) = 0,f(9) = 1.$ Now, for no $x,$ $x = f(x) + g(x) \mod 10.$ So, (iii) is FALSE.
by Veteran (421k points)
edited by
Is taking examples the only way? Or is there any formal approach to solve such type of questions?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,376 questions
55,839 answers
91,392 users