From: mareg@mimosa.csv.warwick.ac.uk () Subject: Re: message passing Date: 4 Oct 2000 09:07:44 GMT Newsgroups: sci.math Summary: [missing] In article <8rcte901ivg@drn.newsguy.com>, pragma@A0L.C0M writes: > > >Player A has a deck of 190 cards numbered 1 to 190. > >He shuffles the deck and deals 5 cards to Player B. > >Player B selects 4 of the 5 cards and gives them to Player C. > >Is there any algorithm that Player B can use to select the 4 cards, >regardless of the 5 cards he is dealt, that will enable him to >communicate a message to Player C (even if it's just one bit of >information)? > >For example, if I added the constraint that Player B gets to >throw away his 5-card hand and ask to be dealt another in the >event that the hand does not contain at least one odd number and >one even number, then Player B could always communicate a >message to Player C by selecting 4 cards that summed to either an >even number or an odd number. But if this constraint is removed, >is there some other way to communicate a message? Do you mind telling us where this problem comes from? Why 190? Is it an exercise in a book or from a combinatorics course? I haven't solved it yet, but it seems to be equivalent to a combinatorial problem that might be well-known! Let 0 < r < n and take a set S of size n. Can we colour the size r-subsets of S red and green, in such a way that for any subset T of S of size r+1, the size r-subsets of T do not all have the same colour? Your problem is the case r=4, n=190. If the property holds for a given (r,n) then it clearly holds for (r,n') for any n' < n, which suggests that, for each r, there is a largest n such that the property holds. For r=2, the largest such n is 5. That is as far as I have got, but as I said this sounds like a problem that might have been extensively studied already. Derek Holt. ============================================================================== From: John Rickard Subject: Re: message passing Date: 04 Oct 2000 13:34:34 +0100 (BST) Newsgroups: sci.math mareg@mimosa.csv.warwick.ac.uk wrote: : Let 0 < r < n and take a set S of size n. Can we colour the size r-subsets : of S red and green, in such a way that for any subset T of S of size : r+1, the size r-subsets of T do not all have the same colour? : : Your problem is the case r=4, n=190. [...] as I said this sounds : like a problem that might have been extensively studied already. It's equivalent to asking whether the Ramsey number R(5,5;4) is greater than 190. A web search reveals at http://isu.indstate.edu/ge/RAMSEY/plex.html a construction by Geoff Exoo showing that R(5,5;4) > 33; I don't know any more about it, but there may well be an upper bound in the literature. -- John Rickard ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: message passing -- possible approach? Date: 4 Oct 2000 22:30:30 GMT Newsgroups: sci.math In article <8rcte901ivg@drn.newsguy.com>, wrote: >Player A has a deck of 190 cards numbered 1 to 190. > >He shuffles the deck and deals 5 cards to Player B. > >Player B selects 4 of the 5 cards and gives them to Player C. > >Is there any algorithm that Player B can use to select the 4 cards, >regardless of the 5 cards he is dealt, that will enable him to >communicate a message to Player C (even if it's just one bit of >information)? Sure. B can transmit at least four bits of information easily. Pick any four of the five cards, sort according to numerical order, then apply a permutation from Sym(4), and pass the cards carefully to C with "first" card on top, etc. (I am assuming that B and C have an opportunity to agree in advance on an enumeration of Sym(4).) Or, ask to use cards with a lot of whitespace, and then use a pencil... But seriously, I assume you are asking this: You have a set K of 190 distinguishible elements. You are asking whether it is possible to find two subsets Y and N of Comb(K,4) with the property that for all S in Comb(K,5), there is at least one element of Y and at least one element of N in Comb(S,4). (Here I write Comb(X,n) for the set of subsets of X of cardinality n.) The communication method is that player B will look the set S of cards dealt to him (not her?), and then pass to player C either an element of Y or and element of N depending on whether he intends to pass the information "Yes" or "No". Again this assumes B and C have a chance to agree ahead of time about what the subsets Y and N will be. I don't know the answer to this question but I can put it into context. I can also point to a potentially interesting solution in case the number "190" was chosen deliberately and not by chance. Let me start with an example: the game of Set. This is a very nice card game (which happens to mirror 4-dimensional affine geometry over the field of three elements!) There is a deck of 81 cards, and there is a rule for deciding when three cards do or do not form a "Set". Players put 12 cards face up and try to find a "Set" of three cards from among them. Occasionally it happens that among the 12 cards shown, there is no "Set". Whenever all players agree that this event has occured, another three cards from the deck are added to the face-up pool. This suggests the mathematical question: what's the worst that can occur, that is, what is the largest subset of the 81 cards which contains no "Set"? The answer turns out to be 20: every set of 21 cards contains at least one "Set" of three cards. (The definition of "Set" happens to imply that every pair of cards is contained in a unique "Set", so it also follows that every set of at least four cards contains a non-"Set", too.) To summarize this game: We start with a deck of 81 cards and a collection Y of subsets of cardinality 3; we compute the magic number 21 which has the property that every set of cardinality at least 21 contains at least one subset of cardinality 3 which is in Y, and at least one subset of cardinality 3 which is not in Y. We can use this observation for communication: shuffle the 81 cards, and give 21 of them to player B. He passes a Set of 3 cards to player C when he wants to say "Yes" and a non-Set of 3 cards to say "No". To generalize this game, suppose we are given a set K and a collection Y of subsets of cardinality n. We wish to know the smallest number m=m(K,Y) which has the property that every set of cardinality at least m contains at least one subset of cardinality n which is in Y, and at least one subset of cardinality n which is not in Y. There is no such number if Y is the empty set or the collection Comb(K,n) of _all_ subsets of cardinality n; otherwise it is clear that m exists and is at most |K|. We also have the obvious statement that m(K,Y) = m(K, Comb(K,n) - Y ) and the more general observation that m will have to be near the upper bound when Y is either very small or very large; beyond that, monotonicity is not so clear. So we then have this second-order question: given only the set K and the number n, what collections Y of n-element subsets of K make m(K,Y) particularly small? And just how small can it be? The answer depends only on k = |K| and n, so let us define a function f(k,n) = minimum of m(K,Y) over all subsets Y of Comb(K,n). The game of Set shows that f(81,3) is at most 21. Our other observations above show that f(k,n) <= k and that in order to compute f we need only consider collections Y of cardinality at most half of the binomial coefficient C(k,n). The original poster's question is now, is f(190,4) as low as 5? That is, can we construct a collection Y of 4-element subsets of a deck K of 190 distinct cards in such a way that m(K,Y) = 5 (meaning, I repeat, that every set of cardinality at least 5 contains at least one subset of cardinality 4 which is in Y, and at least one subset of cardinality 4 which is not in Y). As I say, I don't know the answer to this question offhand, but I can say a few things about the m's and f's. First, f(k,n) is defined iff there are some collections Y of n-element subsets of a k-element set other than the empty collection and its complement: iff 0 < n < k. From the definitions it follows that when defined, f(k,n) > n and <= k, so in particular f(k,k-1) = k . (Exercise: what does that last statement _mean_? What's Y?) When n=1, Y is a collection of singletons. In order to have a subset of K which is sure to contain both elements of Y and elements of K - Y, we will have to insist that the subset have more than |K|-|Y| elements and also more than |Y| elements, that is, m(K,Y) = max( |Y|, |K|-|Y| ) + 1, so that f(k,1) = ceiling(k/2) + 1. An optimal Y contains half the elements of K. For the case n=2, think of K as a set of people, and Y as the set of pairs of people in the set K who know each other. The computation of m(K,Y) asks, how many people must you assemble to be sure you have BOTH a pair of people who know each other and a pair of people who do not know each other? Then the computation of f(k,2) asks us to look for the "most mixed" crowd of k people, one in which it's particularly easy to assemble clusters containing both friends and strangers. I make it out to be that f(3,2)=f(4,2)=3 (let Y contain a single pair of friends in each case). f(5,2) is 3, too: if the pairs of people who know each other are Y={ {1,2}, {2,3}, {3,4}, {4,5}, {5,1} } then any set of three people includes a pair of friends and a pair of strangers. On the other hand, there's no collection of friendships among {1,2,3,4,5,6} with the property that every set of three includes friends and strangers; but if persons 1,2, and 3 are mutually acquainted and also persons 4,5, and 6 are mutually acquainted, then any set of four people will include both friends and strangers, so f(6,2)=4. Next, when n=3 the search is for particularly interesting collections of subsets of cardinality 3. I have already mentioned that f(81,3) is at most 21, since there is a way to describe "interesting" threesomes in a deck of 81 cards in such a way that every group of 21 cards includes at least one interesting threesome and one non-interesting threesome. Certainly f(4,3)=4, and f(5,3)=4 too. (Proof: take Y to be the set of five threesomes of the form {i-1, i, i+1} mod 5.) Would it help to state this in the language of the original problem? Replace "deck of 190 cards" with "deck of 5 cards"; replace "deals 5 cards" with "deals 4 cards"; and replace "selects 4 of the 5" with "selects 3 of the 4". The player B passes to player C the bit of information "Yes" by giving C three consecutive cards from his hand, and passes the bit "No" by giving C three non-consecutive cards. I don't know any good way to compute f(190,4). This calls for the construction of a particularly interesting collection of foursomes from among a set of 190 elements. I don't know if the 190 came into the picture as part of a homework assignment or not, but let's suppose it's a "right" number here --- that there is something about the 190 which fits into the problem of covering the set of foursomes in an interesting way. That is, let's see whether the number 190 turns up in Ramsey theory. I never remember how to state those Ramsey results intelligently. I forget the actual values, too. But I know they're in the sequence server! So I dial up the server and search for "190" and after a couple of irrelevant I entries notice A035347, which mentions covers of sets. This must be relevant! With the help of the MathSciNet review of the article mentioned in A035347 I can describe what the "190" is here; I don't know how to use this fact. OK, here are some interesting collections of subsets of [5]={1,2,3,4,5}: { {1,2,4,5}, {3,4,5} } { {1,4,5}, {2,4}, {3,5} } { {1,4,5}, {2,4,5}, {3} } { {1,4,5}, {2,4,5}, {3,5} } { {1,4,5}, {2,4,5}, {3,4,5} } Each collection has the following features: the union of the subsets is all of [5] (the collections are "covers"); each subset in the collection contains elements not in the other subsets (they are "minimal"); and there are precisely three elements (1,2,3) contained in one subset each (they have "3 unique points"). Permuting the five numbers 1,2,3,4,5 inside the subsets gives rise to more such collections; the orbits have cardinalities 30, 60, 30, 60, and 10, respectively -- 190 total -- and these are the only minimal covers of [5] with three unique points. How might we use this fact? Sorry -- I don't know how to shoehorn it into the current problem. Let's see, take 190 cards, and write out one of these covers on each of the cards. We are asked to assemble a collection Y of 4-tuples of elements of [190], so the question is, is there some way to look at _some_ foursomes of these fancy covers and call those foursomes "special", and declare the other foursomes "not special"? We have to do so in such a way as to guarantee that given _any_ five covers, there is at least one "special" foursome among them and at least one "non-special" foursome. Hmm; that leaves at most 5-1-1=3 foursomes which can go either way... let's see... 5 shows up in THIS way, and 3 shows up in THAT way... We take sets of 5 elements of [190], but each of the 190 cards is a cover of [5]... Duality? Diagonal construction?... Well, I don't get it. Maybe someone else sees a connection. I should just add that there are many contexts in which this kind of combinatorial reasoning appears. I have already used the buzzword "Ramsey theory". One also encounters these ideas in graph-colouring problems, in the theory of designs (BIBDs), and in finite geometries. It's really very rewarding to find symmetric arrangements of such collections Y for which m(K,Y) is rather small; these give upper bounds on the numbers f(k,n). (Finding good lower bounds is harder, I think, but not necessary for the particular problem which started this thread.) These are not simple functions; e.g. we have already showed that f(5,n) is not monotone. dave ============================================================================== From: pragma@A0L.C0M Subject: Re: message passing -- possible approach? Date: 5 Oct 2000 14:08:44 -0700 Newsgroups: sci.math rusin@vesuvius.math.niu.edu wrote: >In article <8rcte901ivg@drn.newsguy.com>, wrote: > >>Player A has a deck of 190 cards numbered 1 to 190. >> >>He shuffles the deck and deals 5 cards to Player B. >> >>Player B selects 4 of the 5 cards and gives them to Player C. >> >>Is there any algorithm that Player B can use to select the 4 cards, >>regardless of the 5 cards he is dealt, that will enable him to >>communicate a message to Player C (even if it's just one bit of >>information)? > >Sure. B can transmit at least four bits of information easily. >Pick any four of the five cards, sort according to numerical order, >then apply a permutation from Sym(4), and pass the cards carefully >to C with "first" card on top, etc. (I am assuming that B and C >have an opportunity to agree in advance on an enumeration of Sym(4).) I should have stated that Player C is required to shuffle the cards thoroughly before looking at them :-) [snip excellent lengthy discussion] >The original poster's question is now, is f(190,4) as low as 5? Thank you. I didn't know how to state it that concisely. >That is, can we construct a collection Y of 4-element subsets of >a deck K of 190 distinct cards in such a way that m(K,Y) = 5 >(meaning, I repeat, that every set of cardinality at least 5 >contains at least one subset of cardinality 4 which is in Y, >and at least one subset of cardinality 4 which is not in Y). >As I say, I don't know the answer to this question offhand, but >I can say a few things about the m's and f's. Is there any resource on the net where I could find the answer, or some further clues? >Would it help to state this in the language of the original problem? >Replace "deck of 190 cards" with "deck of 5 cards"; replace >"deals 5 cards" with "deals 4 cards"; and replace "selects 4 of the 5" >with "selects 3 of the 4". The player B passes to player C the >bit of information "Yes" by giving C three consecutive cards from >his hand, and passes the bit "No" by giving C three non-consecutive >cards. Good example. >I don't know any good way to compute f(190,4). This calls for the >construction of a particularly interesting collection of foursomes >from among a set of 190 elements. I don't know if the 190 came >into the picture as part of a homework assignment or not, No, it's not a homework assignment. I'm a number puzzle hobbyist, and there's a particular problem I'm working on that could be solved nicely if I could get a "yes" answer. Thanks again for the discussion.