edited by
1,365 views
13 votes
13 votes

Consider a function $T_{k, n}: \left\{0, 1\right\}^{n}\rightarrow \left\{0, 1\right\}$ which returns $1$ if at least $k$ of its $n$ inputs are $1$. Formally, $T_{k, n}(x)=1$ if $\sum ^{n}_{1} x_{i}\geq k$. Let $y \in \left\{0, 1\right\}^{n}$ be such that $y$ has exactly $k$ ones. Then, the function $T_{k, n-1} \left(y_{1}, y_{2},....y_{i-1}, y_{i+1},...,y_{n}\right)$ (where $y_{i}$ is omitted) is equivalent to

  1. $T_{k-1}, n(y)$
  2. $T_{k, n}(y)$
  3. $y_{i}$
  4. $\neg y_{i}$
  5. None of the above
edited by

4 Answers

Best answer
15 votes
15 votes

$T_{k,n} = 1$ iff there are at least $k$ $1's$ in $n$ bit binary string.

Similarly, $T_{k,n-1} = 1$ iff $k$ $1's$ are there out of $(n-1)$ bits

It is given that  $\langle y_1,y_2,y_3,y_4,y_5 \ldots y_n\rangle$  has exactly $k$ $1's$ which means out of $n$ bits, $k$ bits are $1's.$

Now, suddenly one-bit $y_i$ is removed (that one bit can be $1$ or $0,$ we don't know). Removing one bit will make the number of bits as $(n-1).$

So, $T_{k,n-1}$ really depends on whether $i^{th}$ bit which we removed is a $0$ or $1.$ If $0,$ then we have $k$ $1's$ in our remaining $(n-1)$ bits and function will return $1.$
 If $1,$ then we have only $(k-1)$ $1's$ out of $(n-1)$ bits and so the function will return $0.$

So, $T_{k,n-1} = \neg y_i$ which depends on the value of $y_i$ .

Option D is correct. 

selected by
9 votes
9 votes
ANS : D

as number of $1's$ is exactly $k$ and $y_{i}$ is missing . if $y_{i} =1$   then result becomes $0$  , because number of $1's$ are less than $k$ now.

if $y_{i}= 0$ then result becomes $1$. as number of $1's$ remain same. removal of which won't effect final value.
edited by
1 votes
1 votes

Given that ,Tk,n(x) =1 if  ∑ xi ≥ k  ,which is eqt to say ,Tk,n(x) =1 if atleast k of its n inputs are 1.

We need to have atleast k inputs whose values are 1 for Tk,n(x) =1.

y ∈ {y1,y2,y3,.........y(i-1),y(i+1),........yn}

In this yi is misssing and we need to findout the value of Tk,n−1(y1,y2,....yi−1,yi+1,...,yn).

See, we dont know what is the value of yi but we know that it is either 0 or 1 because codomain is {0,1}.

And in Qs given that y has exactly k - one's and (n-k) - zero's.

Missing yi has only two possible value either 0 or 1.

CASE-1: if yi = 0

It means k inputs are present in (y1,y2,....yi−1,yi+1,...,yn) whose values are 1.It satisfy the condition Tk,n(x) =1 if atleast k of its n inputs are 1.

Therefore, Tk,n−1(y1,y2,....yi−1,yi+1,...,yn)  = 1 = complement of yi 

CASE-2: if yi = 1

It means only (k-1) inputs are present in (y1,y2,....yi−1,yi+1,...,yn) whose values are 1.So it does not satisfy the condition Tk,n(x) =1 if atleast k of its n inputs are 1.

Therefore, Tk,n−1(y1,y2,....yi−1,yi+1,...,yn)  = 0 = complement of yi 

Hence,it is equivalent to say  Tk,n−1(y1,y2,....yi−1,yi+1,...,yn)  =  complement of yi .

The correct answer is,(d) ¬yi 

0 votes
0 votes
Answer will be (d) because $T_{k, n-1} \left(y_{1}, y_{2},....y_{i-1}, y_{i+1},...,y_{n}\right)$ means that at least k ones should be  present in n-1 inputs. We are removing 1 bit from $T_{k, n}$ so our $T_{k, n-1}$ will depend on whether that one bit  was 1 or 0.

If it was 1 then we will have k-1 1s and the result will be 0

If it was 0 then we will have k 1s and the result will be 1

so our result depends on that $y_i$ bit which when 0 result is  when  result will be 0

so answer is (D) $\neg y_1$
Answer:

Related questions

8 votes
8 votes
2 answers
3
makhdoom ghaya asked Nov 5, 2015
1,401 views
The minimum of the function $f(x) = x \log_{e}(x)$ over the interval $[\frac{1}{2}, \infty )$ is$0$$-e$$\frac{-\log_{e}(2)}{2}$$\frac{-1}{e}$None of the above