How Long Can the Escaping Ant Be Confined?
June 25, 2026
Abstract
Langton’s ant is a simple two-dimensional cellular automaton whose long-term behavior exhibits remarkable complexity. While it is known that the ant eventually escapes any finite connected region of the grid, the quantitative aspects of this escape remain poorly understood. In this paper, we study the escaping time of Langton’s ant, defined as the maximum number of steps the ant can perform within a finite connected domain before leaving it.
We establish general upper bounds on the escaping time as a function of the domain size, and derive improved bounds for rectangular domains. In particular, we obtain a factorial upper bound for square domains via an inductive decomposition argument. We also obtain linear upper bounds for rectangular domains of height two and three via a column-by-column analysis. More generally, for rectangular domains with a fixed height, we establish a polynomial upper bound in the number of columns. These results are complemented by exact values computed through an optimized simulation algorithm that exploits the geometric symmetries of the grid and employs a backtracking branching strategy to avoid exhaustive search over all color configurations. We also provide lower-bound constructions, proving that the linear upper bounds for rectangular domains of heights two and three are asymptotically optimal.
1 Introduction↩︎
Many natural and artificial systems can be modeled as collections of simple interacting elements evolving over discrete time. Each element updates its state according to local rules that depend only on a small neighborhood, yet the repeated application of these rules can generate complex global behavior. Understanding how such macroscopic patterns arise from microscopic interactions, often referred to as emergence, is a central question in the study of discrete dynamical systems.
A classical example of emergence in a discrete dynamical system is Langton’s ant, a two-dimensional cellular automaton introduced by Christopher G. Langton in 1986 in the context of artificial life [1]. Langton’s ant is defined on the infinite square grid whose cells are in one of two states: black (turn-left) or white (turn-right). The ant occupies a cell and has an orientation among the four cardinal directions. At each step, the ant turns left on a black cell and right on a white cell, flips the state of the cell, and moves forward to the adjacent cell in the new direction.
Despite the simplicity of these local rules, the trajectory of the ant exhibits highly unpredictable behavior. Starting from a uniformly white (or black) initial configuration, the ant’s trajectory shows rotational symmetry during the first 500 steps, followed by an apparently erratic phase lasting until around step 10 000, after which the trajectory suddenly becomes regular: the ant advances indefinitely along one of the four diagonal directions, tracing a periodic pattern of period 104 known as the highway (Figure 1). Numerical simulations consistently show that this highway emerges from any finite initial configuration (configuration in which all but a finite number of cells are in the same state), yet this experimental observation has never been formally established.
Beyond the standard two-dimensional square lattice, Langton’s ant has been studied on a variety of other regular structures and topologies, including one-dimensional lattices [2], [3], triangular and hexagonal grids [3], [4], infinite bi-regular and hyperbolic graphs, finite and planar graphs [5], twisted tori [6], and higher-dimensional lattices [7]. Those works show that the dynamical behavior of the ant is strongly influenced by the topology of the underlying graph. Generalizations have also been proposed along other axes: variants with a richer set of movements and multi-state extensions [8], [9].
While much attention has been devoted to the ant’s behavior on infinite grids, its dynamics on finite domains remain poorly understood. It is known that Langton’s ant eventually escapes any finite connected region of the grid, yet the quantitative aspects of this escape —and more broadly, the computational complexity of predicting its behavior on finite two-color grids— are still unclear. A natural and fundamental question thus arises: how long can the ant remain confined within a finite region before escaping? Bounding the escaping time provides insight into the complexity of reachability problems and prediction difficulty for the ant on finite domains.
The Present Work
This paper studies the escaping time of Langton’s ant on the standard two-color square grid from a quantitative perspective, without modifying the cell states or the underlying topology. Our contributions are as follows.
We first establish that, while confined to a finite connected domain, the same color configuration cannot appear twice in the ant’s trajectory. This immediately yields a general upper bound of \(2^d\) on the escaping time for any domain of \(d\) cells.
We then derive improved bounds depending on the shape of the domain. For square domains with \(n\) rows and \(n\) columns, an inductive decomposition into a boundary layer and interior yields a factorial upper bound \((n+1)!\). For rectangular domains of height two, a column-by-column analysis gives the linear bound \(6(n-1)\) for a grid with \(n\) columns, which is tight: we exhibit explicit configurations achieving exactly \(6(n-1)\) steps. For rectangular domains of height three, the same approach yields the linear bound \(10n-4\), with near-matching constructions. More generally, for fixed \(k\), an inductive argument gives for rectangular domains with \(k\) rows and \(n\) columns an upper bound \(\left(\frac{n+1}{\sqrt{2}}\right)^k\), which is polynomial in \(n\) for every fixed \(k\).
These results are complemented by exact escaping times computed for all rectangular grids up to size \(9 \times 9\), using an optimized simulation algorithm that exploits grid symmetries and a backtracking branching strategy, which in particular corrects and extends the OEIS sequence A282425 [10].
The remainder of this paper is organized as follows. Section 2 introduces the formal framework, definitions, and known results. Section 3 presents our general results on finite connected domains, including the proof that color configurations cannot repeat. Section 4 details our simulations (4.1), the inductive derivation of the square domain bound (4.2), the linear bounds for two-row (4.3.1) and three-row (4.3.2) rectangular grids and the inductive derivation of the bound of rectangular domain with fixed height (4.4).
2 Preliminaries↩︎
This section introduces the concepts, definitions, and notation that will be used throughout the paper.
2.1 Graph Representation and Transition Function↩︎
We represent the infinite grid as a planar directed graph \(G = (V, A)\), where the vertex set \(V = \mathbb{Z}^2\) corresponds to the cells, and \(A\) consists of arcs in both directions between vertices corresponding to adjacent cells (i.e. pairs of vertices differing by exactly one unit in exactly one coordinate). See Figure 2 for an illustration, where each pair of opposite arcs is represented as single undirected edge. In this representation, the position of the ant (the cell it occupies and its orientation) is encoded by an arc \((u,v) \in A\), specifying both the cell \(u\) from which the ant arrives and the cell \(v\) toward which it is heading. We identify vertices with cells of the grid and arcs with oriented positions of the ant. Thus, we may use ‘cell’ for vertices and ‘position’ for arcs.
In all figures cited in the remainder of this paper, black cells are in the \(L\) state and white cells in the \(R\) state. Gray cells represent cells whose state may be either \(L\) or \(R\) and is not yet fixed.
A color configuration of the grid is a function \(C : \mathbb{Z}^2 \rightarrow \{L,R\}\) assigning to each cell its state, where \(L\) denotes the turn-left state and \(R\) denotes the turn-right state. A configuration is a pair \((C, pos)\) consisting of a color configuration of the grid together with the position \(pos \in A\) currently occupied by the ant.
The global transition function \(T\) is defined by \(T(C, pos) = (C', pos')\), where, given \(pos = (u, v)\):
\(C'(w) = C(w)\) for all \(w \neq v\), and \(C'(v) = \overline{C(v)}\), where \(\overline{L} = R\) and \(\overline{R} = L\);
\(pos' = (v, w)\), where \(w\) is the neighbor of \(v\) obtained by turning right from the direction \((u \to v)\) if \(C(v) = R\), or turning left if \(C(v) = L\).
Applying \(T\) once corresponds to executing one step of the ant’s motion. See Figure 3 for an illustration of the application of transition function.
An important property is that the dynamics of the ant is deterministic and reversible, i.e. the transition function is bijective. Configurations at each time in the future and in the past are entirely determined by the current configuration. To determine the previous configuration, it is enough to invert the direction of the ant, to apply the transition function \(T\), and to invert once more the direction of the ant.
2.2 HV-partition Property↩︎
Another fundamental structural property of Langton’s ant is what we call the HV-partition property. The ant’s orientation alternates between horizontal and vertical, since its direction is rotated by a quarter turn at each step. Color the cells of \(G\) in a checkerboard pattern by assigning one color to all cells \((i,j)\) with \(i+j\) even, and the other color to those with \(i+j\) odd. If the ant starts in a horizontal orientation and is pointing toward a cell of the first color, then it will always be in a horizontal orientation when pointing toward a cell of that color, and in a vertical orientation when pointing toward a cell of the other color. This induces a natural partition of \(\mathbb{Z}^2\) into two classes, H-cells and V-cells: when the ant points toward an H-cell (resp.a V-cell), it arrives horizontally (resp.vertically) and departs vertically (resp.horizontally). See Figure 4 for illustration.
This partition of the cells induces a corresponding partition of the arc set \(A\) into two subsets \(A_H\) and \(A_V\), where \(A_H\) (resp.\(A_V\)) is the set of admissible positions of the ant when the origin cell \((0,0)\) is taken as an H-cell (resp.a V-cell). So according to the starting position of the ant the motion of the ant will be either supported by the graph \((\mathbb{Z}^2,A_H)\) (horizontal \(G\)) or \((\mathbb{Z}^2,A_V)\) (vertical \(G\)). In these graphs, every cell has exactly two incoming arcs and exactly two outgoing arcs.
2.3 Finite Connected Domain↩︎
We say that a finite set of cells \(V_D \subset \mathbb{Z}^2\) is connected if for any two cells \(u, v \in V_D\), there exists a sequence \(u = v_0, v_1, \ldots, v_k = v\) in \(V_D\) with \(k\in \mathbb{N}\) such that \(v_{i+1}\) is adjacent to \(v_i\) for every \(0\le i \le k-1\).
For any such set, we define the associated finite connected domain \(D = (V_D, A_D)\), where \(A_D\) consists of all arcs of \(A\) incident to at least one cell of \(V_D\). Three types of arcs in \(A_D\) can be distinguished: interior arcs: both endpoints in \(V_D\); in-boundary arcs: tail outside \(V_D\), head in \(V_D\) and out-boundary arcs: tail in \(V_D\), head outside \(V_D\).
The HV-partition of \(G\) restricts naturally to \(D\): the arc set \(A_D\) is partitioned into \(A_D \cap A_H\) and \(A_D \cap A_V\), identifying within \(D\) the admissible positions of the ant under each of the two partitions. We define horizontal \(D\) as \((V_D, A_D \cap A_H)\) and vertical \(D\) as \((V_D, A_D \cap A_V)\). Henceforth, unless stated otherwise, \(D\) refers to horizontal \(D\) (i.e \(A_D= A_D \cap A_H\)).
A cell of \(D\) is called a boundary cell if it is incident to at least one boundary arc (either an in-boundary or an out-boundary arc), and a corner cell if it is incident to both an in-boundary and an out-boundary arc. See Figure 5 for an illustration.
A color configuration of \(D\) is a function \(C_D: V_D \rightarrow \{L,R\}\), and a configuration of \(D\) is a pair \((C_D, pos)\), where \(pos \in A_D\). The ant is said to be confined in \(D\) as long as its position is an interior or in-boundary arc of \(D\), and it escapes \(D\) at the first step at which its position is an out-boundary arc of \(D\). The transition function \(T\) restricts naturally to \(D\).
Given an initial configuration \((C_0, pos_0)\) of \(D\) with \(pos_0=(v_0, v_1)\), for \(k\in \mathbb{N}\), we denote by \((C_k, pos_k)=T^k (C_0, pos_0)\) with \(pos_k=(v_k,v_{k+1})\), the configuration after \(k\) steps. The trajectory of the ant from \((C_0, pos_0)\) to \((C_k, pos_k)\) is the sequence of configurations \((C_i, pos_i)_{0 \le i \le k}\). The set of exited cells during this trajectory is the set \(\{v_i \mid 1 \le i \le k \}\) consisting of all cells that the ant leaves during its motion. The positions \(pos_0\) and \(pos_k\) are the starting and ending positions of the trajectory, respectively, and \(v_1\) and \(v_k\) are called the starting and ending cells.
The motion of the ant within \(D\) from \((C_0, pos_0)\) refers to any trajectory \((C_i, pos_i)_{0 \le i \le k}\) such that each \(pos_i\) is an arc of \(D\).
The number of steps performed by the ant within \(D\) starting from \((C_0, pos_0)\) is: \[S_D(C_0, pos_0) = \min\,\{k \in \mathbb{N} \mid v_{k+1} \notin V_D\},\] the number of steps during which it remains confined in \(D\). The escaping time of \(D\) is defined as: \[S_D = \max\,\{S_D(C_0, pos_0) \mid (C_0, pos_0) \text{ configuration of } D\},\] that is, the maximum number of steps the ant can perform within \(D\) over all initial configurations. The central question addressed in this paper is the following:
Escaping Time Problem. Given a finite connected domain \(D\) of the grid, what is the escaping time of \(D\)?
2.4 Related Work↩︎
The most fundamental result on Langton’s ant on the infinite square grid, due to Troubetzkoy [11], states that for any initial configuration, if the ant moves indefinitely, the set of cells exited infinitely often contains no corner cell. As a corollary [12], the ant’s trajectory is always unbounded (non-periodic). Consequently, the ant escapes any finite connected domain in a finite number of steps. The main objective of this paper is to quantify this escaping time.
The other main theoretical results concern the computational complexity of the ant. Gajardo, Moreira, and Goles [13] showed that Boolean circuits can be simulated within Langton’s ant by embedding logic gadgets into the initial color configuration of the grid, with the ant’s trajectory serving as the computational signal. This yields the \(\mathsf{P}\)-hardness under log-space reductions of the reachability problem: given an initial configuration, does the ant ever visit a specified target cell? By further composing these gadgets to simulate one-dimensional cellular automata, they established that Langton’s ant is computationally universal, which in turn implies the existence of undecidable problems about its trajectory.
When the ant is restricted to a finite domain, this reachability problem becomes decidable. But what is its precise complexity? In particular, is it \(\mathsf{P}\)-complete? If the escaping time was polynomially bounded, then reachability on finite grids can be decided by direct simulation in polynomial time, suggesting that the problem lies strictly within \(\mathsf{P}\).
Tsukiji and Hagiwara established \(\mathsf{PSPACE}\)-hardness results concerning the predictability and macroscopic behavior of the ant. On the square grid [4], by introducing a third cell state in which the ant moves straight ahead without changing the cell’s color, they proved that determining whether a given finite configuration is repeatable (i.e. the ant’s trajectory is bounded and eventually cycles through a finite sequence of configurations) is \(\mathsf{PSPACE}\)-complete. They also established the \(\mathsf{PSPACE}\)-hardness of this problem on a hexagonal grid. These results are obtained through a reduction from the Quantified Boolean Formula (QBF) evaluation problem. In a subsequent study on a twisted torus [6], they proved that it is \(\mathsf{PSPACE}\)-hard to determine whether the ant will ever visit almost all vertices or nearly none of them via a reduction from the Quantified Conjunctive Normal Form (QCNF) problem. The introduction of the third state on the square grid and the use of the twisted torus topology are crucial for these reductions. These break the standard HV-partition of the square grid and allows the ant to be "reversed", so that it can traverse arcs in both directions. This property is exploited in the reductions through the reversible behavior of the system.
On the standard two-color square grid, however, the HV-partition is a rigid structural constraint: the ant cannot be reversed, and every arc is traversed in a fixed direction. This raises the question of whether \(\mathsf{PSPACE}\)-hardness can be achieved without breaking the HV-partition, or whether every natural decision problem about the ant on the finite two-color square grid is solvable in polynomial time. Quantifying the escaping time is a necessary first step toward answering this question.
3 Escaping Time of Finite Connected Domains↩︎
Let \(D\) be a finite connected domain of \(d \in \mathbb{N}^*\) cells. Since each cell can be in one of two states, there are \(2^d\) color configurations of \(D\). By the HV-partition, each cell is the head of exactly two arcs in \(A_D\), giving \(2d\) admissible positions. Together with \(2^d\) possible color configurations, the total number of configurations of \(D\) is \(2d \cdot 2^d\). The unboundedness result ensures that the ant’s trajectory cannot be periodic within \(D\), so no configuration of \(D\) can be encountered twice in the trajectory of the ant within \(D\), and the escaping time of \(D\) is bounded by \(2d \cdot 2^d\). However, this bound is far from tight, and the following results provide a slight improvement.
Starting from a configuration of a finite connected domain \(D\), no color configuration of \(D\) can appear twice in the motion of the ant within \(D\).
Proof. Suppose, for contradiction, that some color configuration \(C_D\) appears twice during the ant’s motion within \(D\). Let \(Traj\) denote the trajectory of the ant between the first and second occurrences of \(C_D\). Since the successive positions of the ant during its trajectory form a connected path, the set of exited cells during \(Traj\) induces a finite connected subdomain of \(D\), which we denote by \(D'\). As the configuration \(C_D\) is identical at the beginning and end of \(Traj\), the state of each cell in \(D'\) must be flipped an even number of times during \(Traj\). Consequently, the ant must exit each cell of \(D'\) a positive even number of times. The contradiction follows from the two claims below.
Claim 1. Every corner cell of \(D'\) is either a starting cell or an ending cell of \(Traj\).
Claim 2. \(D'\) has at least three distinct corner cells.
Claims 1 and 2 together imply that the trajectory \(Traj\) has at least two distinct starting cells or at least two distinct ending cells, contradicting the fact that each ant trajectory has a unique starting and a unique ending cell. Thus, no coloring of \(D\) can appear twice during the ant motion within \(D\).
Proof of Claim 1. Every cell of \(D'\) has exactly two incoming arcs and exactly two outgoing arcs. Let \(v_c\) be a corner cell of \(D'\), and let \(b_{in}\) and \(b_{out}\) denote respectively an in-boundary arc and an out-boundary arc of \(D'\) incident to \(v_c\). We denote by \(a_{in}\) the other incoming arc of \(v_c\), and by \(a_{out}\) the other outgoing arc of \(v_c\). See Figure [fig:cornercell95a].
Since the state of \(v_c\) alternates at every visit, for the ant to exit \(v_c\) a positive even number of times, it must exit exactly twice, in one of these two possible ways:
The ant enters once via \(a_{in}\) and once via \(b_{in}\), and exits both times via \(a_{out}\) (Figure [fig:cornercell95b]). Then \(b_{in}\) must be the starting position of \(Traj\), so \(v_c\) is a starting cell.
The ant enters twice via \(a_{in}\), and exits once via \(a_{out}\) and once via \(b_{out}\) (Figure [fig:cornercell95c]). Then \(b_{out}\) must be the ending position of \(Traj\), so \(v_c\) is an ending cell.
In both cases, \(a_{in}\) and \(a_{out}\) are interior arcs of \(D'\), since \(Traj\) cannot have two starting positions or two ending positions.
Proof of Claim 2. Without loss of generality, assume \(v_c\) is the topmost among the leftmost cells of \(D'\). By Claim 1, the two possibilities for the ant to exit \(v_c\) a positive even number of times involves \(a_{in}\) and \(a_{out}\) as interior arcs, so \(D'\) contains at least one cell to the right of \(v_c\) and at least one cell below \(v_c\). Consequently, the topmost among the rightmost cells of \(D'\) and the leftmost among the bottommost cells of \(D'\) are both distinct from \(v_c\) and from each other, giving at least three distinct corner cells of \(D'\).
This completes the proof of Proposition [pr:no95repeated95coloring]. ◻
Corollary 1. For any finite connected domain \(D\) of \(d \in \mathbb{N}^*\) cells, one has \(S_D \le 2^d\).
Proof. Suppose, for the sake of contradiction, that the ant is confined in \(D\) for more than \(2^d\) steps. Since there are exactly \(2^d\) distinct color configurations of \(D\), the pigeonhole principle implies that some coloring \(C_D\) must occur at least twice during the ant’s motion within \(D\). This contradicts Proposition [pr:no95repeated95coloring]. ◻
This bound is, however, also far from being achieved in practice. In the following sections, we present simulation results on the escaping time over rectangular domains, which suggest that the true maximum grows significantly slower than \(2^d\), and we establish rigorous upper bounds for square connected domains and some rectangular connected domains.
We end this section by pointing out that:
In order to maximize the number of steps performed within a finite connected domain \(D\), the ant must start from an in-boundary arc of \(D\).
Indeed, if the maximal number of steps were achieved by an ant starting from an interior arc, then, by reversibility of the transition function, this number could be extended, contradicting maximality.
4 Escaping Time of Square and Rectangular Connected Domains↩︎
We now focus on rectangular finite connected domains. For \(k, n \in \mathbb{N}^*\), we denote by \(G_{k,n}\) the rectangular domain with \(k\) rows and \(n\) columns. The horizontal \(G_{k,n}\) is the graph equipped with the HV-partition in which the cell in the last row of the first column is an H-cell; the alternative partition is referred to as the vertical \(G_{k,n}\). We denote by \(S_{k,n}\) the maximum escaping time over both horizontal \(G_{k,n}\) and vertical \(G_{k,n}\).
The goal of this section is twofold: we first present exact values of \(S_{k,n}\) obtained by computer simulation, which serve both as a reference and as a guide for the theoretical bounds established thereafter; we then prove rigorous bounds for square connected domains and some rectangular connected domains.
4.1 Exact Escape Times via Simulation on Small Grids↩︎
We computed the exact values of \(S_{k,n}\) for \(1 \le k, n \le 9\) (Table 1). The values \(S_{n,n} - 1\) up to \(n = 7\) were previously listed as sequence A282425 in the OEIS [10], with an error of 1 for \(S_{7,7}\); our values correct this entry.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 6 | 12 | 18 | 24 | 30 | 36 | 42 | 48 | |
| 3 | 17 | 28 | 37 | 48 | 57 | 68 | 77 | ||
| 4 | 46 | 64 | 86 | 104 | 146 | 156 | |||
| 5 | 85 | 130 | 145 | 214 | 221 | ||||
| 6 | 164 | 220 | 280 | 315 | |||||
| 7 | 262 | 356 | 410 | ||||||
| 8 | 488 | 618 | |||||||
| 9 | 679 |
Simulation Algorithm
By Remark [rm:inb95max], it suffices to consider initial configurations where the ant starts from an in-boundary arc. Computing the escape time \(S_{k,n}\) amounts to evaluating, over all initial configurations \((C, pos)\), the number of steps before escape, where \(pos\) ranges over in-boundary arcs and \(C\) over all possible color configurations of \(G_{k,n}\). A naive exhaustive search over all \(2^{kn}\) color configurations for each starting position is prohibitively expensive; we reduce this cost via two complementary optimizations.
Branching exploration. For a fixed starting position \(pos\), instead of simulating the ant independently for every color configuration \(C\), we exploit the fact that the choice of the state of a cell only matters upon its first visit. The exploration can thus be structured as a binary decision tree: whenever the ant visits a cell for the first time, the algorithm branches into two cases corresponding to the two possible initial states of that cell. Each branch then evolves deterministically according to Langton’s rule. In this way, all configurations that coincide on the set of already visited cells share the same trajectory prefix and are explored simultaneously. This avoids redundant recomputation and allows the entire configuration space to be traversed in a single branching exploration.
Symmetry reduction. The number of starting positions can also be reduced using geometric symmetries of the grid. Since the ant’s dynamics are invariant under reflections and rotations of the rectangular domain, many in-boundary arcs lead to equivalent trajectories. It therefore suffices to consider only the in-boundary arcs associated with \(\lceil k/2 \rceil\) consecutive cells of a boundary column (for horizontal starting positions), beginning at a corner cell, together with those associated with \(\lceil n/2 \rceil\) consecutive cells of a boundary row (for vertical starting positions), also beginning at a corner cell. When \(k = n\), the additional symmetry between rows and columns makes these two families equivalent, so that it is enough to consider a single boundary side. Moreover, instead of launching a separate branching exploration for each of these representative starting positions of a side, we aggregate them into a single exploration. For the horizontal case, this is achieved by extending \(G_{k,n}\) upward with \(\left\lceil \frac{k}{2} \right\rceil - 1\) additional rows, yielding a working grid of height \(k + \left\lceil \frac{k}{2} \right\rceil - 1\). The exploration is then initiated from the in-boundary arc of the cell that originally lay on the top row of \(G_{k,n}\). During the exploration, each branch is followed until the vertical span of the visited cells exceeds \(k\). This condition precisely captures the escape of the ant for one of the original starting positions represented in the merged construction. A symmetric construction is used for vertical starting positions when \(k \neq n\), and the overall escape time is obtained by taking the maximum over both orientations.
The branching exploration is implemented via a depth-first backtracking algorithm. During the forward phase, the ant is simulated until it escapes the admissible region. Each first visit to a cell is recorded as a branching point together with the current height and vertical bounds. When a branch terminates, the algorithm retraces its steps backward, restoring the previous state and identifying the most recent cell where an unexplored alternative remains. The exploration then resumes from this point with the alternate state. This systematic traversal guarantees that every feasible branch (and thus every configuration consistent with the symmetry reduction) is explored.
4.2 Upper Bound of the Escaping time of Square Domains↩︎
In this section, we consider the square finite connected domain \(G_n = G_{n,n}\) with \(n \in \mathbb{N}^*\) and investigate the growth of \(S_n = S_{n,n}\). Note that \(G_n\) has \(2 n^2 \cdot 2^{n^2}\) configurations and by Corollary 1, \(S_n \le 2^{n^2}\). In this section, we derive an improved upper bound using an inductive approach, expressing \(S_n\) in terms of \(S_{n-2}\).
Theorem 1. For each positive integer \(n\), we have \(S_n \le (n+1)!\).
Proof. By simulation: \(S_1=1\) and \((1+1)!=2\), \(S_2=6\) and \((2+1)!=6\) thus the inequality is true for \(n\in \{1,2\}\).
For \(n \ge 3\), observe that \(G_n\) can be decomposed as the union of \(G_{n-2}\) and \(B_n\), where \(B_n\) denotes the connected domain on the boundary cells of \(G_n\) (see Figure 9). This decomposition provides the basis for our inductive argument.
To maximize the number of steps on \(G_n\), the ant must start at an in-boundary arc of \(G_n\) (Remark [rm:inb95max]). From this starting position, it reaches an in-boundary arc of \(G_{n-2}\) within at most two or three steps when a corner cell is involved. Then it performs some number of steps within \(G_{n-2}\) before reaching an out-boundary arc of \(G_{n-2}\) thereby returning to \(B_n\). Once in \(B_n\), the ant undergoes a bouncing phase before re-entering \(G_{n-2}\). Each such bouncing phase requires at most two steps or three steps when a corner cell is involved. The process then repeats: the ant alternates between phases inside \(G_{n-2}\) and bouncing phases within \(B_n\) until it finally exits \(G_{n-2}\) for the last time and reaches an out-boundary arc of \(G_{n}\) in at most three additional steps. Suppose that the ant returns to \(G_{n-2}\) at most \(X_n\) times after its initial entry, then we obtain:
\[S_n \le 3 + (X_n+1) \cdot S_{n-2} + 3X_n + 3,\] where the four terms account, respectively, for: the initial steps to enter \(G_{n-2}\) from an in-boundary arc of \(G_n\); the \((X_n+1)\) visits to \(G_{n-2}\) (initial entry plus \(X_n\) returns); the \(X_n\) bouncing phases on \(B_n\); and the final steps to escape \(G_{n-2}\) to an out-boundary arc of \(G_n\). This simplifies to: \[S_n \le (X_n+1) \cdot S_{n-2} + 3X_n + 6.\]
It remains to bound \(X_n\). To this end, we analyze the behavior of the ant on the top row of \(B_n\) and determine the maximal number of times it can bounce there while still being able to return to \(G_{n-2}\). During a bouncing phase, the ant moves from \(G_{n-2}\), traverses boundary cells, and returns to \(G_{n-2}\), without occupying any in-boundary or out-boundary arc of \(G_n\).
For example, Figure 10 illustrates all possible bounces in the top row of \(B_{10}\) along with the maximum number of times each can be performed.
Each of the two corner cells of the top row can be used to perform only one type of bounce, which can occur at most once. Indeed, after a corner cell is used for a bounce, its color is updated, and the ant’s next visit to that cell immediately leads to an out-boundary arc of \(G_n\) in a single step.
In general, each non-corner cell in the top row can be used to perform two types of bouncing motions - left and right - depending on which side of the cell is located the horizontal arc that is involved in the bounce. Moreover, for each such cell, the counts of left and right bounces can differ by at most one, since consecutive visits to a given cell must alternate between the two directions due to the color-alternation property.
Combining these two observations, the number of possible bounces on the top row of \(B_n\) is bounded by: \[\begin{cases} 1+2+...+(\frac{n}{2}-1) +\frac{n}{2}+ (\frac{n}{2} -1) +...+2+1= \frac{n^2}{4} & \text{if n is even}\\ 1+2+...+(\frac{n-1}{2} -1) +\frac{n-1}{2}+\frac{n-1}{2}+ (\frac{n-1}{2} -1) +...+2+1= \frac{n^2-1}{4} & \text{if n is odd} \end{cases}\] By symmetry across the four sides of \(B_n\), we obtain \(X_n \le 4 \cdot \frac{n^2}{4}=n^2\). Substituting in \(S_n\le (X_n+1) \cdot S_{n-2} + 3X_n+6\), we obtain: \(S_n \le \left(n^2+1\right) S_{n-2} + 3n^2 + 6.\) Let us define \[T_n = S_n + 3.\] Then the previous inequality can be written as \((S_n +3) \le \left(n^2+1\right)\left(S_{n-2} +3 \right) + 6\) which yields \(T_n \le \left(n^2+1\right)T_{n-2} + 6\).
We claim that \(6<(n-1)T_{n-2}\) for all \(n\ge 3\). Indeed, for \(n = 3\), we have, \(S_1= 1\), and thus \((n-1)T_{n-2} = 2\times (1+3) = 8 > 6\). Since \((n-1)T_{n-2}\) is increasing, it follows that \(6<(n-1)T_{n-2}\) for all \(n\ge 3\). Therefore \[T_n \le \left(n^2+1\right)T_{n-2} + 6 \le \left(n^2+1\right) T_{n-2} + (n-1)T_{n-2} = (n+1) \cdot n \cdot T_{n-2}\] and by induction on the inequality \(T_n\le (n+1) \cdot n \cdot T_{n-2}\), we have
\[T_{n} \le \begin{cases} (n+1) \cdot n \cdot (n-1)\cdot (n-2)\cdot ...\cdot 6 \cdot T_4 & \text{if } n \text{ is even} \\ (n+1) \cdot n \cdot (n-1)\cdot (n-2) \cdot ... \cdot 5 \cdot T_3 & \text{if } n \text{ is odd} \end{cases}\] which in both cases yield \(S_{n} \le T_{n} \le (n+1)!\) since \(T_3= S_3+3=20 < 4!\) and \(T_4=S_4+3 =49 < 5!\). ◻
4.3 Linear bound of the Escaping Time of Some Rectangular Domains↩︎
In this section, we focus on the escaping time of rectangular finite connected domains consisting of two or three rows and an arbitrary number of columns. Our approach to determining the escape time of these domains consists in bounding the number of steps the ant can perform within each column of the domain before the termination of its motion within the entire domain. These columns — horizontal or vertical \(G_{2,1}\) or \(G_{3,1}\) — can be interpreted as gadgets consisting of entry arcs (the in-boundary arcs), exit arcs (the out-boundary arcs), and an internal state determined by the color configuration. Given its internal state and the specific entry arc through which the ant enters, the gadget updates its internal state and directs the ant toward one of its exit arcs. There are four possible types of motion that the ant can perform on every such column:
Bouncing: the ant enters and leaves through the same side of the column;
Crossing: the ant enters through one side of the column and exits through the opposite side;
Initial: the ant enters the grid through an in-boundary arc at the top or bottom of the column;
Out: the ant exits the grid through an out-boundary arc at the top or bottom of the column.
Initial and out motions are performed in one step, bouncing and crossing motions in two steps.
In all figures of this section, black, white, and gray cells still represent cells whose states are \(L\), \(R\), or unspecified, respectively, and curved solid arrows depict the motion of the ant.
4.3.1 Two-row Grids↩︎
When viewed column by column, a two-row grid (either vertical or horizontal) can be seen as an alternating succession of horizontal and vertical \(G_{2,1}\) ( See Figure\(~\ref{fig:2rowgrid}\)).
Since horizontal and vertical \(G_{2,1}\) are symmetric by a half turn rotation, it suffices to restrict our analysis to the horizontal \(G_{2,1}\). We therefore examine the possible behaviors arising when the ant enters and exits a horizontal \(G_{2,1}\) during its motion within the whole two-row grid.
Let’s label the three in-boundary arcs by \(l_{in},r_{in}\) and \(t_{in}\) and the three out-boundary arcs by \(l_{out},r_{out}\) and \(b_{out}\). The letters \(l,r,t\) and \(b\) respectively denote the left, right, top, and bottom sides of \(G_{2,1}\), according to the side of the gadget on which the corresponding arc is located, see Figure\(~\ref{fig:grid2195io}\) for an illustration.
When the ant enters through \(l_{in}\) or \(r_{in}\), it can exit through any of the three exit arcs. In contrast, when the ant enters through \(t_{in}\), it can exit only through \(l_{out}\) or \(r_{out}\). We associate with each admissible entry–exit pair a label to describe the motion of the ant, as summarized in Table\(~\ref{tbl:tab:motiontable2}\) where the letters \(I,B,O\) and \(C\) respectively denote Initial, Bouncing, Out and Crossing motions.
| Entry | \(t_{in}\) | \(t_{in}\) | \(l_{in}\) | \(l_{in}\) | \(l_{in}\) | \(r_{in}\) | \(r_{in}\) | \(r_{in}\) |
|---|---|---|---|---|---|---|---|---|
| Exit | \(l_{out}\) | \(r_{out}\) | \(l_{out}\) | \(r_{out}\) | \(b_{out}\) | \(l_{out}\) | \(r_{out}\) | \(b_{out}\) |
| Motion | \(R\) | \(L\) | \(LL\) | \(LR\) | \(R\) | \(RR\) | \(RL\) | \(L\) |
| Label | \(I_l\) | \(I_r\) | \(B_l\) | \(C_l\) | \(O_l\) | \(B_r\) | \(C_r\) | \(O_r\) |
Note that, during its motion within any two-row grid, the ant can use \(t_{in}\) as an entry into a horizontal \(G_{2,1}\) only once, namely when it enters the whole two-row grid. Moreover, if the ant exits through \(b_{out}\), it escapes the two-row grid entirely, thereby terminating its motion. Also note that if the ant exits a horizontal \(G_{2,1}\) through \(l_{out}\) (respectively \(r_{out}\)), it can subsequently re-enter the column only through \(l_{in}\) (respectively \(r_{in}\)).
The following result analyzes, for each type of motion (Initial, Bouncing, Out or Crossing) performed by the ant upon its first visit to a horizontal \(G_{2,1}\), the maximum number of steps it can perform within this horizontal \(G_{2,1}\) during its motion within the entire two-row grid. This is done by counting the steps of the initial motion together with those of any subsequent motions upon return. The next theorem is also true for vertical \(G_{2,1}\).
Lemma 1. During its motion within a two-row grid, if the motion performed by the ant upon its first visit to a column that is a horizontal \(G_{2,1}\) is:
an out motion, then the ant performs at most one step within this column before escaping the two-row grid;
a bouncing motion, then the ant performs at most three steps within this column before escaping the two-row grid. Moreover, these three steps consist of the bouncing motion and an out motion;
an initial motion, then the ant performs at most four steps within this column before escaping the two-row grid. Moreover, these four steps consist of the initial motion, a bouncing motion and an out motion;
a crossing motion, then the ant performs at most six steps within this column before escaping the two-row grid. Moreover, these six steps consist of three crossing motions, two of which occur in the same direction;
Proof. In all figures cited in this proof, black cells are in the \(L\) state and white cells are in the \(R\) state. Gray cells represent cells whose state may be either \(L\) or \(R\) and is not yet fixed. Curved solid arrows depict the motion of the ant within the column.
Let \(OC\) denote the horizontal \(G_{2,1}\) under consideration (\(OC\) for Original Column). We denote by \({C_{1} \brack C_{2} }\) the color configuration of \(OC\), where \(C_{1}, C_{2} \in \{ L, R \}\) correspond respectively to the states of the top and bottom cells. If the motion performed by the ant upon its first visit to \(OC\) is:
1. an out motion ( \(O_{l}\) or \(O_{r}\)): one step. The ant performs \(O_{l}\) or \(O_{r}\) in one step escaping the entire two-row grid.
2. a bouncing motion ( \(B_{l}\) or \(B_{r}\)): three steps at most. For the ant to perform \(B_{l}\) for example, the color configuration must necessarily be \({L \brack L}\). It becomes \({R \brack R}\) after \(B_l\) and upon a subsequent return, the ant then performs \(O_{l}\) reaching \(b_{out}\) in one step. See Figure 13. The symmetric behavior occurs for \(B_{r}\).
3. an initial motion (\(I_{l}\) or \(I_{r}\)): four steps at most. For the ant to perform \(I_{l}\) for example, the color configuration is necessarily either (A) \({R \brack L}\) or (B) \({R \brack R}\). After the execution of \(I_{l}\), the ant may subsequently re-enter the column only from the left.
If the initial configuration is \({R \brack L}\), then after performing \(I_{l}\) in one step it becomes \({L \brack L}\). From this it can perform additional three steps at most, since the ant can only eventually return from left to perform \(B_l\) and then \(O_l\). See A in Figure 14.
If the initial configuration is \({R \brack R}\) , then after performing \(I_{l}\) in one step it becomes \({L \brack R}\). Upon the next return from the left, the ant then performs \(O_{l}\) reaching \(b_{out}\) in one step. See B in Figure 14.
The symmetric behavior occurs for \(I_{r}\).
4. a crossing motion (\(C_{l}\) or \(C_{r}\)): six steps at most. For the motion \(C_{l}\) to occur for example, the color configuration must be \({R \brack L}\). In this case, the ant traverses \(OC\) from left to right in two steps, thereby updating the configuration to \({L \brack R}\). Upon a subsequent return from the right, the ant traverses \(OC\) from right to left in two steps, restoring the configuration to \({R \brack L}\). In principle, this alternating behavior could continue indefinitely, provided that the ant repeatedly crosses the column. See Figure 15.
However, such indefinite repetition cannot occur in a two-row grid. After traversing \(OC\) from left to right (\(C_l\)), the ant must reach a column \(RC\) (as Right Column) to the right of \(OC\) in order to return. To do so, it traverses all intermediate columns and performs a bouncing motion within \(RC\). This sends the ant back from right to left across the same columns until it returns to \(OC\), which it now traverses performing \(C_r\). Upon returning to \(OC\) again, the ant performs a second \(C_l\) and moves once more toward \(RC\). This time, however, the visit to \(RC\) results in an outgoing motion, as it already executed a bouncing motion there previously. Thereby the ant terminates its motion within the entire two-row grid. See Figure 16 for an illustration of all this.
The symmetric behavior occurs when the first crossing motion within \(OC\) is \(C_{r}\).
◻
Theorem 2. For every integer \(n\ge2\), one has \(S_{2,n}\le 6(n-1)\).
Proof. For \(S_2=6\) by simulation. For \(n>2\), the grid consists of two boundary columns and \(n-2\) interior columns. To maximize the number of steps, the ant must perform a crossing motion within each interior column upon its first visit, and a bouncing or initial motion within the boundary columns. Since the initial motion can occur only once, the optimal strategy is to perform an initial motion within one boundary column, a bouncing motion within the other, and crossing motions on all interior columns. Thus by Lemma 1 \[S_{2,n}\le 4 +3 -1 + 6(n-2) = 6(n-1).\] The term \(-1\) accounts for the fact that the out motion occurs only once but would otherwise be counted twice in the contribution of the boundary columns. ◻
This bound is tight. Figure 17 exhibits explicit configurations achieving \(S_{2,n} = 6(n-1)\) for all \(n \ge 2\), with separate constructions for even and odd \(n\).
4.3.2 Three-row Grids↩︎
When viewed column by column, a three-row grid (either vertical or horizontal) can be seen as an alternating succession of horizontal and vertical \(G_{3,1}\) ( see Figure\(~\ref{fig:3rowgrid}\)). There are four possible types of motion that the ant can perform on a column of a three-row grid: Initial, Bouncing, Crossing and Out motions. However, no Out motion can occur on a vertical \(G_{3,1}\), and no Initial motion can occur on a horizontal \(G_{3,1}\).
The main result of this section is:
Theorem 3. For every integer \(n\ge2\), one has \(S_{3,n} \le 10n-4\).
The proof of Theorem 3 relies on Corollary 2, which bounds the number of steps the ant can perform within each vertical column depending on the type of its first motion. This corollary itself follows from two lemmas - Lemma 3 and Lemma 4 - bounding the additional steps after a crossing and a bouncing motion respectively, both of which rely on the blocking behavior of horizontal columns established in Lemma 2. We now state and prove these results.
We start with a result concerning horizontal \(G_{3,1}\). Let’s label its four in-boundary arcs by \(lt_{in},lb_{in},rt_{in}\) and \(rb_{in}\) and its four out-boundary arcs by \(l_{out},r_{out},t_{out}\) and \(b_{out}\) as illustrated on Figure\(~\ref{fig:Hgrid3195io}\).
Lemma 2. During the motion of the ant on a three-row grid, suppose the ant performs a crossing motion within a column that is a horizontal \(G_{3,1}\) and subsequently re-enters it via an arc incident to a cell not exited during that crossing. Then the ant cannot perform any further crossing motion through this column before escaping the three-row grid.
Proof. Let \(OC\) denote the horizontal \(G_{3,1}\) under consideration. We denote by the color configuration of \(OC\), where \(C_{1},C_{2},C_{3}\in\{L,R\}\) correspond respectively to the state of the top, middle, and bottom cells. Assume without loss of generality that the ant crosses \(OC\) from left to right using cells of the top and the middle rows (enter through \(lt_{in}\) and exit through \(r_{out}\)). The argument for the other types of crossings follows by symmetry. Figure 20 illustrates the arguments that follow.
Before the crossing, the color configuration of the column is either or . After the crossing, the ant can subsequently return to the column only from the right and in order to re-enter it through an arc incident to a cell different from the top and the middle cells, it must enter through \(rb_{in}\).
Case A. Suppose the initial color configuration is . After the crossing, it becomes . When the ant returns through \(rb_{in}\), it must perform an out motion reaching \(b_{out}\), thereby escaping the three-row grid.
Case B. Suppose the initial color configuration is . After the crossing, it becomes . When the ant returns through \(rb_{in}\), it performs a bouncing motion updating the color configuration to . The ant can subsequently return to the column only from the right through \(rb_{in}\) (B.A) or \(rt_{in}\) (B.B).
Case B.A. If the ant again returns through \(rb_{in}\), it must perform an out motion reaching \(b_{out}\).
Case B.B. If instead, the ant returns through \(rt_{in}\), it performs a bouncing motion, yielding the color configuration . With this configuration, any subsequent return through either \(rb_{in}\) (B.B.A) or \(rt_{in}\) (B.B.B) necessarily leads to \(b_{out}\) or \(t_{out}\), respectively.
In all cases, the ant escapes the three-row grid without performing any further crossing motion through \(OC\).
◻
For simplicity, throughout the remainder of this section, we say that a horizontal column is blocking if it is in a color configuration such that the ant cannot perform any further crossing motion through it before escaping the entire three-row grid.
We now turn to vertical columns. Label the in-boundary and out-boundary arcs of a vertical \(G_{3,1}\) by \(l_{in},r_{in},t_{in}\) and \(b_{in}\) and its four out-boundary arcs by \(lt_{out},lb_{out},rt_{out}\) and \(rb_{out}\) as illustrated on Figure\(~\ref{fig:Vgrid3195io}\).
When the ant enters through \(l_{in}\) or \(r_{in}\), it can exit through any of the four exit arcs. In contrast, when the ant enters through \(t_{in}\) it can exit only through \(lt_{out}\) or \(rt_{out}\) and when the ant enters through \(b_{in}\) it can exit only through \(lb_{out}\) or \(rb_{out}\). We associate with each admissible entry–exit pair a label to describe the motion of the ant, as summarized in Table\(~\ref{tbl:tab:motiontable3}\).
| Entry | \(t_{in}\) | \(t_{in}\) | \(b_{in}\) | \(b_{in}\) | \(l_{in}\) | \(l_{in}\) | \(l_{in}\) | \(l_{in}\) | \(r_{in}\) | \(r_{in}\) | \(r_{in}\) | \(r_{in}\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Exit | \(lt_{out}\) | \(rt_{out}\) | \(lb_{out}\) | \(rb_{out}\) | \(lt_{out}\) | \(lb_{out}\) | \(rt_{out}\) | \(rb_{out}\) | \(rt_{out}\) | \(rb_{out}\) | \(lt_{out}\) | \(lb_{out}\) |
| Motion | \(R\) | \(L\) | \(L\) | \(R\) | \(LL\) | \(RR\) | \(LR\) | \(RL\) | \(RR\) | \(LL\) | \(RL\) | \(LR\) |
| Label | \(I_{lt}\) | \(I_{rt}\) | \(I_{lb}\) | \(I_{rb}\) | \(B_{lt}\) | \(B_{lb}\) | \(C_{lt}\) | \(C_{lb}\) | \(B_{rt}\) | \(B_{rb}\) | \(C_{rt}\) | \(C_{rb}\) |
Lemma 3. During its motion within a three-row grid, after performing a crossing motion within a column that is a vertical \(G_{3,1}\), the ant can subsequently perform at most four additional steps on that column before escaping the three-row grid. Moreover, these additional four steps consist of two crossing motions in opposite directions.
Proof. Let \(OC\) denote the vertical \(G_{3,1}\) under consideration. Without loss of generality, we may suppose that the ant performs \(C_{lt}\) within \(OC\). The argument for the other types of crossings follows by symmetry.
After performing \(C_{lt}\), the ant may subsequently re-enter \(OC\) only from the right, through \(r_{in}\) and in order for the ant to return to \(OC\), it must first perform a bouncing motion within some column \(RC\) located to the right of \(OC\). The forward motion, which includes the crossing of \(OC\), the traversal of the eventual intermediate columns between \(OC\) and \(RC\), and the bounce on \(RC\), may be performed in one of the following two ways: either (A) using only cells of the top and middle rows of the three-row grid or (B) using cells of all three rows.
Case A. In the case the forward motion is performed exclusively using cells of the top and middle rows, the ant behaves as if it were moving on a two-row grid. Consequently, after bouncing on \(RC\), it may return toward \(OC\), perform \(C_{rt}\) and eventually another \(C_{lt}\) on \(OC\), and return to \(RC\). The column \(RC\) may be either (A.A) horizontal or (A.B) vertical.
Case A.A. If \(RC\) is horizontal, then upon returning to it the ant reaches \(t_{out}\) in a single step. Hence, it escapes the entire grid and does not return to \(OC\). See Figure 22 for an illustration of the motion of the ant.
Case A.B. If \(RC\) is a vertical column, then there exists at least one horizontal intermediate column between \(OC\) and \(RC\), since \(OC\) is also a vertical column. Let \(LHC\) denote the horizontal column immediately to the left of \(RC\). When the ant return to \(RC\), it can only perform either (A.B.A) \(B_{lb}\) or (A.B.B) \(C_{lb}\). Figure 23 illustrates the arguments that follow.
Case A.B.A. If it performs \(B_{lb}\) on \(RC\), it immediately returns to \(LHC\) through \(rb_{in}\), thereby turning \(LHC\) into a blocking column by Lemma 2, since the last motion performed on \(LHC\) was a left-to-right crossing using cells of the top and the middle rows.
Case A.B.B. If it performs \(C_{lb}\) on \(RC\), then upon to a return from the right, the ant performs \(C_{rb}\) on \(RC\) and enters \(LHC\) through \(rb_{in}\), again turning \(LHC\) into a blocking column by Lemma 2.
After the first execution of \(C_{lt}\) on \(OC\), in Case A, the ant performs at most four additional steps on \(OC\) consisting of \(C_{rt}\) followed by another \(C_{lt}\).
Case B. In the case where the forward motion involves all three rows, let \(LHC\) denote the last column in which the ant motion uses a cell belonging to a row different from those used to bounce on \(RC\) during this forward motion. Figure 24 illustrates the arguments that follow.
The column \(LHC\) must necessarily be horizontal. Indeed, for the ant to cross a vertical column, it must use either the cells of the middle and top rows or those of the middle and bottom rows. If the traversal is performed using the middle and top cells, then in order to cross or bounce in the next column (which is horizontal), the ant must again use the top and middle cells. Similarly, if the crossing is performed using the middle and bottom cells, then in order to cross or bounce in the next column, the ant must use the bottom and middle cells. Therefore, the motion performed by the ant on these two consecutive columns necessarily involves cells from the same two rows. Consequently, \(LHC\) cannot be vertical and must be horizontal.
Let \(LVC\) denote the column immediately reached by the ant after \(LHC\) during the forward motion toward \(RC\). The motion from \(LVC\) to \(RC\) is performed using exactly two rows, namely either the top and middle rows or the middle and bottom rows. Assume that these two rows are the top and middle rows. Then the ant must have traversed \(LHC\) using the bottom and middle rows and have performed \(C_{lt}\) on \(LVC\) during the forward motion. After bouncing on \(RC\), the ant returns to \(LVC\), performs \(C_{rt}\), and subsequently enters \(LHC\) through \(rt_{in}\), thereby turning \(LHC\) into a blocking column by Lemma 2.
If, on the other hand, the motion from \(LVC\) to \(RC\) involves the middle and bottom rows, a symmetric argument shows that upon returning from \(RC\), the ant re-enters \(LHC\) in such a way that \(LHC\) again becomes a blocking column.
After the first execution of \(C_{lt}\) on \(OC\), in Case B also, the ant performs at most four additional steps on \(OC\) consisting of \(C_{rt}\) followed by another \(C_{lt}\). ◻
Lemma 4. During its motion within a three-row grid, after performing a bouncing motion within a column that is a vertical \(G_{3,1}\), the ant can subsequently perform at most eight additional steps on that column before escaping the three-row grid. Moreover, these steps consist of one bouncing motion within the same side of the initial bouncing and three crossing motions, two of which start from the side of the initial bouncing.
Proof. Let \(OC\) denote the vertical \(G_{3,1}\) under consideration. Assume the ant performs a bouncing motion within \(OC\). Without loss of generality, we may suppose that its a left top bouncing, \(B_{lt}\), since the argument presented below applies symmetrically to all other types of bouncing. Figure 25 illustrates the arguments that follow.
After performing \(B_{lt}\), the ant may re-enter \(OC\) from the left through \(l_{in}\), and it can perform either \(C_{lb}\) (A) or \(B_{lb}\) (B) on \(OC\).
Case A. If the ant performs \(C_{lb}\), then by Lemma 3, it can subsequently perform at most four additional steps on \(OC\). Together with the crossing \(C_{lb}\), this yields a total of six additional steps after the first bouncing.
Case B. If the ant instead performs \(B_{lb}\), then upon one further return from the left to \(OC\) through \(l_{in}\) and this time can only perform \(C_{lt}\) (B.A). After this, by Lemma 3, it can perform at most four additional steps on \(OC\) before escaping the three-row grid. Hence, in this case, the total number of additional steps after the first bouncing reaches eight.
◻
Corollary 2.
During its motion within a three-row grid, if the motion performed by the ant upon its first visit to a column that is a vertical \(G_{3,1}\) is:
a crossing motion, then the ant performs at most six steps within this column before escaping the entire three-row grid. Moreover, these six steps consist of three crossing motions, two of which occur in the same direction;
a bouncing motion, then the ant performs at most ten steps within this column before escaping the entire three-row grid. Moreover, these ten steps consist of two bouncing motion within the same side and three crossing motions, two of which start from the side of the bouncing;
an initial motion, then the ant performs at most eleven steps within this column before escaping the entire three-row grid.
Proof. Statements (1) and (2) follow directly from Lemma 3 and Lemma 4. For (3), it suffices to observe that any initial motion is performed in a single step and can occur only once. Upon a subsequent return of the ant to the column, the only possible motions are either a crossing or a bouncing. The conclusion then follows immediately from (1) and (2). ◻
We now give the proof of the main result.
Proof of Theorem 3. We decompose \(S_{3,n}= SH_{3,n} + SV_{3,n}\), where \(SH_{3,n}\) and \(SV_{3,n}\) denote respectively the maximum number of steps the ant can perform within all the horizontal columns and all the vertical columns of the three-row grid with \(n\) columns. Except for the initial motion and the final out motion, each of which is performed in a single step and occurs at most once, the motion of the ant can be decomposed into a succession of two-step segments within individual columns. Moreover, after performing two steps within a horizontal column, the ant must necessarily perform its next two steps within a vertical column. Conversely, after visiting a vertical column, the ant must necessarily move to a horizontal column. Therefore, the total contribution of horizontal columns cannot exceed that of vertical columns by more than two steps, and we obtain \(SH_{3,n} \le SV_{3,n}+2\). It remains to bound \(SV_{3,n}\).
Case A. \(n\) is even. In this case, there is exactly one vertical column that is a boundary column. On such a boundary column, if the first motion of the ant is a crossing, the ant can perform at most four steps on it, consisting of two crossings in opposite directions, the first making the ant enter the whole grid and the other making the ant leave it. If the first motion is a bouncing, then the ant can perform at most six steps, consisting of two bouncing and one crossing, after which it exits the grid. For non-boundary vertical columns, Corollary 2 provides a bound of \(10\) steps per column, except for at most one column where the bound may increase to \(11\) if the ant starts its motion there. Hence \[SV_{3,n} \le 10\left(\frac{n}{2} - 1\right) + 6 + 1 = 5n - 3,\] where the three terms account, respectively, for: the non-boundary vertical columns; the boundary vertical column; and the possible initial motion within a vertical column.
Case B. \(n\) is odd. The two boundary columns of the three-row grid are either both vertical (B.A) or both horizontal (B.B).
Case B.A. Both boundary columns are vertical. On one boundary column the ant may perform at most six steps (two bouncing and a crossing, after which it exits the grid), while on the other it may perform at most four steps (two bouncing motions), since the ant exits the grid only once. Hence, \[SV_{3,n} \le 10\left(\frac{n+1}{2} - 2\right) + (6 + 4) + 1 = 5n - 4,\] where the three terms account, respectively, for: the non-boundary vertical columns; the two boundary vertical columns; and the possible initial motion within a vertical column.
Case B.B. Both boundary columns are horizontal. In this situation, \[SV_{3,n} \le 10\left(\frac{n-1}{2}\right) + 1 = 5n - 4,\] where the two terms account, respectively, for: the non-boundary vertical columns (all vertical columns are non-boundary in this case); and the possible initial motion within a vertical column.
In all cases, we obtain \(SV_{3,n}\le 5n-3\). Using \(SH_{3,n} \le SV_{3,n}+2\), we have \[SH_{3,n}\le 5n-1 \text{ and } S_{3,n}=SH_{3,n}+SV_{3,n} \le 10n-4.\] ◻
Lower bound for \(S_{3,n}\)
The upper bound is nearly tight. Explicit constructions show that for every \(n \ge 3\):
\[S_{3,n} \ge \begin{cases} 10n - 12 & \text{ if } n \text{ is even. (see Figure \ref{fig:3maxeven})} , \\ 10n - 13 & \text{ if } n \text{ is odd.~ (see Figure \ref{fig:3maxodd}).} \end{cases}\] Moreover, our simulations for \(n\le20\) yield exact escaping times consistent with these constructions.
4.3.3 Four-row Grids: Lower bound and conjecture↩︎
Explicit constructions (Figure 28) show that for every \(n \ge 14:\) \[S_{4,n} \ge 34(n-5) + 20.\] Moreover, our simulations indicate that \(S_{4,n} = 34(n-5) + 20\) for even \(n\) with \(14\le n \le 18\) and odd \(n\) with \(9\le n \le 17\). These observations lead us to conjecture the following linear upper bound.
For every integer \(n \ge 2\), one has \(S_{4,n} \le 34n\).
4.4 Upper Bound for the Escaping Time of Rectangular Domains↩︎
Using the same inductive decomposition as in Section 4.2, adapted to the rectangular setting, we now derive an upper bound for \(S_{k,n}\) that improves on the general \(2^{kn}\) bound for fixed \(k\).
Theorem 4. For fixed \(k \ge 2\) and \(n \ge k\), \[S_{k,n} \;\le\; \begin{cases} (6n-4)\cdot\left(\dfrac{n+1}{\sqrt{2}}\right)^{k-2} & \text{if } k \text{ is even,}\\[6pt] (10n-2)\cdot\left(\dfrac{n+1}{\sqrt{2}}\right)^{k-3} & \text{if } k \text{ is odd.} \end{cases}\] In particular, \(S_{k,n} \le \left(\frac{n+1}{\sqrt{2}}\right)^k.\)
Proof. We decompose \(G_{k,n}\) as the union of the interior grid \(G_{k-2,n}\) and two \(G_{1,n}\), one along the top boundary and one along the bottom boundary (Figure 29).
By Remark [rm:inb95max], the ant starts from an in-boundary arc of \(G_{k,n}\), reaches an in-boundary arc of \(G_{k-2,n}\) in at most two steps, and then alternates between phases inside \(G_{k-2,n}\) and bouncing phases on the two \(G_{1,n}\), until it finally exits \(G_{k,n}\) in at most two additional steps. If the ant returns to \(G_{k-2,n}\) at most \(Y_n\) times after its initial entry, we obtain \[S_{k,n} \;\le\; (Y_n+1)\cdot S_{k-2,n} + 2Y_n + 4.\]
It remains to bound \(Y_n\). Since the decomposition involves only the top and bottom \(G_{1,n}\) (two sides rather than four), the same per-row bouncing analysis as in Section 4.2 gives \(Y_n \le 2 \cdot \frac{n^2}{4} = \frac{n^2}{2}\). Substituting: \[S_{k,n} \;\le\; \left(\frac{n^2}{2}+1\right) S_{k-2,n} + n^2 + 4 \text{ or equivalently } 2S_{k,n} \le (n^2+2)\,S_{k-2,n} + 2n^2 + 8\]
Defining \(T_{k,n} = S_{k,n}+2\), this rewrites as \(2T_{k,n} \;\le\; (n^2+2)\,T_{k-2,n} + 8.\)
Since \((n^2+2) = (n+1)^2 - (2n-1)\) and \((2n-1)\,T_{k-2,n} > 8\) for all \(k \ge 4\) and \(n \ge k\) (which follows from \(T_{2,n}=6(n-1)+2\) and the monotonicity of \((2n-1)\,T_{k-2,n}\)), we obtain \[2T_{k,n} \;\le\; (n+1)^2\,T_{k-2,n}, \quad\text{i.e.,}\quad T_{k,n} \;\le\; \left( \frac{n+1}{\sqrt{2}}\right)^2 \,T_{k-2,n} .\]
Applying this inequality by induction on \(k\), using the base cases \(T_{2,n} \le 6n-4\) (for even \(k\)) and \(T_{3,n} \le 10n-2\) (for odd \(k\)), given by Theorems 2 and 3 respectively, yields the stated bound. ◻
5 Conclusion and Open Questions↩︎
We studied the escaping time of Langton’s ant on finite connected domains of the square grid, establishing general structural properties and deriving upper bounds. We obtained a factorial upper bound for square domains and linear bounds for rectangular domains of height two and three, supported by exact values from simulations and matching or near-matching lower-bound constructions. More generally, for a fixed height \(k\), we obtained an upper bound \(\left(\frac{n+1}{\sqrt{2}}\right)^k\) for rectangular domains \(G_{k,n}\). Several directions remain open.
Our simulation results for square domains (\(n \le 9\)) suggest that \(S_{n,n}\) grows significantly slower than the factorial upper bound \((n+1)!\), with values consistent with cubic growth \(S_{n,n} \in O(n^3)\). Can the factorial bound be improved to a polynomial bound in \(n\)?
Extending the column-by-column analysis to grids of height four appears feasible, although the case analysis becomes significantly more complex. Preliminary simulations suggest a linear bound of the form \(S_{4,n} \le 34n\), and we have identified constructions achieving values close to this bound. Can this conjecture be proved?
More generally, while \(\left(\frac{n+1}{\sqrt{2}}\right)^k\) guarantees a polynomial upper bound in \(n\) for every fixed \(k\) for \(S_{k,n}\), the degree grows with \(k\). Is there a function \(f\) such that \(S_{k,n} \le f(k)\,n\) for all \(k \in \mathbb{N}\)? In other words, is the escaping time linear in \(n\) for every fixed height \(k\)?
Computing exact values of \(S_{k,n}\) for larger grids (e.g., \(10 \times 10\) and beyond) could help refine these conjectures, and designing constructions yielding stronger lower bounds remains an important combinatorial challenge.
Finally, a better understanding of escaping time may contribute to clarifying the computational complexity of Langton’s ant on finite grids, particularly for reachability problems.