GATE IT 2005 | Question: 46

Question

A line $L$ in a circuit is said to have a $stuck-at-0$ fault if the line permanently has a logic value $0$. Similarly a line $L$ in a circuit is said to have a $stuck-at-1$ fault if the line permanently has a logic value $1$. A circuit is said to have a multiple $stuck-at$ fault if one or more lines have stuck at faults. The total number of distinct multiple $stuck-at$ faults possible in a circuit with $N$ lines is 

• A. $3^N$
• B. $3^N - 1$
• C. $2^N - 1$
• D. $2$

Answer 1

Answer should be ${3^N}-{1}$.

Explanation:

The total possible combinations (i.e., a line may either be at fault (in $2$ ways i.e stuck at fault $0$ or $1$) or it may not be, so there are only $3$ possibilities for a line ) is ${3^N}$.

In only one combination the circuit will have all lines to be correct (i.e not at fault.)

Hence ${3^N}-{1}$ (as it has been said that circuit is said to have multiple stuck up fault if one or more line is at fault)

Comments

i quickly understood the question after reading this comment, thanks bud

 

---

@Lavish_Mittal Wlcm bro

---

yeah it is similar to this question of n couples invited to the party. Combinatory: GATE CSE 2003 | Question: 5

Answer 2

In a line, there can be three possibilities :
1. Stuck-at 0 fault
2. Stuck-at 1 fault
3. No fault

Thus, total combinations = 3^N

It is mentioned that one or more lines have stuck at faults.
So, a case in which there is no fault in any line i.e. all lines are correct can not occur.
Total combinations = 3^N – 1

 
Thus, option (B) is correct.

Answer 3

Correct Option: B

---

 

Verification for $N=4$ lines:

For each line that is stuck we have 2 possiblities either stuck-at-1 or stuck-at-0

• 1 line stuck: $\binom{4}{1} \times 2 = 8$

• 2 lines stuck: $\binom{4}{2} \times 4 = 24$

• 3 lines stuck: $\binom{4}{3} \times 8 = 32$

• 4 lines stuck: $\binom{4}{4} \times 16 = 16$

• Sum $= 8 + 24 + 32 + 16 = \mathbf{80}$

• Using formula: $3^4 - 1 = 81 - 1 = \mathbf{80}$.
   

Also we can try using binomial expansion for this approach

Using the Binomial Theorem for $N=4$:

$$(1 + x)^4 = \binom{4}{0}x^0 + \binom{4}{1}x^1 + \binom{4}{2}x^2 + \binom{4}{3}x^3 + \binom{4}{4}x^4$$

If we substitute $x = 2$, we get:

$$(1 + 2)^4 = \binom{4}{0}2^0 + \binom{4}{1}2^1 + \binom{4}{2}2^2 + \binom{4}{3}2^3 + \binom{4}{4}2^4$$

Now, let's calculate the values for each specific term:

• $\binom{4}{0}2^0 = 1 \times 1 = \mathbf{1}$ (This is the "no faults" state)

• $\binom{4}{1}2^1 = 4 \times 2 = \mathbf{8}$

• $\binom{4}{2}2^2 = 6 \times 4 = \mathbf{24}$

• $\binom{4}{3}2^3 = 4 \times 8 = \mathbf{32}$

• $\binom{4}{4}2^4 = 1 \times 16 = \mathbf{16}$

Plugging those calculated values back into the equation:

$$3^4 = 1 + \left[ 8 + 24 + 32 + 16 \right]$$

To find the total number of multiple stuck-at faults (the bracketed portion), we move the $1$ to the other side:

$$3^4 - 1 = 8 + 24 + 32 + 16$$

$$81 - 1 = \mathbf{80}$$

Answer 4

every line has 3 possibility

1) no fault , 2) stuck at 0 , 3) stuck at 1 so as the N lines the total  no of faults = 3^N and now telling   total number of distinct multiple stuck−atstuck−at faults = total no of faults - no line faults = 3^N -1 SO ans is B one more here assuming N = 3 then L1,L2,L3 so , possible 1->ONLY  L1 STUCK AT 0 , 2--> ONLY L2 STUCK AT 1 3--> 3 FAULTS , 4---> L1 STUCK AT 0 AND L3 STUCK AT 1 ALL ARE POSSIBLE BUT no faults is not posible.

Answer 5

Watch full video solution by deepak sir