How Many Guards Are Needed to Cover Every Aisle in a Grid‑Shaped Supermarket?

Problem

Consider a supermarket or exhibition hall with m rows and n columns of aisles. Each guard can watch the aisle directly in front of them and the aisles to the left and right (three directions). What is the minimum number of guards required to monitor all aisles?

Modeling

We abstract the rows and columns as horizontal and vertical lines, forming a grid with m horizontal lines and n vertical lines.

Let the minimum number of guards be g . We first study lower bounds for g .

Lower Bound 1

Proposition 1: g ≥ m + n − 1. Proof: a guard cannot watch aisles belonging to different rows and different columns simultaneously; therefore at least one guard is needed for each row and each column, minus the overlap at a corner.

Lower Bound 2

Proposition 2: g ≥ ⌈(m + n)/2⌉. Proof: a guard placed on the border can watch two lines, while a guard inside the grid can watch at most one and a half lines. Even if four border guards each watch two lines, the remaining guards watch at most one and a half lines, leading to the stated bound.

Construction (Upper Bound)

We construct guard placements that achieve the upper bound, considering several cases.

Case 1. When m ≤ 2 n and n ≤ 2 m , place two guards in each column facing each other, ensuring they occupy different rows. These guards cover all columns and rows. Then use additional guards to cover any remaining rows, resulting in a total of ⌈(m + n)/2⌉ guards.

Case 2 (1). If the remaining number of rows is at least twice the remaining number of columns, apply the method of Case 1 to the reduced sub‑grid, requiring ⌈(remaining m + remaining n)/2⌉ guards, which again equals ⌈(m + n)/2⌉.

Case 2 (2). Repeatedly select a pair of rows and a column (or a pair of columns and a row) and place two guards facing each other. Continue this alternating process until the numbers of rows and columns differ by at most one. This leads to three sub‑cases:

(i) No rows or columns left: total guards = ⌈(m + n)/2⌉.

(ii) No rows but one column left: an extra guard is needed, still giving ⌈(m + n)/2⌉.

(iii) One row and one column left: two guards facing each other are required, again yielding ⌈(m + n)/2⌉.

Case 3. The remaining situation reduces to the previous cases and can be proved similarly.

Combining all cases, the final result is g = ⌈(m + n)/2⌉ , where ⌈·⌉ denotes the smallest integer not less than the argument.

Source: Shen Wenxuan, Yang Qingtiao, “Mathematical Modeling Attempts”.