Vol. 9, No. 4, 2016

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
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

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 4n2 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 n2 kings are attacking each other. According to our specific distance metric, n2 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 1 4. We consider a generalization of this maximum density problem, instead requiring that no king attacks more than k other kings for 0 k 12. For instance when k = 2 the density is at most 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.

$k$-dependence, combinatorial chessboard, optimization, discharging, linear programming
Mathematical Subject Classification 2010
Primary: 90C05, 90C27
Received: 22 July 2015
Revised: 31 July 2015
Accepted: 17 September 2015
Published: 6 July 2016

Communicated by Arthur T. Benjamin
Robert Doughty
Miami University
Oxford, OH 45162
United States
Jessica Gonda
The University of Akron
Akron, OH 44304
United States
Adriana Morales
University of Puerto Rico
San Juan, 00931
Puerto Rico
Berkeley Reiswig
Anderson University
Anderson, SC 29621
United States
Josiah Reiswig
University of South Carolina
Columbia, SC 29208
United States
Katherine Slyman
Wake Forest University
Winston-Salem, NC 27106
United States
Daniel Pritikin
Department of Mathematics
Miami University
123 Bachelor Hall
301 S. Patterson Ave.
Oxford, OH 45056
United States