
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00001681/00001
Material Information
 Title:
 The 2packing number of 3D complete grid graphs
 Creator:
 Beel, Sarah R
 Publication Date:
 1993
 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, CU Denver
 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 ) nonfiction ( 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 2PACKING NUMBER
OF 3D 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 2Packing Number of 3D Complete Grid Graphs
Thesis directed by Associate Professor David C. Fisher
ABSTRACT
The 2packing 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 2packing number of a 2xraxn grid for all m and
n. We also find the 2packing 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 2PACKING HUMBER OF A 2xmxn GRID.........3
3. THE 2PACKING NUMBER OF A 3xmxn GRID.......11
4. THE 2PACKING NUMBER OF A 4xmxn GRID .......17
BIBLIOGRAPHY .,.
21
vi
1.INTRODUCTION.
In a 2packing 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 2packing number
az,m,n f an /xmxn grid is the maximum number of checkers in a 2packing.
Fisher [1]and Fisher and Kellner [2] solve similar problems in 2
dimensional grids. Fisher [1]found the 2packing number of Ixmxn grids (i.e., 2
dimensional grids) for all m and n. We find the 2packing number of 2xmxn grids
for all m and n. We also find the 2packing numbers for 3x3xn, 3x4xn, 3x7xn, and
4x4xn grids. General formulas for 2pacMng 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 2packings
of 3D 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 2D 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 3D 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 3D 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 2D
representation.
Figure 1:2D Representations of 2Packings of a 3D Grid.
Hare and Hare [3] developed an efricient algorithm for finding n. Fisher
[1]showed that the 2packing 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, 2packing results for I = 2,3* and 4 are presented. Our
conjectures for amn are based on 2paddng number output from a program by
Fisher. A modification of the same program generates 2packing 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 2packing of an Ixmxn grid has at most checkers in the
first nj 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 2PACKING NUMBER OF A 2XMXN GRID.
For the 2xmxn case, Theorems 1B lead to the following results:
Lemma 2. For all m > 0 and n > 0, a2in tl > {mn/3}.
Proof. Any 2packing 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 2Packings* Since there are
Imn cubes in a grid, at least one of the seven 2packings has at least {/mn/7}
checkers.
0
f15
0 sd
dffof
c/hea
^ead'c
c
0
ado
ocfh
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
fheada
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 2packings. Since there are 2mn cubes in the grid, at least
Figure 3: Partitioning of a 2xmxn Grid into Six 2Packings. 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 2pacMng prohibits legal placement of a third
checker.
1
2
Figure 4: a2A2 = 2. Up to symmetry, there is only one way to 2pack a 2x2x2
grid.
Lemma 4. a2,2 3 = 2.
one of the six 2packings 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
2packed 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 2pack 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 n3,
Then by Lemma 1 and induction on na2An S a2A3 + a2An4 = 2 + {2(n3)/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{(n2)/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 2packed 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
______ _________________________
12 21
Figure 8: 2 Checkers in Each of the 3 Columns of a 2x5x3 Grid Is Illegal. If
the grid is to be 2packed 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 n6 ^ 1,and n6 ^ 3, a2)5f ^ a2>^6 + a2i5>n_6
=10 + {5(n6)/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 + a23 = 6 + 2(n3) = 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,n4 =14 + {7(n6)/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(n3)/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 m6. By Lemma 1 and
induetion on m, %^%6n + %mi4n = *2n += {rrm/3h
3. THE 2PACKMG 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(n3)/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(n2) = 2n.
1 i t t
Figure 11:a3>4lt Ss 2n.
Our conjecture for the 2packing 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 computergenerated 3x5xn 2oacMng 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 ndependent 2packing 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 14column patterns and that
one of the two patterns is an inversion of the other.
213131213132313132131312131321
3113131133131331131311331
X3121313123131323131Z13131Z313
Figure 13: 2Packing Pattern for a Maximally 2Packed 3x5x50 Grid.
Our conjecture for the 2packing 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 2paddng 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 2pacMng pattern in Figure 14 below.
Figure 14: 2Packing Pattern for a Maximally 2Packed 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, =a3j72 = 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,3k6 = 20 + (10(3k6)/3} = {10n/3}; a3j7;3k+t ^ %,7,6 + a3,7,3k5 = 20 +
{10(3k5)/3}=10k+4 = {10(3k+l)/3} = {10n/3}; a3,7,3k+2 < a3>7>6 + a3,?(3M =
20 + {10(3k4)/3} + 1=10k+8 = {10(3k+2)/3} + 1={10n/3} + 1.
Fisher5s program proves the following conjecture for the 2pacMng 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 2packing pattern is presented in Figure 16 below.
13123123123131313131312312312313
3l~2'~222*23l__
~~1
32I31313i3~23l3l31313131321
2~313131~313l312312312313131313i3l2
Figure 16: 2Packing Pattern for a Maximally 2Packed 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 = 4J1, and n = 3k+2, we see that this grid pattern is packed with 5jk+4j
16
checkers. Then j = (m+l)/4, k = (n2)/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 computergenerated 2packing
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: 2Packing Pattern for a 3xmxn Grid
4. THE 2PACKING NUMBER OF A 4XMXN GRID.
We present our findings for the 2packing 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(n14)/2} = {5n/2}.
Our conjecture for the 2packing 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 2packing 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; 2Packing Pattern for a Maximally 2Packed 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 2packed 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: 2Packing Pattern for a Maximally 2Packed 4x6x30 Grid.
As explained in the opening remarks for this chapter, the limitations of our
means for gathering the data on which our 2packing 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 2Packing Number of Complete Grid Graphs", to appear
in Ars Combinatoria.
Fisher, D.C, and Kellner, B., "The 3Packing Number of Complete Grid
Graphs", to appear in Ars Combinatoria.
E.O. Hare and W.R. Hare, "kPacMng of P, x Pn", Congressus
Numerantium, 84 (1991) 3339.

Full Text 
PAGE 1
THE 2PACKING NUMBER OF 3D 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 2Packing Number of 3D Complete Grid Graphs Thesis directed by Associate Professor David C. Fisher ABSTRACT The 2packing 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 2packing number of a 2xmxn grid for all m and n. We also find the 2packing 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 2PACKING NUMBER OF A 2xmxn GRID ........ 3 THE 2PACKING NUMBER OF A 3xmxn GRID . . . 11 4. THE 2PACKING NUMBER OF A 4xmxn GRID . . . 17 BIBLIOGRAPHY .................................... 21 vi
PAGE 7
1. INTRODUCTION. In a 2packing 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 2packing number a1mn of an lxmxn grid is the maximum number of checkers in a 2packing. Fisher [1] and Fisher and Kellner [2] solve similar problems in 2dimensional grids. Fisher [1] found the 2packing number of lxmxn grids (i.e., 2dimensional grids) for all m and n. We find the 2packing number of 2xmxn grids for all m and n. We also find the 2packing numbers for 3x3xn, 3x4xn, 3x7xn, and 4x4xn grids. General formulas for 2packing 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 2packings of 3D 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 2D 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 3D 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 3D 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 2D representation. Figure 1: 2D Representations of 2Packings of a 3D Grid. Hare and Hare [3] developed an efficient algorithm for finding a,,n Fisher [1] showed that the 2packing 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, 2packing results for l = 2,3, and 4 are presented. Our conjectures for a1,m,n are based on 2packing number output from a program by Fisher. A modification of the same program generates 2packing 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 2packing 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 2Packings. Since there are lmn cubes in a grid, at least one of the seven 2packings has at least {lmn/7} checkers. 4
PAGE 11
a 2xmxn grid into six 2packings. Since there are 2mn cubes in the grid, at least one of the six 2packings 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 2Packings. 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 2packed with 2 checkers. This 2packing prohibits legal placement of a third checker. 1 2 Figure 4: a2 2 2 = 2. Up to symmetry, there is only one way to 2pack 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 2packed 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 2pack 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 n3. Then by Lemma 1 and induction on n, a2 ,2,n a 2 2 ,3 + a 2 2,n.3 = 2 + {2(n3)/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,n2 = a2 ,2 ,3 + a 2 ,3,n.2 = 2 + 2{(n2)/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,nJ = 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 2packed 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 2packed 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 n6 ;e 1, and n6 ;C 3, a2,s,n a2 5 6 + a2 5 . 6 = 10 + {5(n6)/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(n3) = 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(n6)/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(n3)/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 m6. By Lemma 1 and induction on m, a2mn ::;; a26n + a2m6n = 2n + {(m6)n/3} = {mn/3}. , , 3. THE 2PACKING 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(n3)/3} = {5n/3}. 131313 2 2 313131 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(n2) = 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 2packing 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 2packed 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 computergenerated 3x5xn 2packing 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 ndependent 2packing formula, and a1 ,n,k + a1 ,m,nk 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,nk = {(33n+6)/14}. One interesting and typical example of a fully packed 3x5xn grid is presented in Figure 13 below. Note the 2 alternating 14column patterns and that one of the two patterns is an inversion of the other. 21313121313231313213131Z131321 132Z3Z1Z213223213 3l13l3113313133113131l33123223122123zz3l22 131Z13131Z313132313121313lZ313Figure 13: 2Packing Pattern for a Maximally 2Packed 3x5x50 Grid. Our conjecture for the 2packing 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 2packing 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 2packing pattern in Figure 14 below. 31313131313131313131313131313 Z231ZZ312Z3122 31Z2131313131313l313lZ131 31313131313131313133 2 3 1 2 2 3 1 2 2 3 1 2 2 3 1 2 2 1 l313131313131313131313131 313Z Figure 14: 2Packing Pattern for a Maximally 2Packed 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,3k6 = 20 + {10(3k6)/3} = {lOn/3}; a,,7,3k+t ::::; a,,7,6 + a,,7,3k5 = 20 + {10(3k5)/3} = 10k+4 = {10(3k+ 1)/3} = {!On/3}; a,,7,3k+2 ::::; a3 ,7,, + a 3 7,3k4 = 20 + {10(3k4)/3} + 1 = 10k+8 = {10(3k+2)/3} + 1 = {10n/3} + 1. Fisher's program proves the following conjecture for the 2packing 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 2packing pattern is presented in Figure 16 below, 1312312312313131313131Z31231Z313 Z3l3l31222Z23l3l31Z3113l3l313131313Z313l331 3Z13Z13Z1313Z132132111313213213213133 3213131313Z3l3l313131313Z1 1ZZZ2Z3131312Z22232313131313131231231Z3131313131312 Figure 16: 2Packing Pattern for a Maximally 2Packed 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 = 4j1, 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 = (n2)/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 computergenerated 2packing 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: 2Packing Pattern for a 3xmxn Grid 4. THE 2PACKING NUMBER OF A 4XMXN GRID. We present our findings for the 2packing 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 2packing 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(n14)/2} = {5n/2}. Our conjecture for the 2packing 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 2packing 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: 2Packing Pattern for a Maximally 2Packed 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 2packed 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: 2Packing Pattern for a Maximally 2Packed 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 2packing 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 2Packing Number of Complete Grid Graphs", to appear in Ars Combinatoria. 2. Fisher, D.C. and Kellner, B., "The 3Packing 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) 3339. 21

