282 16. Answers to Exercises
and so the number of non-S-triples isb−b′=(v+1)( 8 v−1). Every non-S-
triple has at most one point inSand thus at least two points not inS.
But the number of pairs not isSis
((v+1)/ 2
2)
=(v+1)( 8 v−1), and since these
pairs can belong to one of the non-S-triples only, it follows that each of
the non-S-triples must contain exactly one pair of elements outsideS. This
proves that each non-S-triple must contain an element ofS.
14.4.4. See Figure 16.5.
FIGURE 16.5.14.4.5. Every girl has 8 other girls to walk with; every day she can walk
with 2 in a line. So 4 days are necessary for her to walk with everybody
exactly once.
14.5 Latin Squares
14.5.1. There are 576 different 4×4 Latin squares. There are many ways
to arrive at this figure; we sketch one. The first row can be filled out 4!
ways. These are all equivalent in the sense that the number of ways they
can be completed is the same for each of them, so we may fix the first
row as 0 1 2 3 and just count the number of ways to complete this. The
first column now can be filled out in 3! ways, and again all of these are
equivalent, so let’s fix it as 0 1 2 3.
If the 0 in the second row is in the second position, then the rest of the
second row and second column is forced, but we get two ways to fill out
the 4 fields in the lower right corner. If the 0 in the second row is in the
third or fourth position, then the way to fill out the rest is forced. Thus we
get the 4 Latin squares below:
0123 0123 0123 0123
1032 1032 1230 1302
2301 2310 2301 2031
3210 3201 3012 3210Therefore, the number of ways to fill out the remaining 9 fields is 4, so the
total number is 4!·3!·4 = 576.