Rectangle searches: detailed proofs

13 Sep 2026

The active manuscript concerns two-dimensional rectangles, constant daily budgets, and full initial uncertainty. Exact evaluators are distinguished from the intended explicit value-and-strategy endpoint. The complete classification remains open.

Rectangle overview · Progress reconciliation · Coverage and remaining gaps · Parked companion · PDF from the same source

Introduction and results

A princess moves through a building every night. Each morning a searcher may open several doors. The princess knows the search plan, may start anywhere, and must move to an adjacent room after each unsuccessful day. The problem is to guarantee capture as quickly as possible. Even on a single corridor the answer has a parity correction: dividing the amount of uncertainty by the apparent daily progress is not always enough.

This is a minimum-time version of the Hunters and Rabbit game. Our active objective concerns two-dimensional rectangles only. A path $P_n$ has $n$ vertices, and $P_{n_1}\mathbin{\square}\cdots\mathbin{\square}P_{n_d}$ denotes the Cartesian box with those side lengths. Write $T_m(G)$ for the optimal guaranteed number of inspection days, with value $\infty$ when no finite guarantee exists. Section 2 specifies the order of inspection and compulsory movement precisely.

The fixed completion criterion

For every $a,b\ge1$ and constant daily budget $k\ge0$, the numerical research goal is a fixed-size closed-form expression for $T_k(a,b)$, including its infinite cases. Evaluation must use an absolute $O(1)$ number of standard numerical operations, independent of $a,b,k$. Arithmetic, powers, roots, floors, ceilings and a fixed finite case list are permitted. This is an operation-count goal, not constant bit complexity. Parameter-length sums or products, recurrences, iterative arrays, shortest paths and parameter-dependent preprocessing do not satisfy it. Renaming an algorithm as one operation does not change this. We do not claim that the goal has been attained or is necessarily attainable.

A separate requirement is a directly specified optimal sequence $S_t(a,b,k)$ when the answer is finite, with proofs of capture and of minimality against every competing inspection sequence. Printing the sequence need not take $O(1)$ time. Strategy existence, reconstruction by optimization, and direct inspection rules are distinguished below. The graph notation $T_m(G)$ and the local width/length letters in older proofs are retained, with $T_k(a,b)=T_k(P_a\mathbin{\square}P_b)$ and $w=\min(a,b)$, $n=\max(a,b)$.

Relevant exact evaluators, lower and upper bounds, counterexamples, partial-state arguments and general proof tools remain in this paper. Their inclusion records progress; it does not lower the completion criterion. Independent higher-dimensional classifications and applications are preserved at https://angelraychev.com/princess/extensions/ with a separate manuscript, sources, formalization map and parked restart notes. Scope selection is not mathematical unification, and this separation establishes no new cases.

Current rectangle coverage

Feasibility already has a bounded numerical criterion: $$T_k(a,b)<\infty \quad\Longleftrightarrow\quad k\ge\left\lfloor\min(a,b)/2\right\rfloor+1.$$ For both sides at least two this is the rectangular-grid theorem of Abramovskaya et al. (2016, Theorem 2); paths and the one-room case are covered separately below. Thus the infinite-value cases do not remain an open part of the rectangle classification.

Fixed numerical formulas and attaining constructions are available for all budgets on rectangles with at most five rows, and above the stated quadratic budget thresholds at every width and side parity. Every seven-row odd-length budget is now covered (Theorem 30.2), as is the even-width budget curve $k=r(r-1)$ on width $2r$, $r\ge3$, at every length (Theorem 31.4). The finite constants in the minimum-budget theorem also give fixed formulas at its listed widths through fifteen. These are proved ranges, not a complete arbitrary-width classification.

Every odd rectangle has exact compatible neighborhood profiles and an exact joint evaluator. Theorem 6.1 places its time in $\{2\tau-1,2\tau\}$; the bounded joint frontier in Theorem 7.1 decides which value occurs. The solo-residual rule suffices beyond the explicit threshold in Theorem 7.5 and at every length in the additional ranges of Theorem 30.5 and Corollary 30.6. In general these recurrences still require reduction to bounded numerical expressions. Even the all-width minimum- budget identity $T_{b+1}(2b+1,n)=2(2b+1)n-C_{2b+1}$, for odd $n\ge2b+1$, retains a width-only $O(b)$ clock in $C_{2b+1}$ (Theorem 21.1). It is an exact general theorem, but not numerical completion when $b$ varies.

For even-area rectangles, exact static neighborhood profiles and the physical interface theorem 27.1 retain the actual boundary choices. The symbolic transition theorem 13.3 evaluates the interior connections. Parameter-dependent boundary preprocessing and shortest-path optimization remain. The constants hidden in $O_{w,k}(1)$ are not an absolute $O(1)$ bound independent of all three parameters.

Uniform bounds also narrow a broad even-area region to one day: Theorem 29.19 covers $k\ge\lceil4w/3\rceil$, and Corollary 29.21 improves the threshold to $\lceil13w/10\rceil$ for even widths. The physical upper strategies are explicit, while choosing the optimal endpoint and evaluating every underlying clock in fixed size remain separate obligations.

The common corner-capacity and propagation arguments remain as tools for these gaps. The target is the optimum from the full rectangle. Universal optimality from every partial state, or classification of every legal boundary transition, is not an additional completion condition.

The exact narrow-grid formulas

On a path, $T_m(P_n)=1$ if $n\le m$. With one inspection per day, $T_1(P_2)=2$ and $T_1(P_n)=2n-4$ for $n\ge3$. For $n>m\ge2$, $$T_m(P_n)=\left\lceil\frac{2n-4}{2m-1}\right\rceil+\varepsilon,$$(1) where $\varepsilon=1$ exactly when $n\equiv m+1\pmod{2m-1}$ and $n,m$ are not both even. This theorem is the domain-corrected result of the author’s original 2019–2020 work. We give a shorter construction and a matching-based lower proof, and formalize the complete statement in Lean.

For two rows and $n\ge2$, one daily inspection is insufficient, and $m\ge2n$ gives one day. In the remaining range put $N=n-1$, $M=m-1$. Then $$T_m(P_2\mathbin{\square}P_n)=\left\lceil\frac{2N}{M}\right\rceil+\mathbf{1}_{\{M\text{ even and }N\equiv M/2\pmod M\}}.$$(2)

For three rows and $n\ge2$, the one-day threshold is $3n$, the two-day threshold is $\left\lfloor 3n/2\right\rfloor$, and one inspection is insufficient. For $2\le m<\left\lfloor 3n/2\right\rfloor$, write $3n-4=q(2m-3)+r$, $0\le r<2m-3$. The answer is $$\begin{cases} 2q,&r=0,\\ 2q+1,&r>0\text{ and }m\ge r+4-\mathbf{1}_{\{n\text{ even},\ q\text{ odd}\}},\\ 2q+2,&\text{otherwise}. \end{cases}$$(3)

For four rows and $n\ge4$, the one-day threshold is $4n$, the two-day threshold is $2n$, and budgets at most two are insufficient. For $3\le m<2n$, write $2n-2=q(m-2)+r$, $0\le r<m-2$. The answer is $$\begin{cases} 2q,&r=0,\\ 2q+1,&r=1\text{ or }(r\ge2\text{ and }m\ge2r+4),\\ 2q+2,&\text{otherwise}. \end{cases}$$(4) Rotating a shorter four-row board reduces it to a preceding family. In particular the minimum feasible budgets give $T_2(P_3\mathbin{\square}P_n)=6n-8$ and $T_3(P_4\mathbin{\square}P_n)=4n-4$ in their stated nondegenerate ranges. For five rows and $n\ge5$, the minimum feasible budget is three, and $$T_3(P_5\mathbin{\square}P_n)=10n-20.$$(5) The even-length proof uses a finite symbolic boundary certificate valid for every length, together with a history-dependent potential. The odd-length proof follows from the explicit neighborhood profiles. For every even $n\ge6$, putting $h=5n/2$ also gives $$T_4(P_5\mathbin{\square}P_n)=2\left\lceil\frac{2h-8}{3}\right\rceil.$$ Theorem 19.5 gives a closed quotient-and-remainder formula for every larger budget on these even-length boards. Theorem 19.7 supplies the closed answer for every odd length as well. In particular, four inspections per day take $2\left\lceil(5n-9)/3\right\rceil+2\mathbf{1}_{\{3\mid n\}}$ days when $n\ge5$ is odd. Together with rotation of shorter boards, these give explicit formulas and attaining strategies for every five-row board and every budget. The wider odd-rectangle theorem extends the closed analysis to every width $2b+1$ when $m\ge b^2+1$.

Shared proof tools and proof status

The common difficulty is temporal. A smallest next neighborhood need not contain an equally favorable survivor for the following day. Whole- strategy compression, attained inverse-profile arithmetic, corner capacities, physical propagation and efficient-frontier arguments address different parts of that obstruction. General statements are retained where they are natural dependencies of rectangle proofs; their independent box applications are in the parked companion.

The exact fixed-deadline minimum constant budget is an inverse formulation of the same capture relation. Section 28 therefore retains its rectangle consequence and proof. It is not silently turned into a varying-budget objective.

Ordinary proofs, independent finite checks and physical-game Lean verification are different evidence layers. Section 32 states the precise boundary. A compiled collection of reusable components does not formally verify every unbounded theorem appearing here.

Prior work and provenance

Britnell and Wildon (Britnell and Wildon 2013) studied the princess puzzle with one daily inspection, including the path value $2n-4$. Haslegrave studied the associated evasion game (Haslegrave 2014); related moving- target search appears in Beluhov and Kolev (Beluhov and Kolev 2017). Abramovskaya, Fomin, Golovach, and Pilipczuk (Abramovskaya et al. 2016) developed Hunters and Rabbit results, including the rectangular-grid feasibility threshold $\left\lfloor\min(a,b)/2\right\rfloor+1$. Bolkema and Groothuis proved isoperimetric nesting and the hunting number for hypercubes (Bolkema and Groothuis 2019). We use precise versions of these results; minimum-time claims do not follow from feasibility alone. Parity-restricted boundary minimization on the binary cube goes back to Körner and Wei (Körner and Wei 1984). Compression proofs and local-to-global principles have a substantial earlier literature, including Bezrukov and Serra (Bezrukov and Serra 2002); their closed-neighborhood theorem is distinct from the open-neighborhood argument given here.

Dmitry Kamenetsky recorded conjectural two- and three-inspection path formulas in March 2018 (Kamenetsky 2018a, 2018b). Equation (1) proves those special cases and extends them to arbitrary budgets. The author’s independent path work took place between October 2019 and March 2020 and was written in two Bulgarian conference manuscripts (Raychev and Rusev 2020; Raychev 2020). The one-probe restriction omitted from a printed general formula is made explicit here. The original conference documents are preserved.

The time-budget inverse parameter is also considered in recent work (Ben-Ameur et al. 2026); we do not claim the general optimization question as new. Recontamination can matter substantially on general graphs (Dissaux et al. 2025), so a presumed monotone search is never used as an unproved lower-bound assumption. The parked companion separately records the classical closed-neighborhood isoperimetry used for its higher-dimensional applications. Those applications do not supply the open-neighborhood argument for odd rectangles.

The game and its possible positions

Let $G=(V,E)$ be a finite simple graph without isolated vertices, and let $m\geq1$ be the daily inspection budget. Every connected board with at least two rooms satisfies this graph assumption; a one-room board takes one inspection and is treated separately. The target chooses an unknown initial vertex. On day $t=1,2,\ldots$, the searcher inspects a set $S_t\subseteq V$ with $|S_t|\leq m$. If the target occupies a vertex of $S_t$, it is caught. Otherwise it must move along exactly one edge before the next day. Inspections within a day are simultaneous. The searcher receives no information about an unsuccessful inspection other than the miss.

Write $T_m(G)$ for the minimum number of days in which capture can be guaranteed, and put $T_m(G)=\infty$ if there is no finite guarantee. For positive rectangle side lengths define $$T_k(a,b):=T_k(P_a\mathbin{\square}P_b)=T_k(b,a).$$ The daily inspection set is $S_t(a,b,k)$, with $|S_t(a,b,k)|\le k$. We use $k$ for the global budget and retain the legacy letter $m$ in individual proofs; locally $w=\min(a,b)$ and $n=\max(a,b)$. The separate no-inspection convention is $T_0(a,b)=\infty$, including the one-room board: inability to move is not capture. This convention is not derived from a vacuous target-walk quantifier. The associated feasibility threshold is $$h(G)=\min\{m\geq1:T_m(G)<\infty\}.$$ We consider deterministic guarantees. Before capture, every observation is a miss. Thus an adaptive strategy has only one continuing observation history and is represented by a sequence $(S_t)_{t\geq1}$. This sequence formulation does not restrict the searcher’s guaranteed performance.

For $A\subseteq V$, its open neighborhood is $$N(A)=\{v\in V:\text{some }u\in A\text{ satisfies }uv\in E\}.$$ Define the possible-position sets immediately before inspection by $$B_1=V,\qquad B_{t+1}=N(B_t\setminus S_t).$$ The following elementary interpretation is used in every subsequent argument.

Since $G$ has no isolated vertices, a nonempty set has a nonempty open neighborhood. Hence the capture condition is also equivalent to $B_{t+1}=\varnothing$. We use this equivalent form only under that hypothesis. A board with a single room is handled directly: one inspection on the first day suffices. Thus an inability to make a move is never silently treated as capture.

Two monotonicity observations will be useful. Starting from fewer possible positions cannot make a fixed inspection sequence less successful, and adding inspected vertices cannot make it less successful. Both follow by induction from monotonicity of $N$ and set difference in their respective arguments. In particular, probes outside the current possible-position set may be wasted, but they cause no problem for the model or the lower bounds.

Two initial parity classes

Suppose $G$ is bipartite, with vertex classes $V_0,V_1$. Keep track of the two possible initial colors separately: $$R^s_1=V_s,\qquad R^s_{t+1}=N(R^s_t\setminus S_t),\qquad s\in\{0,1\}.$$ Then $$B_t=R^0_t\mathbin{\dot\cup}R^1_t, \qquad R^s_t\subseteq V_{s+t-1\pmod2}.$$ Indeed, neighborhood and deletion distribute over unions, and every edge reverses color. The two sets therefore stay disjoint while exchanging their current colors each night. Allocations to the two initial classes sum to at most the day’s inspection budget. We will state explicitly whether a pair of counts is indexed by initial color or by current color; the latter convention swaps the two counts after every move.

This separates the bookkeeping common to the path, ladder, and grid arguments. The work specific to a graph is to determine how small a neighborhood can be after a given number of inspections, and when a sequence of such bounds can actually be attained.

Compressing entire strategies

An isoperimetric inequality bounds one neighborhood. To preserve an optimal search, the replacement sets must also respect containment and remain compatible after successive moves. The following criterion provides that stronger conclusion.

Products and simultaneous compression

Compositions of strategy compressions are strategy compressions, since $$N(C(D(S)))\subseteq C(N(D(S)))\subseteq C(D(N(S))).$$ Suppose finitely many such operators strictly decrease a common nonnegative integer potential whenever they change a set. If that potential has a uniform upper bound $B$, cycling through all operators $B+1$ times reaches a common fixed point for every input. A cycle with a change decreases the potential, and a cycle without a change fixes every operator. The resulting map is a composition with a uniform number of factors, hence is monotone and cardinality preserving; it is also idempotent. This avoids assuming that an input-dependent stopping rule preserves monotonicity.

Odd path fibers

For several odd coordinates, combine their lifted operators. Every changing operation decreases the sum of coordinates, so simultaneous compression has the normal form of Theorem 3.2. Its fixed sets satisfy $v\in S\implies v-2e_i\in S$ whenever the latter vertex belongs to the box. These are lower ideals separately in each coordinate-parity pattern. They need not be lower ideals in the whole checkerboard color: for example, $\{(1,1)\}$ in a $3\times3$ square is fixed by the two path operators but does not contain $(0,0)$.

Exact recurrences on odd cylinders

For the rectangle objective take $H=P_w$ below. The prefix-fiber argument is retained in its natural generality as an exact evaluator; independent non-rectangle applications are parked in the companion.

Let $G=H\mathbin{\square}P_{2q+1}$, where $H$ is any finite graph and $q\geq1$. The product lift and Theorem 3.2 give an exact normal form from the full board. It uses two vectors indexed by $V(H)$: $a_v^0$ counts even path coordinates in fiber $v$, and $a_v^1$ counts odd path coordinates. Their ranges are $$0\leq a_v^0\leq q+1,\qquad0\leq a_v^1\leq q.$$ Thus they refer to the parity of the path coordinate, and do not require $H$ to be bipartite. Define $$\phi_0(k)=\min(k,q),\qquad \phi_1(k)=\begin{cases}0,&k=0,\\k+1,&k>0.\end{cases}$$ For survivor vectors $b^0\leq a^0$, $b^1\leq a^1$, the exact next state $F(b)$ is $$\begin{aligned} F(b)^0_v&=\max\left(\phi_1(b_v^1),\max_{u\sim v}b_u^0\right),\\ F(b)^1_v&=\max\left(\phi_0(b_v^0),\max_{u\sim v}b_u^1\right), \end{aligned}$$(9, 10) with an empty maximum interpreted as zero. Path edges supply the first term, and $H$-edges the second. All contributions in a fiber are prefixes of the same parity, so their union has exactly the maximum length. The required number of inspections is $$d(a,b)=\sum_{v\in V(H)}(a_v^0-b_v^0+a_v^1-b_v^1).$$ They are realized by inspecting the removed suffix of each prefix.

For a fixed budget $m$, form an edge $a\to F(b)$ whenever $b\leq a$ and $d(a,b)\leq m$. Then $T_m(a)$ is exactly the shortest-path distance to zero in this state graph, or infinity if zero is unreachable. Equivalently, $$T_m(a)=1+\min_{\substack{b\leq a\\d(a,b)\leq m}}T_m(F(b)), \qquad T_m(0)=0,$$(11) where the shortest-path interpretation specifies the solution of the possibly cyclic equations. For all budgets simultaneously, let $W_t(a)$ be the least constant budget that wins within $t$ days. Then $$W_{t+1}(a)=\min_{b\leq a}\max\{d(a,b),W_t(F(b))\},$$(12) with $W_0(0)=0$, $W_0(a)=\infty$ for $a\ne0$. Backpointers in either recurrence give actual inspection sets.

If $A=|V(H)|$, the number of states is exactly $$K=((q+1)(q+2))^A\leq(2q+2)^{2A}.$$ There are at most $K^2$ state–survivor pairs. Explicit construction of their transitions takes $O((A+|E(H)|)K^2)$ elementary operations, apart from integer bit costs. For fixed $H$, this is polynomial in the odd longitudinal length. Any successful path can have cycles removed, so a finite optimum is at most $K-1$. This proves an exact algorithm, not a uniform polynomial bound in dimension or a closed time formula.

When $H$ is bipartite, one may instead index vectors by global color. For a coloring $\chi$, put $\varepsilon_p(v)=p-\chi(v)\pmod2$. A single current color has transition $$[\Phi_p(b)]_v=\max\left(\phi_{\varepsilon_p(v)}(b_v), \max_{u\sim v}b_u\right).$$ The two current-color vectors then become $(\Phi_1(b^1),\Phi_0(b^0))$. This convention is useful when comparing the cylinder recurrence with the two-color grid arguments below.

Square fibers and equal-sided boxes

Abramovskaya, Fomin, Golovach and Pilipczuk (Abramovskaya et al. 2016, sec. 3.1, Lemma 2) prove that diagonal shifts do not increase the neighborhood size of a one-color set in a square. The following fiber calculation strengthens the scalar comparison to (8) and applies it to both colors. That stronger statement is what allows whole strategies to be compressed.

One quadrant profile for every forbidden initial triangle

The square-root and pronic-root bounds have a common extension that retains prescribed omissions near a corner. Neighborhoods below are always taken in the whole nonnegative quadrant. Forbidden rooms constrain the support; they are not deleted from the graph.

For $h=0$ and $h=1$ the formula gives respectively $\left\lceil\sqrt{k}\right\rceil$ and the least $s$ with $k\le s(s-1)$. The case $h=2$ forbids the even origin; $h=3$ forbids both odd neighbors of the origin. These exact static profiles do not assert that their minimizers can be chained inside arbitrary earlier beliefs.

Each $C_h$ in (13) is the maximum of two convex quadratics and is nondecreasing on $\mathbb{N}$. The lemma therefore optimizes sums of any two punctured-quadrant root costs without searching their allocation interval. It also applies to the capacities $s(s+1)$ and $s^2$ used in the inverse-profile calculation below.

Exact neighborhood profiles on odd rectangles

Let $G=P_{2a+1}\mathbin{\square}P_{2b+1}$, where $a\geq b\geq1$, with coordinates $(x,y)$; thus $x$ is the long coordinate. Write $V_0,V_1$ for its even and odd checkerboard classes, and $$E=|V_0|=\frac{|G|+1}{2},\qquad M=|V_1|=E-1.$$ Define the two open-neighborhood profiles by $$g_p(k)=\min\{|N(S)|:S\subseteq V_p,\ |S|=k\}.$$ It is convenient to use the integer functions $$R(k)=\left\lceil\sqrt{k}\right\rceil,\qquad Q(k)=\min\{r\geq1:k\leq r(r-1)\}.$$ In particular $R(0)=0$ and $Q(0)=1$.

The order fills the short direction first within a diagonal. Its direction is significant on an unequal rectangle. For example, the opposite tie order on $7\times5$ gives the five-element even prefix $\{(0,0),(0,2),(1,1),(2,0),(4,0)\}$, with eight neighbors; the set $\{(0,0),(0,2),(0,4),(1,1),(1,3)\}$ has seven.

Quadrant bounds

Apply the odd-coordinate compressions of Lemma 3.4 in both directions. Their common fixed sets are lower closed under decreasing either coordinate by two, and compression does not increase the neighborhood size. We may therefore assume that each coordinate-parity pattern of $S$ is a lower Ferrers diagram. Let $e_i$ and $o_i$ be the selected counts in rows $y=2i$ and $y=2i+1$, respectively. These are separately nonincreasing sequences. For source color $0$ they count even-$x$ and odd-$x$ vertices, whereas for source color $1$ they count odd-$x$ and even-$x$ vertices.

The two far edges

Lower bounds in Theorem 5.1

Let $S\subseteq V_0$, $|S|=k>0$, and put $\delta=|N(S)|-k$. If $\delta\geq b$ the desired lower bound is immediate. Otherwise Lemma 5.3 leaves two possibilities. With no clipping, $k\leq\delta^2$. With both far edges occupied, let $T$ be the reflected opposite-color complement of $N(S)$. It has size $t=M-k-\delta$. Before reflection, its neighborhood is contained in $V_0\setminus S$, so its quadrant surplus is at most $\delta+1$. For $\delta\geq1$, Lemma 5.2 gives $$M-k-\delta=t\leq\delta(\delta+1),\qquad k\geq E-(\delta+1)^2.$$(5.3) If $\delta=-1$ or $0$, $T$ must be empty, since a nonempty quadrant color-$1$ set has surplus at least two. This yields respectively $k=E$ or $k=M$, the same conclusion. No smaller $\delta$ is possible: pairing along each row, then vertically in the unpaired last column, gives a matching covering all vertices except the far even corner, and hence $|N(S)|\geq k-1$. In all cases, $$\delta\geq\min\{R(k),b,R(E-k)-1\}.$$

For $S\subseteq V_1$, the same matching gives $\delta\geq0$. Below $b+1$, the unclipped case gives $k\leq\delta(\delta-1)$. In the complement case, $T$ has size $E-k-\delta$ and quadrant color-$0$ surplus at most $\delta-1$. The case $\delta=0$ is impossible: $T$ is nonempty because $k\leq M<E$, but would have negative surplus. For $\delta\geq1$, $$E-k-\delta\leq(\delta-1)^2,\qquad k\geq M-\delta(\delta-1).$$ The unclipped nonempty case also has $\delta\geq1$. Thus $$\delta\geq\min\{Q(k),b+1,Q(M-k)\}.$$ These prove the lower bounds in both formulas.

For comparison, the two exact profiles of any bipartite graph obey the complement-inverse identity $$g_1(y)=E-\max\{x:g_0(x)\leq M-y\}.$$(20) Indeed, the existence of nonadjacent sets of sizes $x$ and $y$ in the two colors is equivalent to $g_0(x)\leq M-y$, and also to $g_1(y)\leq E-x$. Thus the second formula can alternatively be checked from the first by exact inversion.

Attainment and neighborhood nesting

The vertices on diagonal $x+y=d$ have $x$ in the interval $$L_d=\max(0,d-2b)\leq x\leq\min(2a,d),$$ whose length is $$\ell(d)=\min(2a,d)-\max(0,d-2b)+1, \qquad0\leq d\leq2a+2b.$$ A nonempty prefix ends after $j$ vertices of diagonal $d$, for some $1\leq j\leq\ell(d)$, and has size $$k=\sum_{\substack{s<d\\s\equiv d\pmod2}}\ell(s)+j.$$(21) All earlier opposite-color diagonals belong to its neighborhood. On diagonal $d+1$, each selected $x$ contributes $x$ or $x+1$ when the corresponding step stays inside the board. Their union is the initial interval there, of length $$f(d,j)=j+1-\mathbf{1}_{\{d\geq 2b\}}-\mathbf{1}_{\{L_d+j-1=2a\}}.$$(22) The first indicator removes the unavailable step past the short-direction boundary, and the second removes the step past the long-direction boundary. At the far corner both are present and $f=0$. The initial minority diagonal $d=1$ additionally covers the corner on diagonal zero, already included among the earlier opposite diagonals. Consequently $$|N(I_p(k))|=\sum_{\substack{s<d\\s\not\equiv d\pmod2}}\ell(s)+f(d,j),$$ and this neighborhood is exactly a prefix of the other color.