edited by
2,209 views
20 votes
20 votes

Let $k$ be an integer at least $4$ and let $\left[k\right]= \left\{1, 2,...,k\right\}$. Let $f:\left[k\right]^{4}\rightarrow \left\{0, 1\right\}$ be defined as follows: $f(y_{1}, y_{2}, y_{3}, y_{4}) = 1$ if an only if the $y_{i} 's$ are all distinct. For each choice $z = (z_{1}, z_{2}, z_{3}) \in \left[k\right]^{3}$, let $g_{z} : \left[k\right]\rightarrow \left\{0, 1\right\}$ be defined by $g_{z}(Y) = f(Y, z_{1}, z_{2}, z_{3})$. Let $N$ be the number of distinct functions $g_{z}$ that are obtained as $z$ varies in $\left\{1, 2,...,k\right\}^{3}$, that is, $N= \mid \left\{g_{z}:z\in \left\{1, 2,...,k\right\}^{3}\right\} \mid$. What is $N$?

  1. $k^{3}+1$
  2. $2^{\left(\frac{k}{3}\right)}$
  3. $\left(\frac{k}{3}\right)$
  4. $\left(\frac{k}{3}\right)+1$
  5. $4 \left(\frac{k}{3}\right)$
edited by

3 Answers

Best answer
11 votes
11 votes
The function $g_z(Y)$ is defined as $[k] \to \{0,1\}$ where $[k]$ is the set of positive integers till $k$. That is, given a triplet $(z_1,z_2, z_3)$, $Y$ can take any value from $1$ to $k$. If $Y$ happen to be any of $z_1, z_2, z_3$, $g_z(Y) = 0$ due to the definition of $f$ and $g_z$. Now even for different $z$, $g_z$ may be the same. Otherwise, the answer would have been how many ways we can form a triplet $z$ - which gives $k^3$ and for each $z$ we get a function $g_z$.

For all unique combinations of $z_1, z_2, z_3$ are unique, we are guaranteed that we get a distinct function $g_z$. This is clear from the definition of $g_z$. For example, suppose $k=4$. The triplets are

$(1,2,3)$
$(1,2,4)$
$(1,3,4)$
$(2,3,4)$
For the triplet $(1,2,3)$, $Y$ can be made in $4$ ways as $(1,2,3,1), (1,2,3,2), (1,2,3,3)$ and $(1,2,3,4)$. Now, as per definition of $g_z$, we get $g_{(1,2,3)} = \{\{1 \to 0\},\{ 2 \to 0\},\{ 3 \to 0\},\{ 4 \to 1\}\}$.

Similarly, for the next three triplets, $g_z$ are different as in second only $3$ maps to $1$, in third one only $2$ maps to $1$ and in fourth one only $1$ maps to $1$.

So, in general, for any given $k$, we have ${}^kC_3$ ways of forming distinct triplets and each of them guarantees a unique function $g_z$ where exactly $k-3$ elements map to $1$ and $3$ elements map to $0$. Now, if any of the elements in the triplet are same, then the function becomes $\{\{1 \to 0\}, \{2 \to 0 \}, \dots, \{k \to 0\}\}$, (all $k$ elements mapping to $0$) and this remains the same for any triplet. So, total number of possible functions are

$${}^kC_3 + 1$$

Correct Answer: $D$
edited by
18 votes
18 votes
I assume definition of f is clear to everyone. The function $g_z(Y)$ is defined over [Y] → {0,1} where Y ∈ ℝ.  The questions states "find the number of distinct functions, $g_z(Y)$". Note here that, $g_z(Y)$ is not a single function, it is changing with the change in set $z$.

If I say there exists a function $p(x)= \begin{cases} 1,& \text{if } x\geq 1\\ 0, & \text{otherwise} \end{cases}$ and there exists another function $h(x)= \begin{cases} 1,& \text{if } x\geq 1\\ 0, & \text{otherwise} \end{cases}$, you would realize that these two are essentially one function only, just with different names.


Hence, among $p(x)$ and $h(x)$, there is only 1 distinct function. Coming back to $g_z(Y)$, first consider quantification (change) over $z$.

Consider distinct z = {z1,z2,z3}, for each distinct z, there will be a distinct $g_z(Y)$. For example $g_{(1,2,3)}(Y)$ is distinct function and where $g_{(1,2,3)}(Y)$ = $f(Y,1,2,3)$ = 0 if {Y is 1 or 2 or 3} else 1. Similarly, $g_{(1,2,4)}(Y)$ is distinct and $g_{(1,2,5)}(Y)$ is distinct. There are k(k-1)(k-2) ways to select {z1,z2,z3}. But notice here,

$g_{(1,2,3)}(Y)$=$g_{(2,1,3)}(Y)$=$g_{(3,2,1)}(Y)$=.... i.e. $g_{(1,2,3)}(Y)$ is counted 3! times. Hence we'll divide the total number by 3!

That is $\tfrac{k(k-1)(k-2)}{3!}$ = $\tfrac{k(k-1)(k-2)(k-3)!}{3!*(k-3)!}$ = kC3 = $\tbinom k3$

But wait, what about non-distinct z? Well for non-distinct z, all $g_z(Y)$ will be identical functions. How? Consider this, $g_{(1,1,1)}(Y)$ will always be 0 and so does $g_{(1,1,2)}(Y)$ and so does $g_{(2,2,2)}(Y)$ etc etc. Therefore for all non-distinct z (which are $k^3 - k(k-1)(k-2)$ in number), all $g_z(Y)$ will be =0 and all those will be counted as 1 function.

Therefore final answer is $\tbinom k3 + 1$, D it should be.
edited by
0 votes
0 votes
f=1 if all of its elements are distinct.

Now g=Y.  where the number of different values of Y depend on the number of possible distinct sets{z1,z2,z3} .

each z value  lies between 1 and k. for {z1,z2,z3} to be distinct, 3 elements should be selected without repetition from {1,2,3,4......k}

this can be done in k*(k-1)*(k-2) ways and there are k-3 possibilities for Y if g(z) should be distinct.

 I am getting  kP4= k(k-1)(k-2)(k-3)(k-4) as answer.
Answer:

Related questions

3 votes
3 votes
0 answers
4