GO Classes DPP | GATE CS | Discrete Mathematics| Functions

Answer 1

First, we'll check whether $f$ a valid function from $\mathbb{Z}$ to $\mathbb{Z}$ or not.

For any integer $n$, the value $3n+1$ is an integer. Therefore, $\frac{3n+1}{2}$ is a real number. The floor function $\lfloor x \rfloor$ maps any real number $x$ to the greatest integer less than or equal to $x$. This means the output will always be an integer. Thus, $f$ is a well-defined function from $\mathbb{Z}$ to $\mathbb{Z}$. This eliminates Option A.

Now, we'll check if $f$ one-to-one (injective) or not.

Let's see how the function grows by calculating $f(n+1) - f(n)$:

$$f(n+1) = \left\lfloor \frac{3(n+1)+1}{2} \right\rfloor = \left\lfloor \frac{3n+4}{2} \right\rfloor = \left\lfloor \frac{3n+1}{2} + 1.5 \right\rfloor$$

Depending on whether $n$ is even or odd, $\frac{3n+1}{2}$ will either be an integer or end in $.5$.

• If $\frac{3n+1}{2}$ ends in $.5$, adding $1.5$ increases the floor value by exactly $2$.

• If $\frac{3n+1}{2}$ is an integer, adding $1.5$ increases the floor value by exactly $1$.

In all cases, $f(n+1) > f(n)$. Because the function is strictly increasing, it is impossible for two different inputs to produce the same output. Therefore, $f$ is one-to-one.

 

Now, we'll check if $f$ onto (surjective) or not.

Let's test a few consecutive integer inputs to see the sequence of outputs:

• $f(0) = \lfloor 1/2 \rfloor = 0$

• $f(1) = \lfloor 4/2 \rfloor = 2$

• $f(2) = \lfloor 7/2 \rfloor = 3$

• $f(3) = \lfloor 10/2 \rfloor = 5$

Notice that the output skips the integer $1$. Since we already established that the function is strictly increasing, it will never "go back" to hit $1$. Because there is an integer in the codomain ($y=1$) that is not mapped to by any integer $n$ in the domain, the function is not onto.

Conclusion : The function $f$ is one-to-one but not onto. The correct option is B.

Answer 2

Correct Option: B

1. Is it a valid function?

Yes. The floor function $\lfloor x \rfloor$ by definition outputs the greatest integer less than or equal to $x$. Since $\frac{3n+1}{2}$ is a real number for any integer $n$, its floor value will always be a unique integer. Thus, $f: \mathbb{Z} \to \mathbb{Z}$ is a well-defined function

2.  One-to-One (Injective)

Proof  for injectivity:

If $n_2 \ge n_1 + 1$, then:

$$3n_2 + 1 \ge 3n_1 + 4$$

$$\frac{3n_2 + 1}{2} \ge \frac{3n_1 + 1}{2} + 1.5$$

Taking the floor of both sides guarantees that $\lfloor \frac{3n_2 + 1}{2} \rfloor > \lfloor \frac{3n_1 + 1}{2} \rfloor$. Since a strictly increasing function on integers never repeats outputs, $f$ is one-to-one.

3. Onto (Surjective)

 we generated: $0, 2, 3, 5\dots$

The integer $1$ is completely skipped.

Let's check if any $n$ can produce $1$:

$$\left\lfloor \frac{3n+1}{2} \right\rfloor = 1 \implies 1 \le \frac{3n+1}{2} < 2$$

$$2 \le 3n + 1 < 4$$

$$1 \le 3n < 3$$

$$\frac{1}{3} \le n < 1$$

Since there is no integer $n$ in the interval $[\frac{1}{3}, 1)$, the value $1$ has no pre-image. Therefore, $f$ is not onto.