Vol. 9, No. 4, 2016

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

Volume 11, 1 issue

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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 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.

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

Communicated by Arthur T. Benjamin
Authors
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