novaBBS - rec.puzzles - Re: cotpi 62

Re: cotpi 62 - Efficient gossiping

<50a716cb-767c-4a17-91a5-441c6bb74bbcn@googlegroups.com>

https://novabbs.com/interests/article-flat.php?id=504&group=rec.puzzles#504

X-Received: by 2002:ac8:5a8c:0:b0:35b:b2f7:7e96 with SMTP id c12-20020ac85a8c000000b0035bb2f77e96mr19790901qtc.659.1663688617850;
Tue, 20 Sep 2022 08:43:37 -0700 (PDT)
X-Received: by 2002:a05:6214:29c2:b0:4ad:68be:8c57 with SMTP id
gh2-20020a05621429c200b004ad68be8c57mr403953qvb.3.1663688617726; Tue, 20 Sep
2022 08:43:37 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: rec.puzzles
Date: Tue, 20 Sep 2022 08:43:37 -0700 (PDT)
In-Reply-To: <k3cthm$ilb$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=2601:648:8600:8880:e4f9:b48f:7205:cbd;
posting-account=YjTkGAoAAAA4_fbAISfvtIqrYbghMeBx
NNTP-Posting-Host: 2601:648:8600:8880:e4f9:b48f:7205:cbd
References: <k3cthm$ilb$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <50a716cb-767c-4a17-91a5-441c6bb74bbcn@googlegroups.com>
Subject: Re: cotpi 62 - Efficient gossiping
From: henha...@gmail.com (henh...@gmail.com)
Injection-Date: Tue, 20 Sep 2022 15:43:37 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2029

by: henh...@gmail.com - Tue, 20 Sep 2022 15:43 UTC

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 ?

Re: cotpi 62 - Efficient gossiping

<ggSdnc9S98BMYrT-nZ2dnZfqnPpg4p2d@brightview.co.uk>

copy mid

https://novabbs.com/interests/article-flat.php?id=505&group=rec.puzzles#505

copy link Newsgroups: rec.puzzles

Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!69.80.99.27.MISMATCH!Xl.tags.giganews.com!local-2.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 20 Sep 2022 18:00:49 +0000
Subject: Re: cotpi 62 - Efficient gossiping
Newsgroups: rec.puzzles
References: <k3cthm$ilb$1@dont-email.me> <50a716cb-767c-4a17-91a5-441c6bb74bbcn@googlegroups.com>
From: news.dea...@darjeeling.plus.com (Mike Terry)
Date: Tue, 20 Sep 2022 19:00:48 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.12
MIME-Version: 1.0
In-Reply-To: <50a716cb-767c-4a17-91a5-441c6bb74bbcn@googlegroups.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <ggSdnc9S98BMYrT-nZ2dnZfqnPpg4p2d@brightview.co.uk>
Lines: 97
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-9gt1/xL1cVpg99r4G78z6oCnY6iMZQ5dbyaFxT/JJWsHIvLbDVbMV2AvovB5Kxpt7xyoX+cpBuQ2lFV!9WFelymVvOlhh6zGysxNu7AQv8aGngLQBPV3CGyh/cxAEagrhp95oOuC2bX3mMRK3PpApkEEXmDJ!1L9+32uXnOPFz6NIt4xkEH0dewE=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Received-Bytes: 3461

by: Mike Terry - Tue, 20 Sep 2022 18:00 UTC

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.

..
..
..

I will make you shorter by the head. -- Elizabeth I

interests / rec.puzzles / Re: cotpi 62 - Efficient gossiping

Subject	Author
Re: cotpi 62 - Efficient gossiping	henh...@gmail.com
Re: cotpi 62 - Efficient gossiping	Mike Terry