Newsgroups: sci.math From: sung@math.snu.ac.kr (PooSung Park) Subject: Q: Is this possible? Date: Wed, 12 Apr 95 05:17:16 GMT Let S be a set of 15 elements. Is there a set A satisfing the following conditions? (1) Every element of A is a set of exactly three elements of S. (2) Any two elements of A have at most one element in common. (3) Every element of S is contained in exactly three elements of A. ============================================================================== From: Douglas Zare Newsgroups: sci.math Subject: Re: Q: Is this possible? Date: 17 Apr 1995 11:18:46 GMT sung@math.snu.ac.kr (PooSung Park) wrote: > > Let S be a set of 15 elements. > Is there a set A satisfing the following conditions? > (1) Every element of A is a set of exactly three elements of S. > (2) Any two elements of A have at most one element in common. > (3) Every element of S is contained in exactly three elements of A. Note that the dual of this structure also has these properties. Actually, one can ask for much more structure. Kirkman's Schoolgirls Problem is as follows: 15 schoolgirls walk to lunch each day in 5 rows of 3. Construct a schedule such that no two girls walk together in the same row more than once each week. This is related to the question of the existence of resolvable block designs. I will not post them, but solutions to the above problem exist (one can take projective 3-space over Z/2 as the design). The rows of any three days form a set A of the type specified above. Douglas Zare zare@cco.caltech.edu ============================================================================== From: "Timothy Chow" Date: Mon, 17 Feb 1997 15:00:38 -0500 (EST) To: rusin@math.niu.edu Subject: Kirkman [From Heinrich Dorrie's _100_Great_Problems_of_Elementary_Mathematics_] Let one girl, whom we will indicate as *, walk in the middle of the same row on all days; we will divide the other girls into two groups of seven and designate the first group by the Arabic numbers 1 to 7 or else by lower-case letters and the second group by the Roman numbers I to VII or else by capital letters. We will let an equation such as R = s indicate that the Roman number indicated by the letter R possesses the same numerical value as the Arabic numeral corresponding to the letter s. Also, we will deisnate the days of the week Sunday, Monday, ..., Saturday by the numerals 0, 1, 2, ..., 6. Let the Sunday arrangement have the following order: a e A b f B c g C d * D E F G From this, by adding r = R to each numeral, we obtain the arrangement a + r e + r A + R b + r f + r B + R c + r g + r C + R d + r * D + R E + R F + R G + R for the rth weekday, where we reduce these numbers modulo 7 if necessary. The arrangements thus obtained yield the solution of the problem if the following three conditions are satisfied: I. The three differences e - a, f - b, g - c are 1, 2 and 3. II. The seven differences A - a, A - e, B - b, B - f, C - c, C - g, D - d are all distinct modulo 7. III. The three differences F - E, G - F, G - E are 1, 2, 3. Proof. 1. Each girl x of the first group will come together exactly once with every other girl y of this group. The difference x - y is then (according to I.) congruent mod 7 to only one of the six differences a - e, b - f, c - g, e - a, f - b, g - c. Let us assume x - y = f - b (mod 7) or x - f = y - b (mod 7). Thus, if r represents the number of the day of the week that is congruent to x - f (or y - b) mod 7, then x = f + r (mod 7) and y = b + r (mod 7), so that the girls x and y walk in the same row on weekday r. 2. Each girl x of the first group comes together exactly once with each girl X of the second group. The difference X - x (according to II.) can be congruent mod 7 to only one of the seven differences A - a, A - e, B - b, B - e, C - c, C - g, D - d. Let us assume X - x = C - g (mod 7) or X - C = x - g (mod 7). If s = S is the weekday number that is congruent to X - C (or x - g) mod 7, then we have X = C + S (mod 7) and x = g + s (mod 7), so that the girls X and x walk in the same row on weekday s. 3. Each girl X of the second group comes together exactly once with every other girl Y of this group. The difference X - Y is (according to III.) congruent mod 7 to only one of the differences F - E, G - F, G - E, E - F, F - G, E - G. Let us assume that X - Y = G - F (mod 7) or X - G = Y - F (mod 7). Then if R represents the weekday number that is congruent to X - G (or Y - F), we obtain X = G + R (mod 7) and Y = F + R (mod 7) so that the girls X and Y walk in the same row on weekday R. Thus, we need only satisfy conditions I. II., and III. to obtain the Sunday arrangement. We choose a = 1, e = 2, b = 3, consequently f = 5, and then c = 4, so that g = 7 and d = 6. We then select A = 1, and thus B = VI, C = II and D = III, so that the differences mentioned in condition II. are the numbers 0, -1, 3, 1, -2, -5, which are incongruent mod 7. The numbers IV, V and VII then remain for the letters E, F, and G. The Sunday arrangement is therefore 1 2 I 3 5 VI 4 7 II 6 * III IV V VII The weekday rows, in order, are arranged in the following manner: 2 3 II 3 4 III 4 5 IV 4 6 VII 5 7 I 6 1 II 5 1 III 6 2 IV 7 3 V 7 * IV 1 * V 2 * VI V VI I VI VII II VII I III 5 6 V 6 7 VI 7 1 VII 7 2 III 1 3 IV 2 4 V 1 4 VI 2 5 VII 3 6 I 3 * VII 4 * I 5 * II I II IV II III V III IV VI