# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Griffin
Daedalian Member

 Posted: Sun Sep 13, 2009 12:55 am    Post subject: 1 In puzzlania, there are n logicians who love nothing better than to take a break from logickizing and share a bit of gossip. Initially, every logician knows one juicy bit of gossip. In order for one logician to call another, he must know at least one bit of gossip that the other does not. Furthermore, once on the phone, the two logicians inevitably share all the gossip that they know. What is the most number of phone calls that can be made before everyone knows everything?
mith
Pitbull of Truth

 Posted: Sun Sep 13, 2009 1:01 am    Post subject: 2 (n^2-n)/2? A calls B. C calls A. C calls B. D calls A. D calls C. D calls B. etc. Every pair talks once.
Griffin
Daedalian Member

 Posted: Sun Sep 13, 2009 2:06 am    Post subject: 3 Yep . Now, proof?
Zag
Tired of his old title

 Posted: Sun Sep 13, 2009 3:46 pm    Post subject: 4 Proof: f(2) = 1, by obviousness. f(N) = f(N-1) + N -1, since you can isolate one person and no one calls him, and arrive f(N-1) with the remaining group. Then the one isolated person calls each of the others, none of whom have heard his gossip yet. With some algebra, this works out to mith's formula (I'm pretty darn sure).
Quailman
His Postmajesty

 Posted: Sun Sep 13, 2009 3:49 pm    Post subject: 5 Homework alert! I think you're being asked to help this kid with his homework.
Zag
Tired of his old title

Posted: Sun Sep 13, 2009 4:26 pm    Post subject: 6

 Griffin's Profile wrote: All about Griffin Daedalian Member Joined: 15 Aug 1999 Total posts: 1194

I thought I recognized the name. He's not quite an addict, but he's hardly a newcomer. If it is homework help, I'm happy to provide it. Especially since I left my "proof" only half done.
Quailman
His Postmajesty

 Posted: Sun Sep 13, 2009 6:27 pm    Post subject: 7 Can't you tell when I'm being sarcastic?
mith
Pitbull of Truth

 Posted: Sun Sep 13, 2009 6:46 pm    Post subject: 8 Zag, that proof unfortunately only gives us a minimum. It doesn't prove that we can't do better. (The basic idea of the proof seems pretty straightforward, I'm just too lazy to work out the details right now. And Griffin probably has something super elegant in mind. )
Zag
Tired of his old title

 Posted: Sun Sep 13, 2009 8:31 pm    Post subject: 9 Fair enough. However, that represents every person talking to every other person, so it is clearly the maximum, too. (Well, clear to me, anyway. Perhaps it isn't clear to a mathematical certainty.) Q. I'm ignoring you.
mith
Pitbull of Truth

 Posted: Sun Sep 13, 2009 8:42 pm    Post subject: 10 It's clear to me too. But we can clearly have a given pair talk more than once (A talks to B, A talks to C, A talks to B again now that he has a new piece of gossip from C). We can see from the three person example that A talking to B again rules out B talking to C, so we've got the same total. But showing that that is always the case may be a little tricky.
Griffin
Daedalian Member

Posted: Mon Sep 14, 2009 1:06 am    Post subject: 11

 mith wrote: And Griffin probably has something super elegant in mind.

I'm not sure about that, but I thought it was a fun problem to think about.

I'll point out that there are n logicians, and every logician needs n-1 pieces of gossip. Since each call transmits at least one piece of gossip, you can have at most n(n-1) calls. But notice this is off by a factor of two from mith's solution. So proving mith's solution is best equates to showing that, for each call (on average), two pieces of gossip are shared.

Oh, and Quailman reminds me: I need the solution by Wednesday if possible, thanks .
ralphmerridew
Daedalian Member

 Posted: Sat Sep 19, 2009 8:38 am    Post subject: 12 It's possible for logicians to call each other many times; if things are chosen properly, it's possible for one pair to have n-1 calls between themselves. Algorithm: - Sort the logicians into some order. Call the lowest numbered logician Alice - Repeat: - - Alice will call the highest numbered logician X such that Alice can tell X something new, but X can not tell Alice anything new, if there is one. - - Otherwise, then Alice will call the lowest numbered logician X such that X can tell Alice something new, if there is one. - - Otherwise, stop the algorithm. So the pattern goes AB, AC, AB, AD, AC, AB, AE, AD, AC, AB, ...
Lepton
1:41+ Arse Scratcher

 Posted: Sun Sep 20, 2009 4:49 am    Post subject: 13 That's cute, and it gives exactly mith's formula, I think. (10 for n=5) I think I'm not alone in thinking that there must be an elegant proof, but my efforts have been futile.
L'lanmal
Daedalian Member

 Posted: Sun Sep 20, 2009 4:05 pm    Post subject: 14 This may be one of those occasions where it is easier to prove a more general formula, then specialize to the starting conditions (of each logician only knowing 1 piece of information).
L'lanmal
Daedalian Member

 Posted: Tue Sep 22, 2009 9:53 pm    Post subject: 15 I think I'm on to something here, but I'm not all the way there. Suppose we limit the logicians to speaking to their neighbors on either side. Label the action of logician i speaking to logician i+1 as "s i " The braid relations are satisfied. (That is, For |j-k| > 1, s j s k =s k s j . Which is another way of saying if two groups of logicians go a while without talking to each other, it doesn't matter which group talks amongst themselves first. For |j-k| = 1, s j s k s j =s k s j s k : If three logicians talk amongst themselves three times, all three of them know the same things.) The requirement that two cannot talk unless they have something to share ensures that conversations do not attempt to go up in the Bruhat order. Therefore, the number of times the logicians will talk is (at most) equal to the number of inversions of the permutation (n, n-1, n-2, n-3 ... , 2, 1), which is n*(n-1)/2. It remains to show that if "distant" logicians speak to each other, it can only accelerate the information sharing.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersGriffinL'lanmalLeptonmithQuailmanralphmerridewZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum