From: mathwft@math.canterbury.ac.nz (Bill Taylor) Newsgroups: sci.math,rec.puzzles Subject: Committee membership = Projective geometry. was: Russian 67 Date: 28 Oct 1998 06:46:58 GMT Kurt Foster writes: |> . (a) A committee has met 40 times, with 10 members at every meeting. No |> . two people have met more than once at committee meetings. Prove that |> . there are more than 60 people on the committee. |> we look at the number of pairs involved on both sides. |> In a set of m objects there are (m*(m-1))/(1*2) pairs. If no two sets in |> a collection of sets have more than one element in common, then no pair |> occurs in more than one set in the collection. This is a not bad upper bound. In general, for a pool of people of size N and collections of size C, it gives the number of possible collections, X, to be bounded by X <= N(N-1)/C(C-1) For the two problems originally given, this is good enough. However, it is not always a sharp bound. A simple counterexample would be N = 6, C = 4. Clearly you cannot get two 4-collections out of {a,b,c,d,e,f} without a doubled-up pair somewhere. But [6.5/4.3] = 2. So the bound [N(N-1)/(C(C-1)] is not sharp. However, this one may be:- X <= [[(N-1)/(C-1)].N/C] This odd "separated iteration" of the integer-part operation comes about as follows. Consider person number 1. He can meet with (N-1) people at most once each; and he can only do this at most (C-1) at a time, in the various collections he's in. So he can be in at most [(N-1)/(C-1)] collections, before he runs out of partners. So he can fulfill at most [(N-1)/(C-1)] collection-appearances. But all people are similar, so they can, in toto, fulfill at most N.[(N-1)/(C-1)] appearances. But there are X.C appearances to fulfill, so thus X <= [(N-1)/(C-1)].N/C] . ======================= Ta-dah! As far as I've checked, this upper bound seems to be sharp, but I can find neither a proof nor counter-example. CAN ANYONE ELSE!?? =============== This whole committee business is just a disguised form of 2-dimensional projective geometry, as one might expect from a purely "incidental" problem. The people can be the points, and the collections the lines. (Interestingly, one could get up a 3-dimensional example by having the pool of people fall into various categories, (planes), e.g. by race or civil service grade. That would be getting into heavy puzzle territory!) So it is not surprising to find that the most efficient "best fits" among committee examples come from those where they are based on a standard finite 2-D projective geometry, based on integer points [modulo p] for some prime p. For instance this example... |> . (b) Prove that you cannot make more than 30 subcommittees of 5 members |> . from a committee of 25 members with no two subcommittees having more |> . than one common member. ...is based on the standard F2DPG [mod 5]; where one takes the people(points) as being the integer points (0,0), (0,1),... ... ..., (4,4), and has lines:- 5 vertical lines of 5 points each; 5 horizontal lines of ditto; 5 NE-SW diagonal lines ditto; 5 NW-SE diagonal lines ditto; 5 NNE-SSW knight-lines ditto; 5 NNW-SSE knight-lines ditto. A total of 30 lines, just managed! Clearly (?) the lines all intersect at most once. Note that for the diagonal and knight's-move-slope lines, when one "goes off" the array, one comes on again on the other side due to the mod-5-ness. In effect, we are looking at the whole infinite array of integer points, and identifying mod-5-aparts either horizontally or vertically (or both). This makes it easier to follow, perhaps, if you are sketching a pic. Note also, (sketch your pic to verify), that the NEE knight-line is the SAME LINE as the NNW one, so one doesn't get two further knight slopes, as originally it might seem. Indeed, sketching out these slopes in a p x p array of points, for various primes p, is great fun, and gives some insight into why such 2DPG's only hold for *prime* p. It's fascinating to see how each new prime is JUST ENOUGH bigger than the previous one to get JUST ENOUGH new directions. *Miraculous*! :) I earnestly enjoin you to sketch a few of these, for p = 2,3,5,7,11,13, say. Experts will note that we have also not used the POINTS (and line) AT INFINITY. Bringing these in, allows one e.g. in the above example to now make up 31 (!) collections of 6 (!) members each, with the modest outlay of a mere 6 extra people. Now *there's* efficiency. Too efficient to be Russian, obviously... ;-) ------------------------------------------------------------------------------- Bill Taylor W.Taylor@math.canterbury.ac.nz ------------------------------------------------------------------------------- Newton: You cannot touch without being touched. Heisenberg: You cannot be touched without touching. ------------------------------------------------------------------------------- ============================================================================== From: John Rickard Newsgroups: sci.math,rec.puzzles Subject: Re: Committee membership = Projective geometry. was: Russian 67 Date: 28 Oct 1998 13:38:48 +0000 (GMT) In rec.puzzles Bill Taylor wrote: : In general, for a pool of people of size N and collections of size C, : it gives the number of possible collections, X, to be bounded by : : X <= N(N-1)/C(C-1) (Where no two collections can have more than one person in common.) : X <= [[(N-1)/(C-1)].N/C] [Proof snipped.] : As far as I've checked, this upper bound seems to be sharp, but I can : find neither a proof nor counter-example. CAN ANYONE ELSE!?? Yes; it's known that there is no projective plane of order 6, so for N = 6^2 + 6 + 1 = 43 and C = 6 + 1 = 7, X must be strictly less than 43 (and your bound is only X <= 43). As you remark ... : This whole committee business is just a disguised form of 2-dimensional : projective geometry, as one might expect from a purely "incidental" : problem. The people can be the points, and the collections the lines. (But indeed, isn't N=5, C=3 a counterexample? Your bound works out as 3, but there don't exist three 3-element subsets of a 5-element set with no two sets having more than one common element.) -- John Rickard ============================================================================== Date: Sun, 14 Feb 1999 14:27:23 -0800 To: rusin@math.niu.edu From: Greig Subject: Committee membership = Projective geometry, was: Russian 67 Dear Dave, Re: 98/projplane Given v committe members, meeting k at a time, with any pair (or t-tuple, with t=2) occuring at most one time the maximum number of meetings possible is D(v,k,t). Determining D(v,k,t) is known as the packing problem (here the pair packing problem). In coding theory, one wants to determine the maximum number of binary codewords of constant weight, w, and dimension v, with any two codewords differing in at least d places, (i.e., having a Hamming distance of d or more). This number is denoted by A(v,d,w). We have D(v,k,t)=A(v,2k-2t,k). Values or bounds, for A(v,d,w) with small parameters can be found at http://www.research.att.com/~njas/codes/Andw/ Clearly D(v-1,k-1,1) = \lfloor{(v-1)/(k-1)}\rfloor = U(v-1,k-1,1) and D(v,k,t) <= \lfloor{vD(v-1,k-1,t-1)/(k-1)}\rfloor which is shown by considering what happens for one fixed committee member. The bound, U, obtained by iterating U(v,k,t) = \lfloor{vU(v-1,k-1,t-1)/(k-1)}\rfloor is known as the Schonheim bound. It is known not to be tight, in general. Specifically, for pairs (t=2), it is known that: if v-1 \equiv 0 mod (k-1) and v(v-1) \equiv -1 mod (k), then D(v,k,2) <= U(v,k,2)-1. (**) For fixed k and t=2, it is believed this bounds are tight asymptotically (in v) However, for small v, they are not too good. Considering the members not siiting at any meeting, we have D(v,k,t) = D(v,v-k,v-2k+t) which gives (especially for v < 2k-1) that D(v,k,t) <= \lfloor{vD(v-1,k,t)/(v-k)}\rfloor Also, for v < kk/(t-1), with vq = kd-r and 0 <= r < v, conting pairs containing the member m, then summing over m, gives vq(q-1) <= (t-1)d(d-1)-2qr which implies the more convenient (but sometimes weaker) form D(v,k,t) <= \lfloor{ (k+1-t)v/(kk-v(t-1)) }\rfloor. Finally, what does asymptotically mean. Actually, not too much is known. What is known is for k=3, t=2, then (**) is tight for v\equiv 5 mod(6), and the Schonheim bound is met otherwise, For k=4, t=2; the Schonheim bound is met if v > 19. For k=4, t=3 and v \not\equiv 5 mod (6), then D(v,4,3) = \lfloor{vD(v-1,3,2)/4}\rfloor. The D(v,4,3) value for v \equiv 5 mod (6) is open for v > 11. The case of D(v,5,2) is currently (1999) being studied; the Schonheim bound is tight for v \equiv 1,3,5 mod (20), and (**) is tight for v \equiv 9,17 mod (20) for v>49. So far as I know, no one has tried any asymptotics for fixed k > 5. Returning to the original problem, taking v=63, and using the Schonheim bound, gives D(63,10,2) <=36, so v>63. QED Two survey articles are: W.H.Mills and R.C.Mullin, Coverings and Packings, in: Contemporary Design Theory (eds. J.H.Dinitz & D.R.Stinson) J.Wiley, NY (1992) pp 371--399. D.R.Stinson, Packings, in: The CRC Handook of Combinatorial Designs (eds. C.J.Colbourn & J.H.Dinitz) CRC Press, Boca Raton FL (1996) pp 409--413 /********************************************************************/