30 views

Skip to first unread message

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/

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/

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.

It takes N-1 calls until the first pair is up to date, and N-2 to

communicate the result to the rest.

Sep 19, 2012, 8:42:46 PM9/19/12

to

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

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
> 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.

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

Sep 20, 2012, 11:57:21 AM9/20/12

to

(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.

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 ?

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

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 ?

Sep 20, 2022, 2:00:57 PMSep 20

to

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

Search

Clear search

Close search

Google apps

Main menu