 |
 |
Recent Issues |
Volume 11, 5 issues
Volume 11
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179
Volume 10, 5 issues
Volume 10
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180
Volume 9, 5 issues
Volume 9
Issue 5, 721–899
Issue 4, 541–720
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–180
Volume 8, 5 issues
Volume 8
Issue 5, 721–900
Issue 4, 541–719
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179
Volume 7, 6 issues
Volume 7
Issue 6, 713–822
Issue 5, 585–712
Issue 4, 431–583
Issue 3, 245–430
Issue 2, 125–244
Issue 1, 1–124
Volume 6, 4 issues
Volume 6
Issue 4, 383–510
Issue 3, 261–381
Issue 2, 127–260
Issue 1, 1–126
Volume 5, 4 issues
Volume 5
Issue 4, 379–504
Issue 3, 237–378
Issue 2, 115–236
Issue 1, 1–113
Volume 4, 4 issues
Volume 4
Issue 4, 307–416
Issue 3, 203–305
Issue 2, 103–202
Issue 1, 1–102
Volume 3, 4 issues
Volume 3
Issue 4, 349–474
Issue 3, 241–347
Issue 2, 129–240
Issue 1, 1–127
Volume 2, 5 issues
Volume 2
Issue 5, 495–628
Issue 4, 371–494
Issue 3, 249–370
Issue 2, 121–247
Issue 1, 1–120
Volume 1, 2 issues
Volume 1
Issue 2, 123–233
Issue 1, 1–121
|
|
 |
 |
|
Abstract
|
Tessellate the plane into rows of hexagons. Consider a subset of
rows of these hexagons,
each row containing
hexagons, forming a rhombus-shaped chessboard of
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
kings
are attacking each other. According to our specific distance metric,
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
. We consider a
generalization of this maximum density problem, instead requiring that no king attacks more
than other kings
for
. For instance
when
the density
is at most
.
For each
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
|
|
|
|