Prisoners and Guards on Rectangular Boards

Grady Bullington, Linda Eroh, and Steven J. Winters Mathematics Department University of Wisconsin, Oshkosh 800 Algoma Blvd. Oshkosh, WI 54901 USA

                  bullingt@uwosh.edu
                    eroh@uwosh.edu
                   winters@uwosh.edu

Abstract

Howard, Ionascu, and Woolbright introduced the “Prisoners and Guards” game as a two-player game on an n × n checkerboard. At the beginning of the game, every square of the board has a guard. At each stage in the game, for each prisoner, there must be at least as many guards as prisoners on adjacent squares. The players take turns either replacing a guard with a prisoner in their color or replacing one prisoner (of either color) with a guard, then replacing two guards with prisoners in their color, subject to the rule above. When neither player can adjust the board any further, the player with more prisoners in their color wins. Howard, Ionascu, and Woolbright gave formulas for the maximum number of prisoners on n × n boards. In this paper, we give formulas for the number of prisoners in the maximum configurations of n × m boards, where 2 ≤ n < m, for n = 2, 3, and 5, upper and lower bounds that differ by less than 2 when n = 4, and a lower bound for n = 6.

1 Introduction

Howard, Ionascu, and Woolbright [6] introduced the “Prisoners and Guards” game based on an earlier puzzle by Woolbright (see [4]) as a two-player game on an n × n checkerboard. At the beginning of the game, every square of the board has a guard. At each stage in the game, for each prisoner, there must be at least as many guards as prisoners on adjacent squares. The players take turns either replacing a guard with a prisoner in their color or replacing one prisoner (of either color) with a guard, then replacing two guards with prisoners in their color, subject to the rule above. When neither player can adjust the board any further, the player with more prisoners in their color wins. Howard, Ionascu, and Woolbright [6] gave formulas for the maximum number of prisoners in n × n boards. In this paper, we give formulas for the number of prisoners in the maximum configurations of n × m boards, where 2 ≤ n < m, for n = 2, 3, and 5, upper and lower bounds that differ by less than 2 when n = 4, and a lower bound for n = 6.

The guards in a valid board are related to a number of domination problems, including the half domination set in the king’s graph [4], unfriendly partition [1], and global offensive alliance [8]. See also [2, 5, 9] for related domination problems.

Following the notation used by Howard, Ionascu, and Woolbright [6], we let P (n, m) represent the maximum number of prisoners that can appear on an n by m rectangular board, subject to the rules that each square contains either a prisoner or a guard, and that for every prisoner, there must be at least as many guards as prisoners on adjacent squares. Here, squares are considered adjacent if they share an edge or a corner, so if one square is immediately to the right, left, above, below or diagonal from the other square. For clarity, in the figures we indicate prisoners with “P” and guards with blank squares.

2 Maximum 2 × n Boards

Theorem 1. For every positive integer n such that n = 3 or n ≥ 5, the maximum number of prisoners satisfies P (2, n) = n + 1, while P (2, 2) = 2 and P (2, 4) = 4.

Proof. It is not difficult to see that P (2, 2) = 2. For P (2, 4), partition the board into two 2 by 2 subboards. Each subboard contains two corner squares. If there is a prisoner in one of the corner squares, then there must be two guards in the 2 by 2 subboard to guard that prisoner; otherwise, there must be guards in both corner squares. Thus, each 2 by 2 subboard contains at most 2 prisoners, so P (2, 4) ≤ 4. We could, for instance, place prisoners in all four corners to achieve P (2, 4) = 4.

Next, we show that P (2, n) ≤ n + 1 for all n ≥ 2. Suppose there is a column with two prisoners. If it is an end-column, then each prisoner must have two guards; otherwise, each prisoner must have three guards. In either case, the next column to the right cannot contain two prisoners. If the next column to the right has exactly one prisoner, then there must be another column to the right of that one with no prisoners. Thus, every time there is a column with two prisoners, provided it is not the last (rightmost) column, we can place it in a block with one or two columns to its right, as shown in Figure 1. Thus, except possibly for the last column, we average at most 1 prisoner per column. The last column could have 2 prisoners. Thus, there are at most (n − 1) + 2 = n + 1 prisoners total.

If n is odd, then we can alternate a column with two prisoners, followed by a column with two guards, etc., in order to place n + 1 prisoners in a 2 by n board. An arrangement

P P  P P P  P P P

Figure 1: Three possible blocks that can be formed when there is a column of all prisoners.

P P  P P P  P P

Figure 2: An arrangement of 7 prisoners in a 2 by 6 board.

of 7 prisoners in a 2 by 6 board is shown in Figure 2. For any even value of n greater than 6, we can add alternating columns with two prisoners, then two guards, etc., to this configuration.

3 Maximum 3 × n Boards

Theorem 2. For every positive integer n ≥ 3, the maximum number of prisoners satisfies P (3, n) = 2n.

Proof. We might place prisoners in every square in the first and third rows, so P (3, n) ≥ 2n. Suppose there is an arrangement with more than 2n prisoners in a 3 by n board. Then, by the pigeonhole principle, some column must contain three prisoners. The prisoner at the top of that column must have two guards if it is an end-column or three guards if it is not an end-column. If it is not an end-column, two of the guards might be in the column to the left, but at least one must be in the column to the right. Thus, the next column to the right must have a guard in either the top or the middle row. Similarly, in order to guard the prisoner at the bottom of the three-prisoner column, the next column to the right must have a guard in either the middle or last row. Thus, the only way that the next column to the right might have 2 or more prisoners is if it has a prisoner in the first and last row and a guard in the middle. But then there must be another column to the right of that containing three guards (see Figure 3). If there is a column with three prisoners and it is not the last (rightmost) column, then we form a block with that column and either one column to the right (if the column to the right has at most one prisoner) or with two columns to the right (in the situation shown in Figure 3). Thus, each block has an average of at most 2 prisoners per column, and each column not used in a block, except possibly the last column, has at most 2 prisoners.

Now, the last (rightmost) column might contain three prisoners, but then the column before it, to the left, must contain three guards. If that all-guard column is not already used

P P P P P

Figure 3: A block of three columns that averages at most 2 prisoners per column

P P P P P  P P P

Figure 4: The only possible blocks that end in a column with all guards.

in some block, then we form a block with the last two columns. If the all-guard column is used in a block, then it is one of the two blocks shown in Figure 4. We include the last column (with 3 prisoners) in this block, and the block still has on average at most 2 prisoners per column. Since we have, on average, at most 2 prisoners per column, there cannot be more than 2n prisoners total.

4 Maximum 4 × n Boards

Theorem 3. For every positive integer n ≥ 4, the maximum number of prisoners satisfies P (4, n) ≤ ⌊\frac{9}{4}n + \frac{5}{4}⌋.

Proof. If every column has 2 or fewer prisoners, then P (4, n) ≤ 2n ≤ \frac{9}{4}n + \frac{5}{4}. Thus, we are only concerned about columns with 3 or more prisoners. Up to symmetry, there are only 3 possible columns with 3 or more prisoners, as shown in Figure 5.

First, we will show that if any of the columns A, B, or C appears anywhere except in the very last (rightmost) column, then it can be combined in a block with other columns to

P P P P A  P P P B  P P P C

Figure 5: Up to symmetry, these are the only possible columns with 3 or more prisoners.

P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P  P P P P P P P P P P P P  P P P P P P P P P P P P P P

Figure 6: Arrangements showing the lower bounds for P (4, 4) = 9, P (4, 5) = 12, P (4, 6) = 14, P (4, 7) = 16, P (4, 8) = 19, and P (4, 9) = 21.

its right so that each block has an average of \frac{7}{3}, \frac{9}{4}, or 2 prisoners per column. Next, we will show that at most two blocks that average \frac{7}{3} prisoners per column can appear consecutively, and that each block or pair of consecutive blocks that averages \frac{7}{3} prisoners per column can be combined with adjacent columns or blocks of columns to form new blocks that average at most \frac{9}{4} prisoners per column.

First, consider a column of type A. If it is the first column on the left, then the very next column must contain all guards, and we can form a block from these two columns. If there is a column of type A that is not the first or last column, then the topmost prisoner requires 3 guards, at least one of which must be in the next column to the right. Similarly, the prisoner in the bottom row requires at least 3 guards, at least one of which must be in the next column to the right. So the next column to the right contains at least two guards, one in the first or second row and one in the third or fourth row. Up to symmetry, there are 6 possibilities for the column to the right of column A. In case AI, when the column to the right contains 4 guards, we form a block from these two columns with an average of 2 < \frac{7}{3} prisoners per column. Each other case is shown in Figure 7, along with the third column with the maximum possible number of prisoners in it. In each of these cases, we form a block from column A and the two columns to its right, as shown in Figure 7. Each block has three columns and at most 7 prisoners.

Now consider a column of type B. If it is the first column, then the second column can have at most one prisoner (in the bottom row), and we can form a block from these two columns with an average of 2 < \frac{7}{3} prisoners per column. In general, if the next column to the right has at most one prisoner, and at least 3 guards, then we can form a block with the column of type B and the one to the right. If the column of type B is not the first or last column, then the prisoner in the top row requires 3 guards, at least one of whom must be in the first or second row of the next column to the right. There are seven possibilities for the next column to the right with at most 2 guards. Each of them is shown in Figure 8 along with the third column containing the maximum possible number of prisoners. In each of these cases, we form a block of three columns, including the column of type B and two to its right, with at most 7 prisoners.

[figure: P; P; P; P; P; P; AIV; P; P; P; P; P; P; AV; P; P; P; P; P; P; P; AVI; P; P; P; P; AI; P; P; P; P; P; P; P; AII; P; P; P; P; P; P; P; AIII]

Figure 7: Possibilities for columns to the right of column A. A circled P means that there can be one prisoner in any location within the circled region.

[figure: P; P; P; P; P; P; P; BV; P; P; P; P; P; P; BVI; P; P; P; P; P; P; BVII; P; P; P; P; P; P; P; BI; P; P; P; P; P; P; BII; P; P; P; P; P; P; P; BIII; P; P; P; P; P; P; BIV]

Figure 8: Possibilities for columns to the right of column B. A circled P means that there can be one prisoner in any location within the circled region.

[figure: P; P; P; P; P; P; P; CV; P; P; P; P; P; P; P; CVI; P; P; P; P; P; P; CVII; P; P; P; P; P; P; P; CI; P; P; P; P; P; P; P; P; CII; P; P; P; P; P; P; CIII; P; P; P; P; P; P; P; CIV]

Figure 9: Possibilities for columns to the right of column C. A circled P means that there can be one prisoner in any location within the circled region.

[figure: P; P; P; P; P; P; P; P; P]

Figure 10: A block of 4 columns in Case CII.

Finally, we consider a column of type C. If it is the first column, then the next column to the right will have at most one prisoner, in the first or second row. We can form a block from these two columns with on average 2 < \frac{7}{3} prisoners per column. Assuming column C is neither the first nor the last column, the prisoner in the bottom row requires 3 guards, at least one of whom must be in the next column to the right, in the third or fourth row. If the next column to the right has at most one prisoner, we again form a block with the column of type C and the column to its right, so that the block has at most 2 prisoners per column. There are seven possibilities for the next column to the right with at least two prisoners, as shown in Figure 9. Each is shown with the maximum possible number of prisoners in the next column. In each case except CII, we form a block of three columns with at most 7 prisoners. In case CII, it is possible that the column of type C and the two columns to its right have 8 prisoners, but then the configuration shown in Figure 10 is forced, and the next column has at most one prisoner. In that case, we form a block of four columns with an average of at most \frac{9}{4} prisoners per column.

Next, we notice that the only blocks that have more than \frac{9}{4} prisoners per column on average are AII, AIII, AVI, BI, BIII, BV, CI, CIV, CV, and CVI. For convenience, we will refer to these blocks as \frac{7}{3}-blocks, since they each average \frac{7}{3} prisoners per column. Checking each of these blocks, we can confirm that none of them could start in the first (leftmost) column of the board. In fact, the only one of the blocks shown above (AI through AVI, BI through BVII, and CI through CVII) which could start in the first column of the board is AI. Blocks AVI and CVI, if they appear, must be preceded (to the left) with a column of 4 guards, each of the blocks AII, AIII, BIII, BV, CI, CIV, and CV must be preceded by a column with at least 3 guards, and BI must be preceded by a column with at least 2 guards. None of them end in a column with 4 guards, and only AVI and CVI end in a column with 3 guards. Furthermore, we can check on a case-by-case basis that, even though BI can be preceded by a column with only 2 guards, it cannot be preceded by any of the other \frac{7}{3}-blocks except for AVI and CVI. From these observations, it follows that at most 2 of these \frac{7}{3}-blocks could appear consecutively as we move across the board from left to right, and if 2 of them do appear consecutively, the first (rightmost) of the two must be either AVI or CVI.

Suppose that two of the \frac{7}{3}-blocks appear consecutively. Since the first (on the left) must be AVI or CVI, the column immediately before the 2 consecutive blocks must contain 4 guards and not be part of any \frac{7}{3}-block. Considering the two consecutive \frac{7}{3}-blocks and the column of 4 guards, we have 7 columns with a total of 14 prisoners, which averages 2 < \frac{9}{4} prisoners per column. We can include the column of 4 guards along with the two consecutive \frac{7}{3}-blocks in a new “megablock” unless the column with 4 guards is already part of a block. It cannot be part of a \frac{7}{3}-block or a \frac{9}{4}-block (CII), but the column with 4 guards might be part of a block that averages 2 prisoners per column (such as A1, AIV, AV, BVI, BVII, or CVII).

So if we include both the two consecutive \frac{7}{3}-blocks and the 2-block immediately before it in a new “megablock”, we have a total of at least 8 columns with at most 2 prisoners per column plus 2 additional prisoners. Since \frac{2t+2}{t} ≤ \frac{9}{4} for t ≥ 8, the “megablock” averages at most \frac{9}{4} prisoners per column. Unless the 2-block is AI, in fact, this new megablock has at most \frac{20}{9} prisoners per column on average. Notice that this “megablock” ends with one of the \frac{7}{3}-blocks, so it has at least one prisoner in its last column. Hence, we maintain the property that a block which ends with a column of 4 guards must average at most 2 prisoners per column.

On the other hand, if a \frac{7}{3}-block appears by itself, then it is preceded by a column C_{i} with at most 2 prisoners. If C_{i} is not part of any block or is part of a block that averages 2 prisoners per column, then we can combine C_{i} or the 2-block containing C_{i} with the \frac{7}{3}-block to form a block with at most \frac{9}{4} prisoners per column. Notice that C_{i} cannot be part of a “megablock” since the “megablocks” end with a \frac{7}{3}-block. We may assume that C_{i} is the last column of CII (or any number of consecutive copies of CII) as shown in Figure 10. But then the column proceeding CII (or the first of the consecutive copies of CII), let’s call it C_{j}, has at most one prisoner. If C_{j} is not part of some other block, then we combine C_{j} with CII (or all of the consecutive copies of CII) and the \frac{7}{3} block to form a megablock with 8 columns and 17 prisoners. The average number of prisoners per column in the megablock is \frac{17}{8} < \frac{9}{4}. If C_{j} is part of a block that averages 2 prisoners per column, then we combine that 2-block,

P P P P P P P P P  P P P P P P P P P P P P P P P P P P P P P P P P  P P P P P P P P P P P P P P P P

Figure 11: The basis for the construction in Theorem 4.

the CII (or all of the consecutive copies of CII), and the \frac{7}{3} block to form a megablock with on average at most \frac{20}{9} < \frac{9}{4} prisoners per column. If C_{j} is part of a \frac{7}{3} block, then it must be either AVI or CVI. But in either of those cases, AVI or CVI must be preceded by a column C_{k} with 4 guards, which is either not part of a block or part of a block with an average of 2 prisoners per column. In either case, we combine C_{k} or the block containing C_{k}, the AVI or CVI block, the CII block (or consecutive copies of CII), and the \frac{7}{3}-block to form a “megablock” with at most \frac{27}{12} = \frac{9}{4} prisoners per column.

Thus, after forming blocks and “megablocks” if necessary, each block has at most \frac{9}{4} prisoners per column, and each column that is not in a block, other than possibly the last column, has at most 2 prisoners. The last column could possibly have 4 prisoners, but then the column prior to it must have 4 guards. Thus, either the last column has at most 3 prisoners, or the next-to-last column has 4 guards and is part of a 2-block with at least 2 columns, or the next-to-last column has 4 guards and is not part of any block. It follows that the number of prisoners is at most the maximum of \frac{9}{4}(n − 1) + 3 = \frac{9}{4}n + \frac{3}{4} or \frac{9}{4}(n − 3) + 2(2) + 4 = \frac{9}{4}n + \frac{5}{4} or \frac{9}{4}(n − 2) + 4 = \frac{9}{4}n − \frac{1}{2} prisoners total.

Theorem 4. For every positive integer n ≥ 4, the maximum number of prisoners satisfies P (4, n) ≥ \frac{9}{4}n − \frac{1}{2}.

Proof. We show a recursive construction. The constructions for n = 4, 5, 6, and 7 are shown in Figure 11. For a construction for 4t + n, with t ≥ 1, insert t copies of the 4-column block for CII shown in Figure 10 after the second column. Specifically, the construction uses \frac{9}{4}n prisoners when n ≅ 0 mod 4, it uses \frac{9}{4}n − \frac{1}{4} prisoners when n ≅ 1 mod 4, it uses \frac{9}{4}n − \frac{1}{2} prisoners when n ≅ 2 mod 4, and it uses \frac{9}{4}n + \frac{1}{4} prisoners when n ≅ 3 mod 4.

P P P P A  P P P P B  P P P P C  P P P P P D

Figure 12: The four possible columns with more than three prisoners.

5 Maximum 5 × n Boards

Theorem 5. For every positive integer n ≥ 5, the maximum number of prisoners satisfies P (5, n) = 3n.

Proof. Since prisoners can be placed in the first, third, and fifth row of a 5 by n rectangle, P (5, n) ≥ 3n. To show that P (5, n) ≤ 3n, we will show that the average number of prisoners per column in any legal arrangement of prisoners and guards is at most 3.

If a column has more than three prisoners, then, up to symmetry, it looks like one of the four columns shown in Figure 12. It is easy to check that if column A, B, or C is the last (rightmost) column, then the column before it has at most one prisoner. If column D is the last (rightmost) column, then the column before it cannot contain any prisoners. We will proceed by showing that if there is a column of type A, B, C, or D in a legal arrangement of prisoners and it is not the last (rightmost) column, then it can be placed in a block with one or two columns to its right that have fewer prisoners so that the average number of prisoners per column in each block is at most three. Then we will consider the case when column A, B, C, or D is the last (rightmost) column separately.

First, consider column A. If the next column to the right has two or fewer prisoners, then we form a block of two columns, and those two columns together average 6/2 = 3 prisoners per column. If column A is the first (leftmost) column, then the top four positions of the next column must all contain guards, and we can always form a block of 2 columns. So we consider the case when A is not the first or last column and the next column has at least 3 prisoners. The topmost prisoner in column A will require at least three guards, at least one of which must be in the first or second row of the next column to the right. The third prisoner down in column A will require at least four guards, at least one of which must be in the second, third, or fourth row of the next column to the right. Thus, there are seven possibilities for the next column to the right of column A that will contain three or more prisoners (see Figure 13). Notice that in each case, there must be at least one more column to the right. For AI, the next column to the right must contain all guards and no prisoners. For AII, AIII, AIV, AV, and AVII, we can check that the next column to the right can have

P P P P P P P AIV  P P P P P P P AV  P P P P P P P AVI  P P P P P P P AVII P P P P P P P P AI  P P P P P P P AII  P P P P P P P AIII

Figure 13: Possible columns right of column A with 3 or more prisoners. In each of these cases, we form a block of 3 columns with the 2 columns shown and one to the right.

at most one prisoner. For AVI, the next column to the right can have at most two prisoners. In each of the cases AI, AII, AIII, AIV, AV, and AVII, we have at most 8 prisoners in 3 columns, for an average of 8/3 < 3 prisoners per column. In case AVI, we have at most 9 prisoners in 3 columns, but in order to have all 9 prisoners, the last column must contain two prisoners.

Next we consider column B. If the next column to the right contains two or fewer prisoners, then we can form a block with those two columns and the block will average at most 6/2 = 3 prisoners per column. If column B is the leftmost (first) column, then there is at most one prisoner in the next column to the right. Thus, we consider the case when column B is not the first (leftmost) or last (rightmost) column, and the next column to the right has at least 3 prisoners. The topmost prisoner in column B must have at least 3 guards, at least one of whom must be in the next column to the right. Thus, there are 9 possibilities for the next column to the right of column B with at least 3 prisoners, as shown in Figure 14.

It is straightforward to check that in each of these nine cases, there must be another column to the right. We will form a block of 3 columns. In cases BI and BII, the next column to the right cannot contain any prisoners. In cases BIV, BV, BVI, BVII, and BIX, the next column to the right can have at most one prisoner, and in cases BIII and BVIII, the next column to the right can have at most two prisoners. In every case except BIII and BVIII, if we group these three columns together, we have at most 8 prisoners in 3 rows, for an average of 8/3 < 3 prisoners per column. In cases BIII and BVIII, we might have 9 prisoners in 3 columns, but only if the third column has at least two prisoners in it.

We consider case C. If the next column to the right has two or fewer prisoners, then we

P P P P P P P BVII  P P P P P P P BVIII  P P P P P P P BIX P P P P P P P BIV  P P P P P P P BV  P P P P P P P BVI P P P P P P P P BI  P P P P P P P P BII  P P P P P P P BIII

Figure 14: Possible columns right of column B with 3 or more prisoners. Again we form blocks of 3 columns including the two columns shown and one to the right.

P P P P P P P CI  P P P P P P P CII  P P P P P P P CIII

Figure 15: Possible columns right of column C with 3 or more prisoners.

can group those two columns together for an average of at most 3 prisoners per column. If column C is the first (leftmost) column, then the next column to the right can have at most 1 prisoner. We will assume that column C is neither the first (leftmost) or last (rightmost) column and that the next column to the right has at least 3 prisoners. Since the first prisoner in column C requires at least 3 guards, at least one of which must lie in the column to the right, one of the top two positions in the next column to the right must contain a guard. Similarly, one of the lower two positions must contain a guard. Up to symmetry, there are only three possibilities for the next column to the right that will have at least three prisoners. See Figure 15. As before, we can easily check that in each of these three cases, there must be at least one more column to the right, and so we will form a block of 3 columns. In cases CII and CIII, the next column to the right can have at most one prisoner, so we may form a block of three columns with at most 8 prisoners and an average of 8/3 < 3 prisoners per column. In Case CI, the next column may have at most two prisoners (in the top and bottom positions). When we form a block of 3 columns, we may have at most 9 prisoners in 3 columns (exactly 3 prisoners per column). However, notice that we do not achieve exactly 3 prisoners per column unless the third column has 2 prisoners.

Finally, we consider case D. If the next column to the right has only one prisoner, then we may form a block of two columns with an average of 3 prisoners per column. If D is the first (leftmost) column, then the next column to the right has no prisoners. We may assume that D is neither the first (leftmost) nor the last (rightmost) column and that the next column to the right has at least two prisoners. In the next column to the right, one of the top two positions must be a guard, at least one of the middle three must be a guard, and at least one of the lower two must be a guard, to guard the top, middle, and lowest prisoners in column D, respectively. Up to symmetry, there are seven possibilities for the next column to the right with at least two prisoners. See Figure 16.

Once again, we can check that in each of these seven cases, there must be at least one more column to the right, and we will form a block of 3 columns. In case DII, the next column to the right cannot have any prisoners, and the block of three columns has 8 prisoners in 3 columns. In cases DI, DIV, DV, and DVI, the next column to the right has at most one more prisoner. In cases DIV, DV, and DVI, we would still have only 8 prisoners in the 3 columns. In case DI, we might have 9 prisoners in 3 columns, but only if the third column

P P P P P P P DVII P P P P P P P DIV  P P P P P P P DV  P P P P P P P DVI P P P P P P P P DI  P P P P P P P P DII  P P P P P P P DIII

Figure 16: Possible columns right of column D with 2 or more prisoners.

P P P P P P P P P P P P P

Figure 17: Case when the last block is C and preceded by a DI block.

has a prisoner in the middle. In cases DIII and DVII, the next column to the right has at most 2 prisoners. The block of 3 columns might have as many as 9 prisoners, but only if the third column has exactly 2.

Thus, any column of the form A, B, C, or D, which is not the last (rightmost) column, is now placed in a block with other columns to the right so that each block averages at most 3 prisoners per column. Finally, we consider the case when the last (right-most) column is A, B, C, or D. First suppose the last column is A, B, or C. It is straightforward to check that the column immediately before it has at most one prisoner. If this column is not already included in a block with some preceding columns, then it can be placed in a block with the last column, and the two columns together average at most 5/2 < 3 prisoners per column. If the next-to-last column is already in a block with some earlier columns so that the block has at most 8 prisoners in 3 columns, then the last column can be added to the block to have 12 prisoners in 4 columns, or 12/4 = 3 prisoners per column. If the next-to-last column is already in a block so that the block has 5 prisoners in 2 columns, then the last column can be added to the block to have 9 prisoners in 3 columns, still at most 3 prisoners per column. Notice that if the next-to-last column is in a block of 2 columns consisting of a D column followed by a column with exactly one prisoner, and then the last column is A, B, or C, then the one prisoner in the next-to-last column has more prisoners than guards as neighbors, which is a contradiction. Thus, if the next-to-last column is in a block of 2 columns, that block must have at most 5 prisoners.

The only remaining case occurs when the next-to-last column is part of a DI block, as shown in Figure 17. In this case, the last column had to be type C. Notice that this configuration has 13 prisoners in only 4 columns, but it is forced to have an empty column before it. If the empty column is not part of some block already, then it can be added to the block and the block will have less than 3 prisoners per column. The only three-column blocks that end in an empty column (AI, BI, BII, or DII followed by an empty column or some other configuration with one or more prisoners missing) average at most 8/3 prisoners per column, and the only two-column blocks that end in an empty column (such as D followed by an empty column) average at most 5/2 prisoners per column. Thus, in this case also, when the DI block and the final column are added to any of these blocks, the resulting configuration averages at most 3 prisoners per column (either 21 prisoners in 7 columns or 18 prisoners in

P P P P P P P P P P P

Figure 18: The construction for P (6, n) ≥ ⌊\frac{11}{3}n⌋.

6 columns).

Finally, we must consider the case when the final column is of type D. It must have an empty column immediately before it. Since the arrangement of prisoners and guards can be reflected, or the argument may be repeated left-to-right instead of right-to-left, we may assume without loss of generality that the first column is also of type D. We will consider the first two columns and the last column together as a single “book-end” block, consisting of two columns of type D and one empty column. This block has 10 prisoners in 3 columns, slightly more than an average of 3 prisoners per column. However, since n ≥ 5, there must be other columns in between which are not in the “book-end” block. The next-to-last column must be empty. If it is not already part of a block, it can be included in the “book-end” block so that the “book-end” block now averages 10/4 < 3 prisoners per column. Otherwise, the next-to-last column is part of a block with at most 8 prisoners in 3 columns or 5 prisoners in 2 columns. In either case, this block can be combined with the “book-end” block to produce a new block with at most 18 prisoners in 6 columns or 15 prisoners in 5 columns. In either case, we have at most 3 prisoners per column.

Thus, we cannot place more than 3n prisoners total. We can place exactly 3n prisoners by putting prisoners in the first, third, and fifth rows. Notice that there may be other configurations that achieve exactly 3n prisoners.

6 Maximum n × m Boards with m > n ≥ 6

Theorem 6. For every positive integer n greater than or equal to 6, the maximum number of prisoners satisfies P (6, n) ≥ ⌊\frac{11}{3}n⌋.

Proof. If n is a multiple of 3, repeat the three columns shown in Figure 18. If n ≅ 1 mod 3, then add the column shown in Figure 19, and if n ≅ 2 mod 3, then add the two columns shown in Figure 20.

P P P

Figure 19: For n ≡ 1 (mod 3), add this column to the construction for P (6, n) ≥ ⌊\frac{11}{3}n⌋.

P P P P P P P

Figure 20: For n ≡ 2 (mod 3), add these columns to the construction for P (6, n) ≥ ⌊\frac{11}{3}n⌋.

Notice that for every odd integer n ≥ 3, an n × m board might have prisoners in every square of each odd-numbered row and guards in every square of each even-numbered row, for a total of \frac{(n+1)m}{2} prisoners.

Observation 7. For every odd integer n ≥ 3 and every integer m ≥ n, the maximum number of prisoners in an n × m board P (n, m) is at least \frac{(n+1)m}{2}.

Ionascu, Pritikin, and Wright [7] gave constructions for the maximum size of a halfdependent set in an n × n king’s graph. A half-dependent set is a valid set of prisoners, since for each vertex (square) in the set, at most half of the neighbors are in the set.

Theorem 8. [7] The maximum size of a half-dependent set in the n×n kings graph satisfies the following lower bounds, for some constant C:

• h(K[n, n]) ≥ \frac{3}{5}n^{2} − \frac{n}{30} − C, if n ≡ 0 (mod 5)

• h(K[n, n)) ≥ \frac{3}{5}n^{2} − \frac{4n}{30} − C, if n ≡ 1 (mod 5)

• h(K[n, n]) ≥ \frac{3}{5}n^{2} − \frac{2n}{30} − C, if n ≡ 2 (mod 5)

• h(K[n, n]) ≥ \frac{3}{5}n^{2} + \frac{3}{5}, if n ≡ 3 (mod 5)

• h(K[n, n]) ≥ \frac{3}{5}n^{2} − \frac{3n}{30} − C, if n ≡ 4 (mod 5)

In light of this result, it is reasonable to conjecture that P (n, m) is on the order of \frac{3}{5}nm for m ≥ n ≥ 3 and n odd.

7 Open questions

Although we have determined the maximum number of prisoners in a valid n × m board for 1 ≤ n < m and n = 1, 2, 3, 5, provided bounds that differ by less than 2 for n = 4, and constructively shown one configuration which achieves that maximum, we have not shown that each configuration is the unique maximum configuration for that board. It would be of interest, especially in playing the prisoners and guards game on rectangular boards, to know if there are other maximum configurations. As in the case with the square boards, it is also possible that there may be maximal configurations, in which neither player can make a move, which are not maximum.

8 Acknowledgments

We would like to thank the referee for many helpful comments and improvements and the editor for grammatical and stylistic suggestions.

References

[1] R. Aharoni, E. C. Milner, and K. Prikry, Unfriendly partitions of graphs, J. Combin. Theory Ser. B 50 (1990), 1–10.

[2] J. P. Bode, H. Harborth, and M. Harborth, King independence on triangle boards, Discrete Math. 266 (2003), 101–107.

[3] G. Chartrand and L. Lesniak, Graphs and Digraphs, 2nd ed., Wadsworth and Brooks/Cole, 1986.

[4] J. E. Dunbar, D. G. Hoffan, R. C. Laskar, and L. R. Markus, α-domination, Discrete Math. 211 (2000), 11–26.

[5] R. D. Dutton, R. Lee, and R. C. Brigham, Bounds on a graph’s security number, Discrete Appl. Math., 156 (2008), 695–704.

[6] T. Howard, E. J. Ionascu, and D. Woolbright, Introduction to the “prisoners and guards” game, J. Integer Seq., 12 (2009), Article 09.1.3.

[7] E. J. Ionascu, D. Pritikin, and S. E. Wright, k-dependence and domination in king’s graph, Amer. Math. Monthly, 115 (2008), 820–836.

[8] J. M. Sigarreta and J. A. Rodríguez, On the global offensive alliance number of a graph, Discrete Appl. Math. 157 (2009), 219–226.

[9] J. Watkins, C. Ricci, and B. McVeigh, King’s domination and independence: a tale of two chessboards, Congr. Numer. 158 (2002), 59–66.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: domination, half-domination, alliance, global offensive alliance.

Received September 17 2013; revised version received January 24 2014; June 3 2014; July 16 2014. Published in Journal of Integer Sequences, July 18 2014. Revised, July 17 2015; July 30 2015.

Return to Journal of Integer Sequences home page.