in Set Theory & Algebra edited by
1,353 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
in Set Theory & Algebra edited by
1.4k views

4 Answers

15 votes
15 votes
Best answer

$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

1 comment

Example - Suppose $n = 5 , k = 3 , i=3$
Lets take $y =(y_1,y_2,y_3,y_4,y_5)=11001.$
I omit $y_i$ i.e $y_3$ which is $0.$
Now $y$ becomes = 1101 . Note that , again y has exactly k i.e 3  1's so
$T_{k,n−1}(y_1,y_2,....y_{i−1},y_{i+1},...,y_n) = T_{3,4}(y_1,y_2,y_4,y_5) =1$

Now take $y =(y_1,y_2,y_3,y_4,y_5)= 11100$ .Omit $y_i$ i.e $y_3$ which is $1.$
Now $y$ becomes = 1100 . Note that , now y has 2 1's only so
$T_{k,n−1}(y_1,y_2,....y_{i−1},y_{i+1},...,y_n) = T_{3,4}(y_1,y_2,y_4,y_5) = 0$

When $y_i$ = 0,  $T_{k,n−1}(y_1,y_2,....y_{i−1},y_{i+1},...,y_n) = 1$
When $y_i$ = 1,  $T_{k,n−1}(y_1,y_2,....y_{i−1},y_{i+1},...,y_n) = 0$
So  $T_{k,n−1}(y_1,y_2,....y_{i−1},y_{i+1},...,y_n) = \neg y_i$

3
3
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

3 Comments

I am unable to understand this.Here it is given that y has exectly k 1's. So for every y , its output should be 1 according to the condition.???
0
0
nice answer :)
0
0
@sushmita can you explain me ??
0
0
1 vote
1 vote

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

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