6xN
Optimal Domination Numbers
Solutions and Proofs
Part 1 of 3
6xN Optimal Domination Numbers
D(6,N) = the domination number for a board with 6 rows and N columns.
D(6,1) = 6
------------
D(6,2) = 4
D(6,3) = 4
D(6,4) = 4
D(6,5) = 6
------------
D(6,N+4) = D(6,N) + 4 for N >= 2
Part 2 of 3
6xN Sufficiency Proofs
Sufficiency is proved by showing a feasible solution
using the domination number of knights.
________________________________________________________
D(6,1) <= 6
x
x
x
x
x
x
________________________________________________________
Extendable solution by repeating the first four columns
D(6,2) <= 4 D(6,4k+2) <= 4k+4
- - - - - - - -
- - - - - - - -
x x - x x - x x
x x - x x - x x
- - - - - - - -
- - - - - - - -
\-----/
repeats
________________________________________________________
Extendable solution by repeating the first four columns
D(6,3) <= 4 D(6,4k+3) <= 4k+4
- - - - - - - - - -
- - - - - - - - - -
- x x - x x - - x x
- x x - x x - - x x
- - - - - - - - - -
- - - - - - - - - -
\-----/
repeats
________________________________________________________
Extendable solution by repeating the first four columns
D(6,4) <= 4 D(6,4k) <= 4k
- - - - - - - - - - - -
- - - - - - - - - - - -
- x x - - x x - - x x -
- x x - - x x - - x x -
- - - - - - - - - - - -
- - - - - - - - - - - -
\-----/
repeats
________________________________________________________
Extendable solution by repeating the first four columns
D(6,5) <= 6 D(6,4k+1) <= 4k+2
- - x - - - - - - - - x - -
- - x - - - - - - - - x - -
- - x - - - x x - - - x - -
- - x - - - x x - - - x - -
- - x - - - - - - - - x - -
- - x - - - - - - - - x - -
\-----/
repeats
Part 3 of 3
6xN Necessity Proofs
Necessity is proved by showing that
at least the domination number of knights is required
to cover a subset of the board.
________________________________________________________
D(6,1) >= 6
o Since no square can be attacked,
o all squares must be covered by occupying them.
o
o
o
o
________________________________________________________
D(6,2) >= 4
a - It takes 2 knights to cover the a-squares and 2 knights to cover
b - the b-squares. A single knight cannot cover both an a-square
a - and a b-square, so the two sets of 2 knights are distinct,
b - making 4 in all.
a -
b -
________________________________________________________
D(6,3) >= 4
a - - Same proof as D(6,2).
b - -
a - -
b - -
a - -
b - -
________________________________________________________
D(6,4) >= 4
a - - - Same proof as D(6,2).
b - - -
a - - -
b - - -
a - - -
b - - -
________________________________________________________
Extendable optimality proof by repeating the first four columns.
D(6,5) >= 6 D(6,4k+1) >= 4k+2
a b a - a a b a b a b a - a No single knight can cover squares
- - - - - - - - - - - - - - of more than one different letter,
- - - - - - - - - - - - - - so it takes 4 separate sets of knights.
- - - - - - - - - - - - - - A knight can cover at most 2 squares
- - - - - - - - - - - - - - of a lettered group. So a 3-square
c d c - c c d c d c d c - c group takes 2 knights, a 5-square group
\-----/ takes 3 knights, etc. Every four columns
repeats adds 4 pairs of letters requiring
4 additional knights.
________________________________________________________
Extendable optimality proof by repeating the first four columns.
D(6,6) >= 8 D(6,4k+2) >= 4k+4
a b a b a b a b a b a b a b a b Same proof as D(6,5).
- - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - -
c d c d c d c d c d c d c d c d
\-----/
repeats
________________________________________________________
Extendable optimality proof by repeating the first four columns.
D(6,7) >= 8 D(6,4k+3) >= 4k+4
a b a b a b - a b a b a b a b a b - Same proof as D(6,5).
- - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - -
c d c d c d - c d c d c d c d c d -
\-----/
repeats
________________________________________________________
Extendable optimality proof by repeating the first four columns.
D(6,8) >= 8 D(6,4k+4) >= 4k+4
a b a b a b - - a b a b a b a b a b - - Same proof as D(6,5).
- - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - -
c d c d c d - - c d c d c d c d c d - -
\-----/
repeats
________________________________________________________