• #### Re: cotpi 62 - Efficient gossiping

From henhanna@gmail.com@21:1/5 to cotpi on Tue Sep 20 08:43:37 2022
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
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/

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 ?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Mike Terry@21:1/5 to henh...@gmail.com on Tue Sep 20 19:00:48 2022
On 20/09/2022 16:43, henh...@gmail.com wrote:
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
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/

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 ?

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.

.
.
.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)