Question:

In the $4\times 4$ array shown, each cell of the first three columns has either a cross (X) or a number as per the rule:
\includegraphics[width=0.5\linewidth]{2.png}
A number equals the count of crosses in its $8$ neighboring cells (left, right, top, bottom, and diagonals). The fourth column is empty. As per this rule, the \emph{maximum} number of crosses possible in the empty column is

Show Hint

When a grid obeys a "neighbor-count" rule, convert each unknown cell to a binary variable and write linear equations from adjacent numbered cells. Solving these quickly gives both feasibility and the maximum/minimum counts requested.
Updated On: Aug 22, 2025
  • 0
  • 1
  • 2
  • 3
Hide Solution
collegedunia
Verified By Collegedunia

The Correct Option is C

Solution and Explanation

Step 1: Notation. Let the cells in the empty (fourth) column from top to bottom be \[ a=\text{(row1,col4)},\quad b=\text{(row2,col4)},\quad c=\text{(row3,col4)},\quad d=\text{(row4,col4)}, \] where each takes value $1$ if it is a cross (X), else $0$. Step 2: Use numbered cells that touch the empty column. - Cell $(1,3)$ has number $2$ and neighbors $\{(1,4)=a,\ (2,4)=b,\ (2,2)=X\}$ among crosses around it. Since $(2,2)$ is already a cross, \[ a+b+1=2 \;\Rightarrow\; a+b=1. \tag{1} \] - Cell $(2,3)$ has number $3$ and neighbors including two fixed crosses $(2,2)$ and $(3,2)$, and the fourth-column cells $a,b,c$. Hence \[ a+b+c+2=3 \;\Rightarrow\; a+b+c=1 \;\Rightarrow\; c=0 \quad\text{(using (1)).} \tag{2} \] - Cell $(3,3)$ has number $4$ and neighbors include three fixed crosses $(2,2)$, $(3,2)$, $(4,3)$ and the fourth-column cells $b,c,d$. Thus \[ b+c+d+3=4 \;\Rightarrow\; b+d=1. \tag{3} \] Step 3: Maximize crosses in the fourth column. We want to maximize $a+b+c+d$. From (2), $c=0$. From (1) and (3): \[ a=1-b,\qquad d=1-b. \] Therefore \[ a+b+c+d=(1-b)+b+0+(1-b)=2-b, \] which is maximized when $b=0$. Then $a=1,\ c=0,\ d=1$, yielding \[ a+b+c+d=2. \] \[ \boxed{2} \]
Was this answer helpful?
0
0

Questions Asked in GATE XH- C3 exam

View More Questions