wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Finding secrets
        
(Message started by: pharaoh on Jan 23^rd, 2007, 9:49am)

Title: Finding secrets
Post by pharaoh on Jan 23^rd, 2007, 9:49am

I dont know whether this has been discussed here before or not. Also, I have heard this puzzle from one of my friends so dont know the exact details. I am presenting the problem as I know it, no additional details are known.

There are 100 people present, each one knows a secret i.e their own secret. When person 1 and 2 talk they share their secrets. When person i talks to person i+1 he divulges all the secrets of others known to him and his own secret. So what are the minimum number of conversations required to know secrets of all the people?

People talk in this order 1 talks to 2, 2 talks to 3...i talks to i+1 etc. A person can talk more than once.

Title: Re: Finding secrets
Post by hiyathere on Jan 23^rd, 2007, 10:43am

Do you mean the minimum required for everyone to know everyone else's secret, or the minimum required for one person to know everyone's secret. And which one?

Title: Re: Finding secrets
Post by pharaoh on Jan 23^rd, 2007, 11:00am

Frankly I dont know, to start with lets assume it is the minimum number of conversation required for one person to know secrets of all others. Then lets go ahead and figure out the other part.

Title: Re: Finding secrets
Post by hiyathere on Jan 23^rd, 2007, 11:08am

In that case, I would say at least 99 times, and that is for the person last in line. I still need to think about this... :P

Title: Re: Finding secrets
Post by towr on Jan 23^rd, 2007, 12:43pm

There some similarity to the problem in "Journalist information exchange" (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1107351085). Although there each conversation is a threeway conference call.

Title: Re: Finding secrets
Post by pharaoh on Jan 23^rd, 2007, 11:41pm

I clarified with the source of problem, we need to find out minimum number of conversations needed so that every one knows every one else's secret.

This is my intial analysis for max 6 persons:

For 2 persons -> 1 cnoversation
For 3 persons -> 3 cnoversation
For 4 persons -> 4 cnoversation
For 5 persons -> 6 cnoversation
For 6 persons -> 8 cnoversation

Upto 4 it is very cool but after that there is a pattern observed as follows:

For 4 people, A,B,C and D.

(A,B) (C,D) (A,C) (B,D)

for 5 people :

(A,E) (A,B) (C,D) (A,C) (B,D) (A, E)

for 6 it should be:

(A, F) (A,E) (A,B) (C,D) (A,C) (B,D) (A, E) (A,F)

So we can solve this problem by reducing it to a smaller problem (up to n = 4)and then just adding the conversations as shown above.

I havent tried for more than 6-7 persons but I think this should hold true for 100 persons too.

Title: Re: Finding secrets
Post by pharaoh on Jan 23^rd, 2007, 11:43pm

I think n=4 is the point from which the problem can be solved by getting optimal solutions to subproblems.

Title: Re: Finding secrets
Post by sk on Jan 27^th, 2007, 6:11pm

person i talking to i+1 means, that person 3 tells person 4 all the scerets, but there is no path back to person 3. so 3 will never know unless this assumption is dropped.

if we drop it, then probably it is 198. 99 (each way) ,if we can imagine that to be a tournament tree. To select a winner out of 100 people, there have to be 99 people eliminated (99 matches).

Title: Re: Finding secrets
Post by pharaoh on Jan 27^th, 2007, 8:13pm

You are right sk, I phrased the question badly and without knowing it completely. People can talk to each other i.e. forward and backward paths are possible.

So, for 100 people the minimum number of conversation needed are 196. After analysing the outputs for n > 4, the answers will be 2n - 4.

for n = 100, 2*100 - 4 = 196;