Citation
The 2-packing number of 3-D complete grid graphs

Material Information

Title:
The 2-packing number of 3-D complete grid graphs
Creator:
Beel, Sarah R
Publication Date:
Language:
English
Physical Description:
vi, 21 leaves : ; 29 cm

Thesis/Dissertation Information

Degree:
Master's ( Master of Science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Mathematical and Statistical Sciences
Degree Disciplines:
Applied Mathematics
Committee Chair:
Fisher, David C.
Committee Members:
Ryan, Jennifer
Payne, Stanley E.

Subjects

Subjects / Keywords:
Graph theory ( lcsh )
Graph theory ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaf 21).
Thesis:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Applied Mathematics. Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Sarah R. Beel.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
30656540 ( OCLC )
ocm30656540
Classification:
LD1190.L622 1993m .B44 ( lcc )

Downloads

This item has the following downloads:


Full Text
THE 2-PACKING NUMBER
OF 3-D COMPLETE GRID GRAPHS
by
Sarah R. Bed
B.A., University of Colorado at Boulder, 1984
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1993


This thesis for the Master of Science
degree by
Sarah R. Beel
has been approved for the
Department of
Mathematics
by
Date


Beel, Sarah R. (M.S., Applied Mathematics)
The 2-Packing Number of 3-D Complete Grid Graphs
Thesis directed by Associate Professor David C. Fisher
ABSTRACT
The 2-packing number of an /xmxti grid is the maximum number of checkers
which can be placed in cubes of the grid so that any two checkers have at least two
cubes between them. We find the 2-packing number of a 2xraxn grid for all m and
n. We also find the 2-packing numbers of 3x3xn, 3x4xn, 3x7xn, and 4x4xn grids.
This abstract accurately represents
recommend its publication.
the content of the candidates thesis. I
Signed.
David C. Fisher
iii


To my loving husband Jeff


ACKNOWLEDGEMENTS
I would like to thank David Fisher for being such a patient and supportive mentor.
I would also like to thank Jennifer Ryan and Stanley Payne for serving on my thesis
committee and for their helpful suggestions.


CHAPTER
CONTENTS
1. INTRODUCTION .............................. 1
2. THE 2-PACKING HUMBER OF A 2xmxn GRID.........3
3. THE 2-PACKING NUMBER OF A 3xmxn GRID.......11
4. THE 2-PACKING NUMBER OF A 4xmxn GRID .......17
BIBLIOGRAPHY .,.
21
vi


1.INTRODUCTION.
In a 2-packing of an /xmxn grid, checkers are placed inside cubes of the grid
so that any 2 checkers have at least 2 cubes between them. The 2-packing number
az,m,n f an /xmxn grid is the maximum number of checkers in a 2-packing.
Fisher [1]and Fisher and Kellner [2] solve similar problems in 2-
dimensional grids. Fisher [1]found the 2-packing number of Ixmxn grids (i.e., 2-
dimensional grids) for all m and n. We find the 2-packing number of 2xmxn grids
for all m and n. We also find the 2-packing numbers for 3x3xn, 3x4xn, 3x7xn, and
4x4xn grids. General formulas for 2-pacMng numbers of Ixmxn grids for / > 3
remain undetermined.
NOTATION AND TERMINOLOGY.
i. For a real number x, {x} denotes the least integer which is greater than or
equal to x.
ii. Diagrams such as those of Figure 1 below are used to represent 2-packings
of 3-D grids. The words "layer% "column, and "row" refer to mxn&m, and /xn
layers of cubes, respectively. Let 1 represent a checker in the top layer, and let 2,3,
and 4 represent checkers in the 2nd, 3rd, and 4th layers below it. Let the cubes be
indexed i,j,k according to layer, row, and column number, respectively. Then a
dash in square j,k of a 2-D diagram means that cubes i,j,k are empty for i =1 to


OK OK NOT OK NOT OK NOT OK
Checkers in the same layer of a 3-D grid are represented 3 or more positions apart.
1 > mm mmm mm mm mm mmm ^ ^ mmr -mm mm
u_ __ u||| [[[[f ...m. ...it ....
OK OK NOT OK NOT OK
Checkers in adjacent layers of a 3-D grid are represented at least 2 positions
apart.
OK OK NOT OK
Checkers separated by one layer may be represented horizontally or vertically
adjacent.
amm mm>
OK
Chmkers 2 or more layers apart may occupy me same position in a 2-D
representation.
Figure 1:2-D Representations of 2-Packings of a 3-D Grid.
Hare and Hare [3] developed an efricient algorithm for finding n. Fisher
[1]showed that the 2-packing number of a lxmxn grid when m < n is:
%

r
{(m+l)n/6}
{6n/7}
{6n/7} + 1
10
{(mn + 2)/5}
17
{mn/5}
If m = 4 and n mod 7 = 1,
if (m,n) = (7,7),
if m {5,6,7} and (mn)7,7)
if (mn) = (810)
if m S 8 and (m,n) ^ (8,10).


In this paper, 2-packing results for I = 2,3* and 4 are presented. Our
conjectures for amn are based on 2-paddng number output from a program by
Fisher. A modification of the same program generates 2-packing patterns which aid
us in the determination of lower bounds. The following lemma will be used in
proofs for upper bounds of a/ m n:
Lemma 1.For all and j with 0 0,
Proof. A maximal 2-packing of an Ixmxn grid has at most checkers in the
first n-j columns and at most almj checkers in the last j columns.
Figure 2 below is the basis for the following coBjecture;
For l>3 and m,n sufficiently large,
= _/7},
2. THE 2-PACKING NUMBER OF A 2XMXN GRID.
For the 2xmxn case, Theorems 1-B lead to the following results:
Lemma 2. For all m > 0 and n > 0, a2in tl > {mn/3}.
Proof. Any 2-packing is a lower bound for a2>ia>n. Figure 3 partitions 4he cubes of

For n 2 m,
if m =1,
if m = 3 and n is odd, and
otherwise.


Figure 2: Partitioning of a 2xmxn Grid into Seven 2-Packings* Since there are
Imn cubes in a grid, at least one of the seven 2-packings has at least {/mn/7}
checkers.
0-
f15
0 sd
dffof
c/hea
^ead'c
c
0
ado-
o-cfh-
f B e a d
e a d a- c £
e a
d 0C
c/p e
ead 0
ad 0 c £ ^
UM
atf
b>cg
ffcea
@ a d y c
d a- 0 e
e
dg
of15
p 0 sd
Md 0C f
gc z1363
a
go
ffie
eado-
dtn 0£
c ^ e a -wu
d
c f
e a
a d 0 c
/ e a d a-
a3c£iJedgo/ieac?lcfi>eadcfi,eado>f1Jad00^efedgcfead'c/^
e ad
e a d 0- c
0- c f &
*Qea
d 0
f
fh-eada-
adgcf
u/be
0 sd
c
e a d 0- c
d0cfPQ
a d a-
C*H

e adgef
3
d a- c
f UM
a
ad 0- c f
cfIQea
e a d 0
c £
fce
d
d e
/ ^ e a d
a d a- c
e M
0
g c/rQea
0 s d 0
d0cf
f ^ e
a d
c
4


a 2xmxn grid into six 2-packings. Since there are 2mn cubes in the grid, at least
Figure 3: Partitioning of a 2xmxn Grid into Six 2-Packings. The first letter in
the pairs of letters represents checker in one of the two layersand the second
letter of the pairs represents a checker in the layer above or below it.
Fisher [1]showed that ai(2jll=a2>J>n = {n/2}. We find a2,m,nfor all m and
n.
Lemma 3. %,2,2 = 2.
Proof. Figure 4 shows the only way up to symmetry that a 2x2x2 grid can be 2-
packed with 2 checkers. This 2-pacMng prohibits legal placement of a third
checker.
1-
-2
Figure 4: a2A2 = 2. Up to symmetry, there is only one way to 2-pack a 2x2x2
grid.
Lemma 4. a2,2 3 = 2.
one of the six 2-packings has at least {2mn/6} = {mn/3} checkers.
5 c d a £ c
a£cfeed
/ c 0d M
0d sf ap
dafc e
c b e d a /
fcedafc
a f c ^ e d
f c ^ e d a
ed a/c"
d sf CP e
c b e d a -r
^e^a/c
afced


Proof. Figure 5 shows the only 4 ways up to symmetry that a 2x2x3 grid can be
2-packed with 2 checkers. Each case prohibits legal placement of a third checker.
^ mm mm mmm -mm
JL ^
Figure 5: a2>2,3 = 2. Up to symmetry, these are the only 4 ways to 2-pack a 2x2x3
grid
Theorem 1.If n > 0, a2i2,n = {2n/3}.
Proof. By Lemma 2? %>2>n > {2n/3}, Fisher [1]showed that ai>2>2 = aw>i=1.By
Lemma 3, a2A2 = 2. By Lemma 4, a2A3 = 2. Assume the theorem holds for n-3,
Then by Lemma 1 and induction on na2An S a2A3 + a2An4 = 2 + {2(n-3)/3}=
{2n/3}.
Theorem 2. For all n > 0 a2<3,n = 2{n/2}.
Proof. Figure 6 shows that for n > 0, a2>3>n > 2{n/2}. Fisher [1]showed that a.u,3
=%34 = 2. By Lemma 4, a2A3 = 2. By Lemma 1 and induction on n, a23 n <
a2A2 + a2,3n.2 = a2A3 + a2,3 2 = 2 + 2{(n-2)/2} = 2{n/2}.
1. -2 * 1- -2 -2 - -2
2 "2 2 - -2 * 2 -2
Figure 6: Lower Bound for a2 3 M.


Theorem 3. For all n > 0, a.2i4 a {4n/3}.
Proof. Lemma 2 shows that {4n/3} is a lower bound. Fisher [1]showed that aw>4
=a2>4,! = 2. By Theorem 1a2>2,4 = a2,4,2 = 3. By Theorem 2, a2,3,4 = 4 By
Lemma 1 and induction on na2A S a2A3 + a2,4>n_3 = a2A4 + a2,43 = 4 + {4(n-
3)/3} = |4n/3}.
Lemma 5. a2>5j = 9.
Proof. By Lemma 2, a2>5 5 s 9. Suppose a25 5 =10. Since a2>5>1=3 and a2 5 4 =
7, the first column has 3 checkers and Columns 2 to 5 have 7 checkers. Also, since
%,s,2 = 4 and a2>j;3 = 6, there are 4 checkers in Columns 1 and 2 and 6 checkers
in Columns 3 to 5. Since there are 3 checkers in Column 1 and 4 checkers in
Columns 1 and 2, Column 2 must have 1 checker. However, 3 checkers in Column
1 prohibits any checkers in Column 2.
mm mm wmm mm mm
mtm mim mm mm mm
aai Maar -aiMi
mm
mm mmr mm mm, Figure 7; a2>5 5 = 9, If there are 3 checkers m Column 1 of a 2x5xn grid, then
there can be no checkers in Column 2,
Lemma 6. a2>5<6 =10.
Proof. By Lemma 2, a25i6 2:10. By Theorem 1,a2>2>e = 4. By Theorem 2, a2i3>6


=6. By Lemma 15 a2fS^ ^ &2,2,6 + a2,3,6 = 4 + 6 =10.
Lemma 7. a2vs7 =12.
Proof. a2>5>7 > 12 by Lemma 2. Suppose a2iS;7 =13. Since a2i54 = 3 and a2>5)6 =
10, Column 1 has 3 checkers. Since a2s,2 = 4 and a2,5s = 9, Columns 1 and 2
have 4 checkers. If there are 4 checkers in Columns 1 and 2 and 3 checkers in
Column 1,then there must be 1 checker in Column 2, However, 3 checkers in
Column 1 and 1 checker in Column 2 is illegal.
Lemma 8. A 2x5x3 grid cannot be 2-packed with 2 checkers in each of its 3
columns.
Proof. Since a2,3a = 2 and a2A4 = 4, and aw6 = 6, there must be 2 checkers in the
top row and 2 checkers in the bottom row. This is possible only if 4 of the corners
have a checker. However, a checker in 4 of the comers prohibits 2 checkers in the
middle column.
2 ~ 2 12
mm mm mm ym mmm mm* Him
______ _________________________
1-2 2-1
Figure 8: 2 Checkers in Each of the 3 Columns of a 2x5x3 Grid Is Illegal. If
the grid is to be 2-packed with 6 checkers, then 4 of the comers must have a
checker, and, consequently, the middle column cannot have 2 checkers.
Lemma 9. %,5,9 = 15.


Proof. By Lemma 2, a2A9 > 15. Suppose a2,5,9 =16- Since a2,5,2 = 4 and a2,5j
=12, Columns 1 and 2 must have 4 checkers. Also, since a2(5i3 = 6 and a2j5)6 =
10Columns 12, and 3 must have 6 checkers. Since there are 4 checkers in
Columns 1 and 2 and 6 checkers in Columns 1 through 3, Column 3 must have 2
checkers. Since 4 checkers in one column is illegal and 3 checkers in one column
and 1 checker in the adjacent column is also illegal, Columns 1 and 2 must each
have 2 checkers. Then, the assumption that a2>5)9 =16 forces 2 checkers in each
of the first 3 2x5x1 layers, but by Lemma 6, this is illegal.
Theorem 4. If n > 1 and n # 3, a2An = {5n/3}.
Proof. a2j5>n > {5n/3} by Lemma 2. By Theorem 1,b.2X$ = a2(5>2 = 4. By
Theorem 3, a2,4,5 = a2,5,4 = 7. By Lemma 5, a2,5,5 = 9. a25>6 =10 by Lemma 6.
By Lemma 1 and induction on n, for n-6 ^ 1,and n-6 ^ 3, a2)5f ^ a2>^6 + a2i5>n_6
=10 + {5(n-6)/3} = {5n/3}. In Lemmas 5,8, and 9 this result is proven for n =
5, n =7, and n = 9, respectively.
Theorem 5. If n ^ 1,a2>6>n = 2n.
Proof. By Lemma 2, 2n is a lower bound. By Theorem 1 a2i2>6 = a2<6i2 = 4. a2i3<6
=a2i6(3 = 6, by Theorem 2. a2<4>s = a2i6>4 = 3, by Theorem 3. By induction on n
and Lemma 1,a2AB S a2,6>3 + a2-3 = 6 + 2(n-3) = 2n.
Lemma 10. a2f77 = {7(7)/3}=17.
Proof. By Lemma 2, a2jj7 > 17. By Theorem 1,a2>2,7 = 5. By Lemma 7, a2,5)7 =


12. By Lemma 1 a2J7 S a2A7 + a2,57 = 5 + 12 =17.
Lemma !! a2,7J =19.
Proof. By Lemma 2, a2(7>8 > 19. By Theorem 2, a2>3i8 = 8. By Theorem 3, a2j4ig
=11,By Lemma 1a2>7,g S a2,3s + a2.4>8 = 8 + 11=19.
X^0HUU£l ^279 = 21,
Proof, By Lemma 2, a2,7,9 > 21,By Theorem 1a2>2,9 = 6, By Theorem 4, a2,519
=15. By Lemma 1a2J>9 S a2A9 + a2,5,9 = 6 + 15 = 21.
Theorem 6. If n > 0 and n ^ {1,3}, a2(7 Proof. By Lemma 2, a2j7iD ^ {7n/3}. By Theorem 1,a2t2>7 = a2(7i2 = 5. By
Theorem 3, a2>4.7 = a2i7j4 = 10. By Lemma 7, a2(5,7 = a2f7t5 =12. By Theorem 5,
a2>6,7 = %7,* =14. Lemmas 10,11, and 12 prove the result for n = 7, n = 8, and
n = 9, respectively. By Lemma 1 and induction on n, for n > 9, a2 7n < a2>7t6 +
a2,7,n-4 =14 + {7(n-6)/3} = {7n/3}.
Theorem 7. If n > 0 and n ^ 1,a2,g>a = {8n/3}.
Proof. a2,M > {8n/3} by Lemma 2. By Theorem 1a2Ag = a2A2 = 6. By
Theorem 2, a2>3(8 = a2>8j3 = 8. By Theorem 3, a2>4>s = a2jg>4 =11.By induction on
n and Lemma 1,a2>g,a < a2>8(3 + a2i8iI1.3 = 8 + |8(n-3)/3} = {8n/3}.
Theorem 8. If n > 0 and n ^ a2(9>n = 3n,
Proof. a2)9(B ^ 3n by Lemma 2. By Theorem 1,a2i2,9 = a2>9i2 = 6. By Theorem
3, a2A9 = a2,914 =12. By Lemma 9, a2s9 = a2,9s =15. By Lemma 12, a2,7,9 =
10


&2,9,7 = 21.By Lemma 1 and induction on na2An < a2A4 + a2AnJl=12 + {9(n_
4)/3)} = 3n.
Theorem 9. If m,n > 4 then a2>Isn = {mn/3}.
Proof. By Lemma 2, for all m > 0 and n > 0, s {mn/3}. Without loss of
generality, assume m < n. If 4 < m < 9, the result follows from Theorems
3,4,5,6,7, and 8. For m > 9, assume the result holds for m-6. By Lemma 1 and
induetion on m, %^%6n + %mi4n = *2n += {rrm/3h
3. THE 2-PACKMG NU3MBER OF A 3XMXN GRID.
We present our findings for the 3xmxn case, Fisher [1]proved that a13 n =
%,i,a ~ {2n/3}. By Theorem 2, a23ja = a3i2>B = 2{n/2}. For 2 < m < 8, our
conjectures for a3mn are based on Fishers program results. Conjectures for a3>3>nJ
a3(4n and a3t7n are proven as Theorems 10,11,and 12, respectively. We also
present some program results which support our conjectures for a3>5>n, a3 6 a, and
a3 gns and we explain why these hypotheses are not proven. In our closing remarks
for this chapter, we explain why a general formula for remains undetermined.
Lemma 13. a3>33 = 5,
Proof. Figure 9 shows that a3(3>3 > 5, Suppose a3>3>3 = 6. Since by Theorem 2,
%3 = a33,2 = 4, and since Fisher [1]showed that a!,3,3 = a3,34 = 2f Columns 1


and 2 must have 4 checkers and Column 3 must have 2 checkers. Also, since by
Theorem 1,a2,2t3 = a3)2>2 = 2, and by Theorem 2, a2>34 = a3<1>2 = 2, the only way
up to symmetry to pack the first 2 columns with 4 checkers is as shown in Figure
9. However, 4 checkers in Columns 1 and 2 prohibits legal placement of 2
checkers in Column 3.
2
3 1-
Figure 9. a3A3 = S.
Theorem 10. For all n>0, a3 3 n = {5n/3}.
Rroof. Figure 10 shows that for n > 0, a3 3 n > |5n/3}. Fisher [1]showed that
ai,3,3 = %,3,1=2. By Theorem 2, a2>3>3 = a3,3>2 = 4. By Lemma 13, a3,3>3 = 5.
By Lemma 1 and induction on n, a3)3>0 < a3,3,3 + a3,3'n.3 = 5 + {5(n-3)/3}=
{5n/3}.
1 3 1 3 1 3
- 2 2 _
3 1 _ 3 1 _ 3 1
Figure 10: Lower Bound Pattern for a3 3 n
Theorem 11.For n t {1,3}, a3Ali = 2n.
12


Proof. The pattern in Figure 11 shows that 2n is a lower bound for a3s4n. By
Theorem 2, a2>3j4 = a3A2 = 4, Fisher's program proves that a34 5 =10. By
Lemma 1 and induction on n, a34tB < a3(4>2 + a3t4ill.3 = 4 + 2(n-2) = 2n.
1 i t t
Figure 11:a3>4lt Ss 2n.
Our conjecture for the 2-packing number of a 3x5xn grid is as follows:
%,5n = {03n+6)/14} for n {1,3,1619}.
Fisher's program proves this result for 1 which is the only 3x5xn grid for 1 {(33n+6)/14) checkers.
1 3 - -1
3 1 -3 _ 1
-2 2
1 _ 3 -1 3
3 1- -3 1
Figure 12: aw :18. A 3x5x7 grid can be packed with 18 checkers.
Although our computer-generated 3x5xn 2-oacMng patterns for 1 < n < 66
support that our a3i5>tl conjecture is a lower bound for n > 19, proving that a3 5 n <
13


{(33n+6)/14} is problematic. Note that in all theorems proven in this paper, the
upper bound arguments are straightforward. In ail of these theorems k is determined
such that ai>mk agrees with the conjectured n-dependent 2-packing formula, and a!)ttii.
+ a,>m>n.k is equivalent to this formula. Hence, induction on n and Lemma 1 are
used to prove upper bounds for these cases. For the 3x5xn case, however, there
appears to be no k such that a35k = {(33k+6)/14) and a3>5>k + a3,5,n_k =
{(33n+6)/14).
One interesting and typical example of a fully packed 3x5xn grid is
presented in Figure 13 below. Note the 2 alternating 14-column patterns and that
one of the two patterns is an inversion of the other.
-2-1-31-31-2-13-13-2-31-31-3-2-1-31-31-2-13-13-2-1
3-1--13-1-311-331-3-133-113-1-311-331-
X-31-2-13-13-1-2-3-13-13-2-31-31-Z-13-13-1-Z-3-13-
Figure 13: 2-Packing Pattern for a Maximally 2-Packed 3x5x50 Grid.
Our conjecture for the 2-packing number of a 3x6xn grid is as follows:
a3A = {(14n+2)/5} for n {3,8}.
For 1 < n < 66, Fisher's program proves this result and that no 2-paddng number
exceeds {(14n+2)/5}. The reasons that this conjecture for a3i6i is difficult to prove
are analogous to those given for the difficulty of proving the a3>5>n conjecture. We
14


present an interesting 3x6xn 2-pacMng pattern in Figure 14 below.

Figure 14: 2-Packing Pattern for a Maximally 2-Packed 3x6x48 Grid.
Proof. Figure 15 verifies that a3 7n > {10n/3} if n mod 3 G {0,1}, and that a3 7n
> {10n/3} + l if n mod 3=2. For n mod 3 = 0 let n = 3k; for n mod 3 = 1,
let n = 3k+l; for n mod 3 = 2,let n = 3k+2. By Theorem 2, =a3j7-2 = 8.
By Theorem 11? a3i4)7 = a3>7>4 =14. Fishery program proves that a3j!5 =18, a3i76
=20, a3)7>7 = 24, and that a3i7>9 = 30. By Lemma 1 and induction on n, a3J>3k <
a3,7,6 +%,7,3k-6 = 20 + (10(3k-6)/3} = {10n/3}; a3j7;3k+t ^ %,7,6 + a3,7,3k-5 = 20 +
{10(3k-5)/3}=10k+4 = {10(3k+l)/3} = {10n/3}; a3,7,3k+2 < a3>7>6 + a3,?(3M =
20 + {10(3k-4)/3} + 1=10k+8 = {10(3k+2)/3} + 1={10n/3} + 1.
Fisher5s program proves the following conjecture for the 2-pacMng number
of a 3x8xn grid for 1 < n ^ 55:
For n {12,3,7,8}
Theorem 12. a3 7,
{10n/3} if n mod 3 e {0,1} and n ^ {1,3}.
{10n/3} + l if n mod 3 = 2.
if n mod 15 {6,9,12},
if n mod 15 {6,9,12}.
15


1 3 1 3 1 3 JL - 3
- 2 - 2 2 - - 2
3 1 3 1 3 1 3 2
1 3 1 3 1 3 1 3
2 _* 2 - 2 . 2
3 1 3 1 3 1 3 1
Figure 15: Lower Bound Pattern for a 3x7xu Grid.
Our a3 g conjecture remains unproven since its proof poses problems comparable
to those we encountered in attempting to prove our a3>5tn and a3 6n hypotheses. An
interesting 2xBxn 2-packing pattern is presented in Figure 16 below.
13-1-2-31-2-31-2-31-31-31-31-31-31-2-31-2-31-2-3-13
3-l~-2'~-2--2--2*23-l__
----~~1--
32--I3-13-13-i3-~23--l-3l3-13-13-13-132-1
2~31-3131~31-3l-312312-31-2-31-31-31-31-3i3l2
Figure 16: 2-Packing Pattern for a Maximally 2-Packed 3x8x51 Grid.
No trend suggesting a general formula for a3(nJin emerges from the 3xmxn
results above. Recall our hypothesis that for / > 3 and sufficiently large m and n,
ai>m,n = {lmn/7}. Hence, for the 3xmxn case we seek evidence that {3mn/7} is the
greatest lower bound for all m,n sufficiently large. Consider Figure 16 below,
which is a lower bound pattern for any 3xmxn grid. If j and k are positive integers,
m = 4J-1, and n = 3k+2, we see that this grid pattern is packed with 5jk+4j
16


checkers. Then j = (m+l)/4, k = (n-2)/3, and 5jk+4j = (m+l)(5k+2)/12. If
m = n = 47, then (m+l)(5n+2)/12 = 948 > {3mn/7} = 947. Hence, if a3jm>n
={3mn/7} for some m,n > n, then n0 must be greater than 47. Our method for
determining a3 ffi would require close scrutiny of computer-generated 2-packing
patterns for grids larger than 3x47x47. The prohibitively long qpu time required
to ran Fisher's program on a high speed computer for grids this large prevents us
from determining a3imn completely.
1 3 2 1 3 2 1 3 2 1 3
3 1 3 1 3 1 3 1
1 3 2 1 3 2 1 3 2 1 3
3 1 3 1 3 1 3 1
1 3 1 3 1 3 1 3
2 2 2
Figure 17: 2-Packing Pattern for a 3xmxn Grid
4. THE 2-PACKING NUMBER OF A 4XMXN GRID.
We present our findings for the 2-packing numbers of 4xmxn grids. Fisher
[1]proved that aj 4>n = a4 i>n = {6n/7} if n mod 7^1 and a4jl n = {6n/7} + 1 if
n mod?=1,By Theorem 3, a2>4 n = a4 2 n = {4n/3). By Theorem 11,a3 4 n =
a4,3n = 2n for n We determine a4,4(see Theorem 13)and present
17


conjectures without proof for 845 ,, and 84¢ By analogy to our unproven a3 5 nJ
%,6,n ^ a3,8,a conjectures, our method of proof is unduly complicated for our 34 5jIJ
and a4i6>a hypotheses.
The cpu time constraints for running Fisher's program prevent us from
collecting sufficient data for the analysis which our method of determining 2-
packing numbers requires. For this reason, a general formula for a4>inii remains
undetermined.
Theorem 13. For n {1,2,4,5,6,8,10,12},^ = {5n/2}.
Proof. The pattern in Figure 18 below verifies that 84 4n > {5n/2} for n E
(3,7,911} and n > 13. By Theorem 11a3,4,4 = a4,4>3 = 8. Fishers program
proves the result for n {7,11131516,1819,20,22,24,26}. By Lemma 1 and
induction on n, a4>4ift < a44jl4 + 3l4Ab_14 = 35 + {5(n-14)/2} = {5n/2}.
Our conjecture for the 2-packing number of a 4x5xn grid is as follows:
Forn ^ {2,3,5,6,10},
=3n+2,
3 1 4 -1 4 2 -3 1 4 - 2 4 2 -3
- 2 -3 41- 2 3 41-
2 41 ^ 3 2 41 _ 3 -2
4 1 3 2 4 1 - 4 1 3 2 4 1 3
Figure 18: Lower Bound Pattern for a 4x4xn Grid.
18


Fisher's program proves this conjecture for 1 < n < 66, An interesting example
of a 4x5xn 2-packing pattern is given in Figure 19 below:
- 2 1 - 4 1 - 4 2 * 14 - 3 1 -
u - - - 2 - - 3 1 - 3 - 2 - 4 2
- 3 1 k 1 h - 4 1 - 4 1 ***
2 - - 2 - 3 1 3 - - 2 2 k
4 1 3 1 U 2 4 1 4 - 1 h - 1
4 1 - 4 1 4 2 3 1 ~ 4 1
- - 2 - * 3 1 - 3 - 2 - 4 2t ~ -
1 k - 1 k - - 1 - k 1 - - 1 k
- 2 - 3 - 1 3 - - Z - - 2 4 - Z
3 - U - 2 4 - 1 4 - 1 4 1 3 -
Figure 19; 2-Packing Pattern for a Maximally 2-Packed 4x5x32 Grid.
Our conjecture for 34 6 b is as follows:
For n ^ {16,25},
&4>6>0 = f{46n/13}+2 if n mod 13 ^ {4,6},
^{46n/13}+l if n mod 13 {4,6}.
Fisher^ program proves this conjature for 1 < n < 44. An example of a
maximally 2-packed 4x6xn grid is given in Figure 20 below.
- 2 4 1 - k 2 - 3
- - 3 - 1 ~ 4 1 -
3 1 4 - 3 - - 3
Z ~ 4 - 1 - - % b 1
4 2 - 3 - 14 - - -
1 3 14 - 2 - 3 1 4
1 3 - 14 - 2 4 i -
4 - 2 - 3 ~ 1 3 4
- i 4 - 1 4 - - - 2
- - - 3 - 2 - 4 1 _
2 4 - 1 4 - 1 - 3 ~
- 1 3 - 2 - k 2 - 14
3 - 1 3 - 14 ~ 2 4 1
1 - 4 - 2 - 3 - - 3
- 3 ~ 1 4 - 1 k 2 -
k X ~ 3 - 2 - - - 14
2 - 4 - 1 4 1 3 -
- 3 l - 3 - 2 4 - 2
Figure 20: 2-Packing Pattern for a Maximally 2-Packed 4x6x30 Grid.
As explained in the opening remarks for this chapter, the limitations of our
means for gathering the data on which our 2-packing number determination depends
19


prevent us from finding a general formula for a* ,,, ,,. In particular, we are unable
to acquire additional data which might support our conjecture that for / > 3 and
sufficiently large m and n, a,>nl>0 = {lmn/7}. At present, we lack evidence that a4 m
={4mn/7}.
20


BIBLIOGRAPHY
Fisher, D.C., "The 2-Packing Number of Complete Grid Graphs", to appear
in Ars Combinatoria.
Fisher, D.C, and Kellner, B., "The 3-Packing Number of Complete Grid
Graphs", to appear in Ars Combinatoria.
E.O. Hare and W.R. Hare, "k-PacMng of P, x Pn", Congressus
Numerantium, 84 (1991) 33-39.


Full Text

PAGE 1

THE 2-PACKING NUMBER OF 3-D COMPLETE GRID GRAPHS by Sarah R. Beel B.A., University of Colorado at Boulder, 1984 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1993

PAGE 2

This thesis for the Master of Science degree by Sarah R. Bee! has been approved for the Department of Mathematics by David C. Fisher E. Payne Date

PAGE 3

Beel, Sarah R. (M.S., Applied Mathematics) The 2-Packing Number of 3-D Complete Grid Graphs Thesis directed by Associate Professor David C. Fisher ABSTRACT The 2-packing number of an lxmxn grid is the maximum number of checkers which can be placed in cubes of the grid so that any two checkers have at least two cubes between them. We find the 2-packing number of a 2xmxn grid for all m and n. We also find the 2-packing numbers of 3x3xn, 3x4xn, 3x7xn, and 4x4xn grids. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. Signed c l1l bavid C. Fisher

PAGE 4

To my loving husband Jeff

PAGE 5

ACKNOWLEDGEMENTS I would like to thank David Fisher for being such a patient and supportive mentor. I would also like to thank Jennifer Ryan and Stanley Payne for serving on my thesis committee and for their helpful suggestions. v

PAGE 6

CHAPTER 1. 2. 3. CONTENTS INTRODUCTION . . . . . . . . . . . . . . 1 THE 2-PACKING NUMBER OF A 2xmxn GRID ........ 3 THE 2-PACKING NUMBER OF A 3xmxn GRID . . . 11 4. THE 2-PACKING NUMBER OF A 4xmxn GRID . . . 17 BIBLIOGRAPHY .................................... 21 vi

PAGE 7

1. INTRODUCTION. In a 2-packing of an lxmxn grid, checkers are placed inside cubes of the grid so that any 2 checkers have at least 2 cubes between them. The 2-packing number a1mn of an lxmxn grid is the maximum number of checkers in a 2-packing. Fisher [1] and Fisher and Kellner [2] solve similar problems in 2-dimensional grids. Fisher [1] found the 2-packing number of lxmxn grids (i.e., 2-dimensional grids) for all m and n. We find the 2-packing number of 2xmxn grids for all m and n. We also find the 2-packing numbers for 3x3xn, 3x4xn, 3x7xn, and 4x4xn grids. General formulas for 2-packing numbers of lxmxn grids for l 3 remain undetermined. NOTATION AND TERMINOLOGY. 1. For a real number x, { x} denotes the least integer which is greater than or equal to x. n. Diagrams such as those of Figure 1 below are used to represent 2-packings of 3-D grids. The words "layer", "column", and "row" refer to mxn, lxm, and lxn layers of cubes, respectively. Let 1 represent a checker in the top layer, and let 2,3, and 4 represent checkers in the 2nd, 3rd, and 4th layers below it. Let the cubes be indexed i,j,k according to layer, row, and column number, respectively. Then a dash in square j ,k of a 2-D diagram means that cubes i,j ,k are empty for i = I to l. 1

PAGE 8

1 ----1 OK 2 -2 OK 3 3 -NOT OK 4 --4 -NOT OK 1 1 NOT OK Checkers in the same layer of a 3-D grid are represented 3 or more positions apart. 1 ---3 4 -2 3 --23 --2 -OK OK NOT OK NOT OK Checkers in adjacent layers of a 3-D grid are represented at least 2 positions apart. 1 3 -OK 2 ---4 --OK 13 --NOT OK Checkers separated by one layer may be represented horizontally or vertically adjacent. 14 --OK ChGekers 2 or more layers apart may occupy the same position in a 2-D representation. Figure 1: 2-D Representations of 2-Packings of a 3-D Grid. Hare and Hare [3] developed an efficient algorithm for finding a,,n Fisher [1] showed that the 2-packing number of a 1xmxn grid when m ::::; n is: a l,m,n -{(m+ 1)n/6} {6n/7} {6n/7} + 1 10 {(mn + 2)/5} 17 {mn/5} 2 if m E {1,2,3}, if m = 4 and n mod 7 ,c 1, if m = 4 and n mod 7 = 1, if (m,n) = (7,7), if m E {5,6,7} and (m,n) ,c (7,7), if (m,n) = (8,10), ifm;::: 8 and (m,n) ,c (8,10).

PAGE 9

In this paper, 2-packing results for l = 2,3, and 4 are presented. Our conjectures for a1,m,n are based on 2-packing number output from a program by Fisher. A modification of the same program generates 2-packing patterns which aid us in the determination of lower bounds. The following lemma will be used in proofs for upper bounds of a1.m,n: Lemma 1. For all/,m,n, and j with O 0, az 0 and n > 0, a2mn {mn/3}. Proof. Any 2-packing is a lower bound for a2,m,n Figure 3 partitions the cubes of 3

PAGE 10

abc d e f g c d e f g a b e f g a b c d g a b c de f b c d e f g a d e f g a b c f g a b c d e d e f g a b c f g a b c d e a b c d e f g c d e f g a b e f g a b c d g a b c d e f b c d e f g a g a b c d e f b c d e f g a d e f g a b c f g a b c d e a b c d e f g c d e f g a b e f g a b c d c d e f g a b e f g abc d g a b c d e g b c d e f g a d e f g a b c f g a b c d e a b c d e f g f g a b c d e a b c d e f g c d e f g a b e f g a b c d g a b c d e f b c d e f g a d e f g a b c b c d e f g a d e f g a b c f g a b c d e a b c d e f g c d e f g a b e f g a b c d g a b c d e f e f g a b c d g a b c de f b c d e f g a d e f g a b c f g a b c d e a b c d e f g c d e f g a b Figure 2: Partitioning of a 2xmxn Grid into Seven 2-Packings. Since there are lmn cubes in a grid, at least one of the seven 2-packings has at least {lmn/7} checkers. 4

PAGE 11

a 2xmxn grid into six 2-packings. Since there are 2mn cubes in the grid, at least one of the six 2-packings has at least {2mn/6} = {mn/3} checkers. ab ed ef ab ed ef ab fe ba de fe ba de fe ed ef ab ed ef ab ed ba de fe ba de fe ba ef ab ed ef ab ed ef de fe ba de fe ba de Figure 3: Partitioning of a 2xmxn Grid into Six 2-Packings. The first letter in the pairs of letters represents a checker in one of the two layers, and the second letter of the pairs represents a checker in the layer above or below it. Fisher [l] showed that a1 2,u = a2 1,n = {n/2}. We find a2,m,n for all m and n. Lemma 3. a22z = 2. Proof. Figure 4 shows the only way up to symmetry that a 2x2x2 grid can be 2-packed with 2 checkers. This 2-packing prohibits legal placement of a third checker. 1 --2 Figure 4: a2 2 2 = 2. Up to symmetry, there is only one way to 2-pack a 2x2x2 grid. Lemma 4. a223 = 2. 5

PAGE 12

Proof. Figure 5 shows the only 4 ways up to symmetry that a 2x2x3 grid can be 2-packed with 2 checkers. Each case prohibits legal placement of a third checker. 1 1 1 1 2 2 --1 -2 Figure 5: a2 2 3 = 2. Up to symmetry, these are the only 4 ways to 2-pack a 2x2x3 grid. Theorem 1. If n > 0, a 2 2,n = {2n/3}. Proof. By Lemma 2, {2n/3}. Fisher [1] showed that a1 ,2 ,2 = a 2 2 1 = 1. By Lemma 3, a 2 2 2 = 2. By Lemma 4, a 2 2 ,3 = 2. Assume the theorem holds for n-3. Then by Lemma 1 and induction on n, a2 ,2,n a 2 2 ,3 + a 2 2,n.3 = 2 + {2(n-3)/3} {2n/3}. Theorem 2. For all n > 0, a 2 3,n = 2{n/2}. Proof. Figure 6 shows that for n > 0, a 2 ,3,n 2{n/2}. Fisher [1] showed that a12 3 = a 2 ,3 1 = 2. By Lemma 4, a 2 2 3 = 2. By Lemma 1 and induction on n, a2 ,3,n :s; a2,3,2 + a2,3,n-2 = a2 ,2 ,3 + a 2 ,3,n.2 = 2 + 2{(n-2)/2} = 2{n/2}. 1 2 1 2 1 2 2 1 2 1 2 1 Figure 6: Lower Bound for a2 3,n 6

PAGE 13

Theorem 3. For all n > 0, a2 ,4,n = {4n/3}. Proof. Lemma 2 shows that {4n/3} is a lower bound. Fisher [1] showed that a1 2 4 = a 2 4 ,1 = 2. By Theorem 1, a2 2 ,4 = a 2 4 ,2 = 3. By Theorem 2, a2 ,3 4 4. By Lemma 1 and induction on n, a2 ,4,n ::; a2 ,4 3 + a2 ,4,n_3 = a2,3,4 + a 2,4,n-J = 4 + {4(n3)/3} = {4n/3}. Lemma 5. a255 = 9. Proof. By Lemma 2, a2 5 5;;;:: 9. Suppose a2 5 5 = 10. Since a2 5 1 = 3 and a2 5 4 = 7, the first column has 3 checkers and Columns 2 to 5 have 7 checkers. Also, since a 2 ,5 2 = 4 and a2 5 ,3 = 6, there are 4 checkers in Columns 1 and 2 and 6 checkers in Columns 3 to 5. Since there are 3 checkers in Column 1 and 4 checkers in Columns 1 and 2, Column 2 must have 1 checker. However, 3 checkers in Column 1 prohibits any checkers in Column 2. 1 ----2 -------1 -------Figure 7: a2 5 5 = 9. If there are 3 checkers in Column 1 of a 2x5xn grid, then there can be no checkers in Column 2. Lemma 6. a2 56 = 10. Proof. By Lemma 2, a2 5 6 ;;;:: 10. By Theorem 1, a 2 ,2 6 = 4. By Theorem 2, a 2 ,3 6 7

PAGE 14

= 6. By Lemma 1, a2 5 6 ::; a2 2 6 + a2 3 6 = 4 + 6 = 10. Lemma 7. a2 5 7 = 12. Proof. a2 5 7 ;;=: 12 by Lemma 2. Suppose a2 5 7 = 13. Since a2 5 1 = 3 and a2 5 ,6 = 10, Column 1 has 3 checkers. Since a2 5 2 = 4 and a2 5 5 = 9, Columns 1 and 2 have 4 checkers. If there are 4 checkers in Columns 1 and 2 and 3 checkers in Column 1, then there must be 1 checker in Column 2. However, 3 checkers in Column 1 and 1 checker in Column 2 is illegal. Lemma 8. A 2x5x3 grid cannot be 2-packed with 2 checkers in each of its 3 columns. Proof. Since a2 3 1 = 2 and a2 3 4 = 4, and a3 3 6 = 6, there must be 2 checkers in the top row and 2 checkers in the bottom row. This is possible only if 4 of the corners have a checker. However, a checker in 4 of the comers prohibits 2 checkers in the middle column. 1 2 1 2 or 1 2 2 1 Figure 8: 2 Checkers in Each of the 3 Columns of a 2x5x3 Grid Is Illegal. If the grid is to be 2-packed with 6 checkers, then 4 of the corners must have a checker, and, consequently, the middle column cannot have 2 checkers. Lemma 9. a2 ,s,9 = 15. 8

PAGE 15

Proof. By Lemma 2, a2 5 9 ;;:: 15. Suppose a2 5 9 = 16. Since a2 5 2 = 4 and a2 5 7 = 12, Columns 1 and 2 must have 4 checkers. Also, since a2 53 = 6 and a2 56 = ' 10, Columns 1 ,2, and 3 must have 6 checkers. Since there are 4 checkers in Columns 1 and 2 and 6 checkers in Columns 1 through 3, Column 3 must have 2 checkers. Since 4 checkers in one column is illegal and 3 checkers in one column and 1 checker in the adjacent column is also illegal, Columns 1 and 2 must each have 2 checkers. Then, the assumption that a2 5 9 = 16 forces 2 checkers in each of the first 3 2x5xl layers, but by Lemma 6, this is illegal. Theorem 4. If n > 1 and n ;C 3, a2 5,. = {5n/3}. Proof. a2,s,. ;;:: {5n/3} by Lemma 2. By Theorem 1, a2 2 5 = a2 5 2 = 4. By Theorem 3, a2 4 5 = a2 ,5 ,4 = 7. By Lemma 5, a2 ,5 5 = 9. a2 5 ,6 = 10 by Lemma 6. By Lemma 1 and induction on n, for n-6 ;e 1, and n-6 ;C 3, a2,s,n a2 5 6 + a2 5 . 6 = 10 + {5(n-6)/3} = {5n/3}. In Lemmas 5,8, and 9 this result is proven for n = 5, n = 7, and n = 9, respectively. Theorem 5. If n ;C 1, a2 6,. = 2n. Proof. By Lemma 2, 2n is a lower bound. By Theorem 1 a2 ,z,6 = a2 6,z = 4. a2,,,6 = a2,6,3 = 6, by Theorem 2. a2 4 6 = a2 ,6 4 = 3, by Theorem 3. By induction on n and Lemma 1, a2 6,. a2 6 3 + a2 6 . 3 = 6 + 2(n-3) = 2n. Lemma 10. a2 ,1, 7 = {7(7)/3} = 17. Proof. By Lemma 2, a2 ,1, 7 ;;:: 17. By Theorem 1, a2 2 7 = 5. By Lemma 7, a2 5 7 = 9

PAGE 16

12. By Lemma 1, a2 7 7 :s; a2 2 7 + a2 5 7 = 5 + 12 = 17. Lemma 11. a2 7 8 = 19. Proof. By Lemma 2, a278 19. By Theorem 2, a2 3,s = 8. By Theorem 3, a2 ,s = 11. By Lemma 1, a2 7 8 :s; a2 3 8 + az..s = 8 + 11 = 19. Lemma 12. a2 7 = 21. Proof. By Lemma 2, a2 7 9 21. By Theorem 1, a2 2, = 6. By Theorem 4, a25 = 15. By Lemma 1, a279:s; a229 + a25 = 6 + 15 = 21. , ' Theorem 6. If n > 0 and n 1/:. {1,3}, a2 7 ,n = {7n13}. Proof. By Lemma 2, a27 {7n13}. By Theorem 1, a2 2 7 = a2 7 2 = 5. By Theorem 3, a2 4 7 = a2 7.4 = 10. By Lemma 7, a2 5 7 = a2 7 5 = 12. By Theorem 5, a2 6 7 = a2 7 6 = 14. Lemmas 10,11, and 12 prove the result for n = 7, n = 8, and n = 9, respectively. By Lemma 1 and induction on n, for n 9, a2 7,n :s; a2 7 6 + a2 7,n_6 = 14 + {7(n-6)/3} = {7n13}. Theorem 7. Ifn > 0 and n 1, a2,s,n = {8n/3}. Proof. a2,s,n {Sn/3} by Lemma 2. By Theorem 1, a2 2 8 = a2 8 2 = 6. By Theorem 2, a2 3 8 = a2 8 3 = 8. By Theorem 3, a2 4 8 = a2 8 4 = 11. By induction on nand Lemma 1, a2 8 ,n :s; a2 8 3 + a2 8 3 = 8 + {8(n-3)/3} = {8n/3}. Theorem 8. If n > 0 and n 1/:. { 1,3}, a2 9 ,n = 3n. Proof. a2 9 ,n 3n by Lemma 2. By Theorem 1, a2 2 9 = a2 9 2 = 6. By Theorem 3, a2 4 9 = a2 9 4 = 12. By Lemma 9, a2 5 9 = a2 9 5 = 15. By Lemma 12, a2 7 9 = 10

PAGE 17

a2 9 7 = 21. By Lemma 1 and induction on n, a2 9,n ::;; a2 9 4 + a2 9,n4 = 12 + {9(n4)/3)} = 3n. Theorem 9. If m,n ;::: 4 then a2mn = {mn/3}. Proof. By Lemma 2, for all m > 0 and n > 0, a2,m,n ;::: {mn/3}. Without loss of generality, assume m ::;; n. If 4 ::;; m ::;; 9, the result follows from Theorems 3,4,5,6,7, and 8. Form > 9, assume the result holds for m-6. By Lemma 1 and induction on m, a2mn ::;; a26n + a2m-6n = 2n + {(m-6)n/3} = {mn/3}. , , 3. THE 2-PACKING NUMBER OF A 3XMXN GRID. We present our findings for the 3xmxn case. Fisher [1] proved that a,,,,n = a3,,,n = {2n/3}. By Theorem 2, a2 3,n = a3 2,n = 2{n/2}. For 2 < m ::;; 8, our conjectures for a3,m,n are based on Fisher's program results. Conjectures for a3 3,n, a3,4,n and a3 7,n are proven as Theorems 10, 11, and 12, respectively. We also present some program results which support our conjectures for a3 5,n, a3 6,n, and a3 8,n, and we explain why these hypotheses are not proven. In our closing remarks for this chapter, we explain why a general formula for a3,m,nremains undetermined. Lemma 13. a3 3 = 5. Proof. Figure 9 shows that a3 3 3 ;::: 5. Suppose a3 3 3 = 6. Since by Theorem 2, a2 3 3 = a3 3 2 = 4, and since Fisher [1] showed that a1 3 3 = a3 3 1 = 2" Columns 1 11

PAGE 18

and 2 must have 4 checkers and Column 3 must have 2 checkers. Also, since by Theorem 1, a2 2 3 = a3 2 2 = 2, and by Theorem 2, a2 3 1 = a3 1 2 = 2, the only way up to symmetry to pack the first 2 columns with 4 checkers is as shown in Figure 9. However, 4 checkers in Columns 1 and 2 prohibits legal placement of 2 checkers in Column 3. 1 3 -2 3 1 -Figure 9: a3 3 3 = 5. Theorem 10. For all n>O, a3 3,n = {5n/3}. Proof. Figure 10 shows that for n > 0, a3 3 ,n {5n/3}. Fisher [1] showed that a1 3 3 = a3 3 1 = 2. By Theorem 2, a2 3 3 = a3 3 2 = 4. By Lemma 13, a3 3 3 = 5. By Lemma 1 and induction on n, a3 3,n ::; a3 3 3 + a3 3,n_3 = 5 + {5(n-3)/3} = {5n/3}. 13-13-13 2 2 31-31-31 Figure 10: Lower Bound Pattern for a3 3,n. Theorem 11. For n ({:. {1,3}, a34n = 2n. 12

PAGE 19

Proof. The pattern in Figure 11 shows that 2n is a lower bound for a3 4 By Theorem 2, a2 3 4 = a3 4 2 = 4. Fisher's program proves that a3 ,4,5 = 10. By Lemma 1 and induction on n, a3 4,. :::; a3 4 2 + a3 4 . 2 = 4 + 2(n-2) = 2n. -3 1 -2 -3 1 -2 1 --3 -1 --3 -3 --1 -3 --1 --1 3 -2 -1 3 -2 Figure 11: a3,4,n 2n. Our conjecture for the 2-packing number of a 3x5xn grid is as follows: a3 5,. = {(33n+6)/14} for n rf_ {1,3,16,19}. Fisher's program proves this result for 1 < n:::; 66. Figure 12 exhibits a 3x5x7 grid which is the only 3x5xn grid for 1:::; n:::; 66 which can be 2-packed with greater than { (33n + 6)/ 14} checkers. 1 -3 -1 -3 3 -1 -3 -1 -2 ---2 -1 -3 -1 -3 3 -1 -3 -1 Figure 12: a3 5 7 = 18. A 3x5x7 grid can be packed with 18 checkers. Although our computer-generated 3x5xn 2-packing patterns for 1 :::; n :::; 66 support that our a3,s,n conjecture is a lower bound for n 19, proving that a3,s,n :::; 13

PAGE 20

{(33n+6)/14} is problematic. Note that in all theorems proven in this paper, the upper bound arguments are straightforward. In all of these theorems k is determined such that a1 ,m,k agrees with the conjectured n-dependent 2-packing formula, and a1 ,n,k + a1 ,m,n-k is equivalent to this formula. Hence, induction on n and Lemma 1 are used to prove upper bounds for these cases. For the 3x5xn case, however, there appears to be no k such that a3 5 ,k = {(33k+6)/14} and a3.s,k + a3 ,s,n-k = {(33n+6)/14}. One interesting and typical example of a fully packed 3x5xn grid is presented in Figure 13 below. Note the 2 alternating 14-column patterns and that one of the two patterns is an inversion of the other. -2-1-31-31-2-13-13-2-31-31-3-2-1-31-31-Z-13-13-2-1 1-3-2--Z----3--Z--1----Z--2-1-3-2--2----3--2--1--3 3-l--13-l-31--1-3--31-3-13--3-1--13-1-31--l-3--31--2--3----2--2-3-1-2--2----1--2--3----z--z-3-l-2--2 1-31-Z-13-13-1-Z-3-13-13-2-31-31-2-13-13-l-Z-3-13-Figure 13: 2-Packing Pattern for a Maximally 2-Packed 3x5x50 Grid. Our conjecture for the 2-packing number of a 3x6xn grid is as follows: a3 6,n = {(14n+2)/5} for n (/'. {3,8}. For 1 n 66, Fisher's program proves this result and that no 2-packing number exceeds { (14n + 2)/5}. The reasons that this conjecture for a3 6 is difficult to prove are analogous to those given for the difficulty of proving the a3.s,n conJecture. We 14

PAGE 21

present an interesting 3x6xn 2-packing pattern in Figure 14 below. -31-31-31--31-31-31--31-31-31--31-31-31--31-31-3 ---Z--2--31--Z--Z--31--2--Z--31--2--2 -31--Z--21-3-13-1----3-13-1----3-13-l----3-13-l-Z--13-1 3-1----3-13-1----3-13-1----3-13-1---3-13-13---3 -2 --3 1 --2 --2 --3 1 --2 --2 --3 1 --2 --2 --3 1 -2 ---2 -1 -l-31--31-31-31--31-31-31--31-31-31--31-31 31-3-Z Figure 14: 2-Packing Pattern for a Maximally 2-Packed 3x6x48 Grid. Theorem 12. a3 ,7,n = {lOn/3} {lOn/3}+1 if n mod 3 E {0, 1} and n r:f_ {1,3}. ifnmod3=2. Proof. Figure 15 verifies that a3 ,7,n {lOn/3} ifn mod 3 E {0,1}, and that a370 {lOn/3}+1 ifn mod 3 = 2. For n mod 3 = 0, let n = 3k; for n mod 3 = 1, let n = 3k+ 1; for n mod 3 = 2, let n = 3k+2. By Theorem 2, a2 ,3 7 = a 3 7 ,2 = 8. By Theorem 11, a 3 ,4 7 = a 3 7,4 = 14. Fisher's program proves that a 3,1, 5 = 18, a 3 7 6 = 20, a 3 7 7 = 24, and that a 3 7 ,9 = 30. By Lemma 1 and induction on n, a 3 7 3 k ::::; a,,7,6 +a,,7,3k-6 = 20 + {10(3k-6)/3} = {lOn/3}; a,,7,3k+t ::::; a,,7,6 + a,,7,3k-5 = 20 + {10(3k-5)/3} = 10k+4 = {10(3k+ 1)/3} = {!On/3}; a,,7,3k+2 ::::; a3 ,7,, + a 3 7,3k-4 = 20 + {10(3k-4)/3} + 1 = 10k+8 = {10(3k+2)/3} + 1 = {10n/3} + 1. Fisher's program proves the following conjecture for the 2-packing number of a 3x8xn grid for 1 ::::; n ::::; 55: For n r:f_ {1,2,3,7,8}, { {lln/5} + 2 {lln/5} + 1 15 if n mod 15 E {6,9,12},. if n mod 15 r:f_ {6,9,12}.

PAGE 22

1 -3 1 -3 1 -3 1 -3 -2 --2 --2 --2 -3 -1 3 -1 3 -1 3 -1 --------1 -3 1 -3 1 -3 1 -3 -2 2 --2 --2 -3 -1 3 -1 3 -1 3 -1 Figure 15: Lower Bound Pattern for a 3x7xn Grid. Our a3 8 ,n conjecture remains unproven since its proof poses problems comparable to those we encountered in attempting to prove our a3,s,n and a3 6,n hypotheses. An interesting 2x8xn 2-packing pattern is presented in Figure 16 below, 13-1-2-31-2-31-2-31-31-31-31-31-31-Z-31-2-31-Z-3-13 --Z-3-l--3-l--3-1--2--2--2--Z--2--3-l--3-l--3-1-Z--31--1-3--l-3--l-3---13-13-13-13--Z--3--1-3--l-3--31 --3--Z-13-Z-13-Z--13-----------13--Z-13-2-13-2--1-1--13-----------13--2-13-2-13-2--13-----------13--3 3-2--13-13-13-13--Z--3--l-3--l-3---13-13-13-13--Z-1 -1--Z--Z--Z--2--Z--3-1--3-1--3-1--2--Z--2--2--2--32-31-31-31-31-31-31-2-31-2-31-Z-31-31-31-31-31-31-2 Figure 16: 2-Packing Pattern for a Maximally 2-Packed 3x8x51 Grid. No trend suggesting a general formula for a3,m,n emerges from the 3xmxn results above. Recall our hypothesis that for l ::?: 3 and sufficiently large m and n, a1,m,n = {lmn/7}. Hence, for the 3xmxn case we seek evidence that {3mn/7} is the greatest lower bound for all m,n sufficiently large. Consider Figure 16 below, which is a lower bound pattern for any 3xmxn grid. If j and k are positive integers, m = 4j-1, and n = 3k+2, we see that this grid pattern is packed with 5jk+4j 16

PAGE 23

checkers. Then j = (m+ 1)/4, k = (n-2)/3, and 5jk+4j = (m+ 1)(5k+2)/12. If m = n = 47, then (m+1)(5n+2)/12 = 948 > {3mn/7} = 947. Hence, ifa3mn = {3mn/7} for some m,n ;;:: n0 then n0 must be greater than 47. Our method for determining a3 ,m,n would require close scrutiny of computer-generated 2-packing patterns for grids larger than 3x47x47. The prohibitively long cpu time required to run Fisher's program on a high speed computer for grids this large prevents us from determining a3,m,n completely. 1 3 -1 3 -1 3 -1 3 2 --2 2 3 1 -3 1 -3 1 -3 1 --------1 3 -1 3 -1 3 -1 3 --2 -2 -2 3 1 -3 1 -3 1 -3 1 --------1 3 -1 3 -1 3 -1 3 2 --2 2 --Figure 17: 2-Packing Pattern for a 3xmxn Grid 4. THE 2-PACKING NUMBER OF A 4XMXN GRID. We present our findings for the 2-packing numbers of 4xmxn grids. Fisher [1] proved that a1 4,n = a..l,n = {6n/7} if n mod 7 ;<; 1 and a., 1,n = {6n/7} + I if n mod? = 1. By Theorem 3, a2 4,n = a4 2,n = {4n/3). By Theorem 11, a3 4,n = a.,3,n = 2n for n if:. {1,3}. We determine a. n (see Theorem 13), and present 17

PAGE 24

conjectures without proof for and By analogy to our unproven a3 5,n, a3 6,., and a3,s,n conjectures, our method of proof is unduly complicated for our and hypotheses. The cpu time constraints for running Fisher's program prevent us from collecting sufficient data for the analysis which our method of determining 2-packing numbers requires. For this reason, a general formula for a. m" remains undetermined. Theorem 13. For n (/::, {1,2,4,5,6,8,10,12}, = {5n/2}. Proof. The pattern in Figure 18 below verifies that 4 ::?: {5n/2} for n E {3,7,9,11} and n ::?: 13. By Theorem 11, a3 4 4 = = 8. Fisher's program proves the result for n E {7,11,13,15,16,18,19,20,22,24,26}. By Lemma 1 and induction on n, :o; + a4 4,n_14 = 35 + {5(n-14)/2} = {5n/2}. Our conjecture for the 2-packing number of a 4x5xn grid is as follows: For n (/::, {2,3,5,6,10}, = 3n+2. 3 1 4 1 4 2 3 1 4 1 4 2 3 2 3 41 2 3 41 2 41 3 2 41 3 2 4 1 3 2 4 1 4 1 3 2 4 1 3 Figure 18: Lower Bound Pattern for a 4x4xn Grid. 18

PAGE 25

Fisher's program proves this conjecture for 1 :5 n :5 66. An interesting example of a 4x5xn 2-packing pattern is given in Figure 19 below: 2 4 1 4 1 4 2 14 3 1 4 1 4 1 4 2 14 3 1 14 2 3 1 3 2 4 2 2 3 1 3 2 4 2 3 1 4 1 4 4 1 4 1 1 4 1 4 4 1 4 1 -2 -2 3 1 3 2 2 4 2 3 1 3 2 2 4 4 1 3 1 14 2 4 1 4 1 4 1 3 14 2 4 1 4 1 4 1 Figure 19: 2-Packing Pattern for a Maximally 2-Packed 4x5x32 Grid. Our conjecture for a. .. is as follows: For n (/; {16,25}, ll.,,6,n = { { 46n/13} + 2 {46nl13}+ 1 if n mod 13 (/; {4,6}, if n mod 13 E {4,6}. Fisher's program proves this conjecture for 1 :5 n :5 44. An example of a maximally 2-packed 4x6xn grid is given in Figure 20 below. 2 4 1 4 2 3 1 3 14 2 4 1 3 1 3 14 2 4 1 14 3 1 4 1 4 2 3 1 3 4 1 4 2 3 3 3 1 4 3 3 1 4 1 4 2 3 1 4 1 4 2 2 4 1 -2 4 1 -3 2 4 1 4 1 3 2 14 4 2 3 14 2 4 1 4 1 3 2 4 1 4 1 3 1 3 14 2 3 1 4 1 3 2 4 2 14 3 1 3 2 4 2 Figure 20: 2-Packing Pattern for a Maximally 2-Packed 4x6x30 Grid. 4 1 1 4 2 3 As explained in the opening remarks for this chapter, the limitations of our means for gathering the data on which our 2-packing number determination depends 19

PAGE 26

prevent us from finding a general formula for l4,m,nIn particular, we are unable to acquire additional data which might support our conjecture that for l ;?; 3 and sufficiently large m and n, = { lmn/7}. At present, we lack evidence that a4 m" = {4mn/7}. 20

PAGE 27

BIBLIOGRAPHY 1. Fisher, D.C., "The 2-Packing Number of Complete Grid Graphs", to appear in Ars Combinatoria. 2. Fisher, D.C. and Kellner, B., "The 3-Packing Number of Complete Grid Graphs", to appear in Ars Combinatoria. 3. E. 0. Hare and W .R. Hare, "kPacking of P m x P n", Congressus Numerantium, 84 (1991) 33-39. 21