Author |
Topic: Finding secrets (Read 600 times) |
|
pharaoh
Newbie
Gender: 
Posts: 50
|
 |
Finding secrets
« on: Jan 23rd, 2007, 9:49am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
Ghost Sniper
Senior Riddler
Do not hide. It is useless.
Gender:
Posts: 599
|
|
Re: Finding secrets
« Reply #1 on: Jan 23rd, 2007, 10:43am » |
Quote Modify
|
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?
|
|
IP Logged |
*sob* I miss my mommy... *blows nose* huh, I'm on? oh right.
(thinks to self) Time for my speech to these college kids.
"Reason is more important than all emotions..."
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Finding secrets
« Reply #2 on: Jan 23rd, 2007, 11:00am » |
Quote Modify
|
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.
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
Ghost Sniper
Senior Riddler
Do not hide. It is useless.
Gender:
Posts: 599
|
|
Re: Finding secrets
« Reply #3 on: Jan 23rd, 2007, 11:08am » |
Quote Modify
|
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... 
|
|
IP Logged |
*sob* I miss my mommy... *blows nose* huh, I'm on? oh right.
(thinks to self) Time for my speech to these college kids.
"Reason is more important than all emotions..."
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Finding secrets
« Reply #5 on: Jan 23rd, 2007, 11:41pm » |
Quote Modify
|
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.
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Finding secrets
« Reply #6 on: Jan 23rd, 2007, 11:43pm » |
Quote Modify
|
I think n=4 is the point from which the problem can be solved by getting optimal solutions to subproblems.
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
sk
Newbie
Posts: 45
|
|
Re: Finding secrets
« Reply #7 on: Jan 27th, 2007, 6:11pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Finding secrets
« Reply #8 on: Jan 27th, 2007, 8:13pm » |
Quote Modify
|
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;
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
