3xN
Optimal Domination Numbers
Solutions and Proofs
Part 1 of 3
3xN Optimal Domination Numbers
D(3,N) = the domination number for a board with 3 rows and N columns.
--------------
D(3, 1) = 3
D(3, 2) = 4
D(3, 3) = 4
D(3, 4) = 4
D(3, 5) = 4
D(3, 6) = 4
D(3, 7) = 6
D(3, 8) = 8
--------------
D(3, 9) = 8
D(3,10) = 8
D(3,11) = 8
D(3,12) = 8
D(3,13) = 10
D(3,14) = 11
--------------
D(3,N+6) = D(3,N) + 4 for N >= 9
Part 2 of 3
3xN Sufficiency Proofs
Sufficiency is proved by showing a feasible solution
using the domination number of knights.
________________________________________________________
D(3,1) <= 3 D(3,2) <= 4 D(3,3) <= 4 D(3,4) <= 4 D(3,5) <= 4
x - - - - - - - - - - - - - -
x x x - x x - - x x - - x x -
x x x - x x - - x x - - x x -
________________________________________________________
D(3,6) <= 4 D(3,7) <= 6 D(3,8) <= 8 D(3,9) <= 8
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - x x - - - - x x x - - - - x x - - x x - - x x - - - x x
- - x x - - - - x x x - - - - x x - - x x - - x x - - - x x
________________________________________________________
D(3,10) <= 8 D(3,11) <= 8 D(3,12) <= 8
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - x x - - - - x x - - x x - - - - x x - - - x x - - - - x x - -
- - x x - - - - x x - - x x - - - - x x - - - x x - - - - x x - -
________________________________________________________
D(3,13) <= 10 D(3,14) <= 11
- - - - - - - - - - - - - - - - - - x - - - - x x - -
- - x x - - - - x x x - - - - x x - - - - - - - - - -
- - x x - - - - x x x - - - - x x - - - x x - - - x x
________________________________________________________
Extendable solution by repeating the first six columns
D(3,6k+15) <= 4k + 12
- - - - - - - - - - - - - - -
- - x x - - - - x x - - - x x
- - x x - - - - x x - - - x x
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(3,6k+16) <= 4k + 12
- - - - - - - - - - - - - - - -
- - x x - - - - x x - - - - x x
- - x x - - - - x x - - - - x x
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(3,6k+17) <= 4k + 12
- - - - - - - - - - - - - - - - -
- - x x - - - - x x - - - - x x -
- - x x - - - - x x - - - - x x -
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(3,6k+18) <= 4k + 12
- - - - - - - - - - - - - - - - - -
- - x x - - - - x x - - - - x x - -
- - x x - - - - x x - - - - x x - -
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(3,6k+19) <= 4k + 14
- - - - - - - - - - - - - - - - - - -
- - x x - - - - x x - - - - x x x - -
- - x x - - - - x x - - - - x x x - -
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(3,6k+20) <= 4k + 15
- - - - - - - - - - - x - - - - x x - -
- - x x - - - - x x - - - - - - - - - -
- - x x - - - - x x - - - x x - - - x x
\---------/
repeats
Part 3 of 3
3xN 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(3,1) >= 3
o Since no square can be attacked,
o all squares must be covered
o by occupying them.
________________________________________________________
D(3,2) >= 4
o o Each of the 4 o-squares must be covered
o o by a different knight.
- -
________________________________________________________
D(3,3) >= 4
a d g The center square can be covered only by occupation.
f o b The 8 outer squares form the cycle, a-b-c-d-e-f-g-h.
c h e A knight can cover 3 adjacent squares in a cycle,
so it takes 3 knights to cover all 8, making 4 knights in all.
________________________________________________________
D(3,4) >= 4
- - - - Each of the 4 o-squares must be covered
o o o o by a different knight.
- - - -
________________________________________________________
D(3,5) >= 4
- - - - - Each of the 4 o-squares must be covered
o o o o - by a different knight.
- - - - -
________________________________________________________
D(3,6) >= 4
- - - - - - Each of the 4 o-squares must be covered
o o o o - - by a different knight.
- - - - - -
________________________________________________________
D(3,7) >= 6
a a - - - - o a's >= 3;
a o - - - - o o's >= 3;
a a - - - - - sum >= 6
________________________________________________________
D(3,8) >= 8
a a - - - - b b a's = b's >= 3;
a o - - - - o b o's >= 2;
a a - - - - b b sum >= 8
________________________________________________________
TO BE CONTINUED
________________________________________________________