Discrete Mathematics Final Presentation
311706017 陳詩婷
Latin Squares
Finite Geometries and Affine Planes
17.4
Block Designs and Projective Planes
17.5
17.3
Outline
17.3�Latin Squares
Definition 17.9
Example 17.13
A research team designs an experiment wherein four erent automobiles, denoted A, B, C, and D, are run on a fixed track in a laboratory ses the same prescribed amount of fuel with one of the additives present.
Tables 17.3
Tables 17.4
Table 17.3, where the additives are numbered 1, 2, 3, and 4. This schedule provides a way to test each additive thoroughly in each type of auto. If one additive produces the best results in all four types, the experiment will reveal its superior capability.
A similar schedule for these tests is shown in Table 17.4, where these engine-cleaning additives are also denoted as 1, 2. 3, and 4.
Example 17.13 (cont’d)
Tables 17.5
On Tuesday, auto C is used to test the combined effect of the 4th additive for improved mileage and the 3rd additive for maintaining a clean engine.
Example 17.14
Tables 17.3
Tables 17.4
Definition 17.10
Example 17.15
and
and
Definition 17.11
If L is an 𝑛 × 𝑛 Latin square, then L is said to be in standard form if its first row is 1 2 3 4 … 𝑛 .
Example:
Example 17.16
If a Latin square is not in standard form, it can be put in that form by interchanging some of the symbols.
4 2 3 5 1
1 3 5 4 2
3 4 2 1 5
2 5 1 3 4
5 1 4 2 3
1 2 3 4 5
5 3 4 1 2
3 1 2 5 4
2 4 5 3 1
4 5 1 2 3
each 4 with 1
each 5 with 4
each 1 with 5
Replace
standard form
not standard form
Theorem 17.14
Theorem 17.15
Theorem 17.16
17.4�Finite Geometries and Affine Planes
Definition 17.12
Let 𝒫 be a finite set of points, and let ℒ be a set of subsets of 𝒫, called lines. A (finite) affine plane on the sets 𝒫 and ℒ is a finite structure satisfying the following conditions.
A1) Two distinct points of 𝒫 are (simultaneously) in only one element of ℒ ; that is, they are on only one line.
Definition 17.12
A2) For each ℓ ∈ ℒ , and each 𝑃 ∈ 𝒫 with 𝑃 ∉ ℓ, there exists a unique element ℓ′ ∈ ℒ where 𝑃 ∈ ℓ′ and ℓ , ℓ′ have no point in common.
A3) There are four points in 𝒫, no three of which are collinear (that is, no three of these four points are in any one of the subsets ℓ ∈ ℒ ).
lines
Infinite slope
(vertical lines)
Finite slope
(not vertical lines)
𝑥 = a
𝑦 = 𝑚𝑥 + b
𝑛 vertical lines
𝑛 2 lines that are not vertical
Theorem 17.17
If F is a finite field, then the system based on the set 𝒫 of points and the set ℒ of lines. As described above, is an affine plane denoted by AP(F).
Example 17.18
Theorem 17.18
17.5�Block Designs and Projective Planes
Example 17.20
Dick (d) and his wife Mary (m) go to New York City with their five children — Richard (r), Peter (p), Christopher (c), Brian (b), and Julie (j). While staying in the city they receive three passes each day, for a week, to visit the Empire State Building. Can we make up a schedule for this family so that everyone gets to visit this attraction the same number of times? The following schedule is one possibility.
1) b, c, d 2) b, j, r 3) b, m, p 4) c, j, m
5) c, p, r 6) d, j, p 7) d, m, r
Definition 17.13
Example 17.21
V, then 𝜆 represents that common measure and design is called balanced. In this text we only deal with balanced designs.
Theorem 17.19
Theorem 17.19
Definition 17.14
If 𝒫′ is a finite set of points and ℒ ′ a set of lines, each of which is a nonempty subset of 𝒫′ , then the (finite) plane based on 𝒫′ and ℒ ′ is called a projective plane if the following conditions are satisfied.
Pl) Two distinct points of 𝒫′ are on only one line.
P2) Any two lines from 𝒫′ intersect in a unique point.
P3) There are four points in 𝒫′ , no three of which are collinear.
Example 17.22
Example 17.22
The six line in ℒ were originally
We rewrite these as
And add a new line ℓ∞ defined by 𝑧 = 0:{ 1, 0, 0, 0, 1, 0, (1, 1, 0)}
Example 17.22
Thank you