Vol. 9, No. 4, 2016

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Arranging kings $k$-dependently on hexagonal chessboards

Robert Doughty, Jessica Gonda, Adriana Morales, Berkeley Reiswig, Josiah Reiswig, Katherine Slyman and Daniel Pritikin

Vol. 9 (2016), No. 4, 699–713
Abstract

Tessellate the plane into rows of hexagons. Consider a subset of $2n$ rows of these hexagons, each row containing $2n$ hexagons, forming a rhombus-shaped chessboard of $4{n}^{2}$ spaces. Two kings placed on the board are said to “attack” each other if their spaces share a side or corner. Placing kings in alternating spaces of every other row results in an arrangement where no two of the ${n}^{2}$ kings are attacking each other. According to our specific distance metric, ${n}^{2}$ is in fact the largest number of kings that can be placed on such a board with no two kings attacking one another, for a maximum “density” of $\frac{1}{4}$. We consider a generalization of this maximum density problem, instead requiring that no king attacks more than $k$ other kings for $0\le k\le 12$. For instance when $k=2$ the density is at most $\frac{1}{3}$. For each $k$ we give constructive lower bounds on the density, and use systems of inequalities and discharging arguments to yield upper bounds, where the bounds match in most cases.

Keywords
$k$-dependence, combinatorial chessboard, optimization, discharging, linear programming
Mathematical Subject Classification 2010
Primary: 90C05, 90C27