cotpi 62 - Efficient gossiping

30 views
Skip to first unread message

cotpi

unread,
Sep 19, 2012, 12:50:23 PM9/19/12
to
Each of n male citizens knows a different piece of gossip. They
are allowed to exchange the gossip they know by phone. During a
call, just one of the men speaks and tells the other all the
gossip he knows. What is the minimum number of calls required to
enable each man to know all the gossip?

--
cotpi
http://cotpi.com/

Alexander Thesoso

unread,
Sep 19, 2012, 6:37:23 PM9/19/12
to
2N - 3
It takes N-1 calls until the first pair is up to date, and N-2 to
communicate the result to the rest.

Eric Sosman

unread,
Sep 19, 2012, 8:42:46 PM9/19/12
to
The offered formula is obviously wrong for N=1 and N=2,
which leads me to doubt its accuracy for greater N. I think
Alexander has overlooked the "just one of the men speaks"
part of the problem statement.

2N-2 clearly suffices: Consider a tree whose N-1 edges
are traversed once toward the root and once away. I have a
sneaking suspicion that 2N-2 is *the* answer, but I also have
a nagging worry that a cleverer arrangement might exist.

--
Eric Sosman
eso...@ieee-dot-org.invalid

James Dow Allen

unread,
Sep 20, 2012, 5:04:04 AM9/20/12
to
On Sep 20, 7:42 am, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
>      2N-2 clearly suffices: Consider a tree whose N-1 edges
> are traversed once toward the root and once away.  I have a
> sneaking suspicion that 2N-2 is *the* answer, but I also have
> a nagging worry that a cleverer arrangement might exist.

Let A be a solution for N citizens. If we can always construct a
solution for (N-1) citizens by removing two edges from A, then
Sosman's Conjecture will follow by induction.

Pick any citizen C whose first call is out-going. We will derive
a solution A', with at least two fewer edges than A,
for the (N-1) citizens other than C. We delete C's
first call (always out-going by choice of C); and his
first in-coming call (label the caller D).
We now need only to reroute C's remaining calls
to ensure the same gossip criterion is met.

Replace all of C's out-going calls (except first call which
was simply deleted) by calls from D.

The only complication that can arise is if C received two or
more in-coming calls, i.e. calls from E, F, etc. after his
call from D. Replace each of these calls (E-->C, F-->C, etc.)
with calls to D (E-->D, F-->D, etc.)

This works, no?

James

Ed Murphy

unread,
Sep 20, 2012, 11:57:21 AM9/20/12
to
Each call increases only one man's knowledge, so someone must be first
(no ties) to know all the gossip. After that, each other man must
receive at least one call, so n-1 calls are needed.

Now we need to get to that intermediate point. Define a "clique" as a
set of men joined to each other, but not to any others, by chains of
past phone calls. (The members of a clique may not have all their
knowledge in common, but they definitely don't have any knowledge in
common with any non-members.) We start with n one-man cliques, and
each call can merge at most two cliques, and no one can possibly know
all the gossip until there's a single n-man clique, so again n-1 calls
are needed.

henh...@gmail.com

unread,
Sep 20, 2022, 11:43:39 AMSep 20
to
On Wednesday, September 19, 2012 at 9:50:23 AM UTC-7, cotpi wrote:

> Each of N male citizens knows a different piece of gossip. They
nice problem !

i too overlooked the part [ During a call, just one of the men speaks ]

what if... Each of the (white, cis) men knows 6 (completely) distinct Gossip-items
and During a call, the max items that can be conveyed are:

-- 1 item
-- 2 items
-- 3 items
-- 4 items
-- 5 items ?

Mike Terry

unread,
Sep 20, 2022, 2:00:57 PMSep 20
to
There's no max items limit. So we may as well assume that initially each male knows 1 gossip item,
and all items are distinct. (So there are N different items to propagate).

.
.
.
.
.
.
.
.
.
. (spoiler space)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. (spoiler space)
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
. (spoiler space)
.
.
.
.

As some point there will be a telephone call where for the first time a male learns all the items.
To start with there are N-1 other males with their own gossip to convey, so it will take at least
N-1 phone calls to reach the "one mail knows all" event. Following the event, there will be N-1
males missing some items, so it will take at least N-1 phone calls to inform them.

Conclusion: required phone calls >= (N-1) + (N-1) = 2N - 2

But this minimum is easily achievable, e.g.
- one male is selected (he will be the luck first know-all!)
- all the rest phone him and tell him their gossip
- then he phones all the others to tell them the complete gossip

Mike.


.
.
.
Reply all
Reply to author
Forward
0 new messages