puzzle puzzling me: 25 people, a rumor, and an island

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

bobjoesmith
Posts: 43
Joined: Wed Feb 17, 2010 9:32 pm UTC

puzzle puzzling me: 25 people, a rumor, and an island

Postby bobjoesmith » Wed Nov 03, 2010 12:20 am UTC

So i have no idea what the answer is and kinda want to find out lol

There are 25 people on a island; they are the only 25 people. One person starts a rumor, and tells people until he meets someone who has already heard the rumor. Everyone who hears the rumor will continue telling the rumor until they meet someone who has already heard the rumor. What is the chance that all 25 people will hear the rumor.

For instance, if A starts a rumor, tells B. B tells C. Then if A meets C, both would stop telling the rumor. If A had also told D, and B met D, then both would also stop and not everyone would have heard.

Since its math, i guess pretend each person would meet the same number of people in a given amount of time

For instance, if A had started and told B, then while B told C, A also would be simultaneously telling D.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: puzzle puzzling me: 25 people, a rumor, and an island

Postby Qaanol » Wed Nov 03, 2010 1:01 am UTC

Can we assume that if a person X tells the rumor to a person Y, then both X and Y will now “know the other one has heard the rumor” and thus they will never “meet” again, since no one will ever try to tell the rumor to the same person a second time, nor the person who originally told them?

Also, I think the “everyone talks to the same number of people in the same amount of time” is both important and impossible. You have an odd number of people. Since the number of people is finite, the only way to guarantee everyone talks to the same number of people in the same amount of time is to have discrete time steps and pair people off 1-to-1 at each time step. But you can’t do this with an odd number of people. Well either that, or you have to allow groups of people to meet simultaneously, so one person can tell the rumor to the whole group, but then the problem is very different.
Last edited by Qaanol on Thu Nov 04, 2010 12:02 am UTC, edited 1 time in total.
wee free kings

Mewzle
Posts: 7
Joined: Sat Oct 30, 2010 5:03 pm UTC

Re: puzzle puzzling me: 25 people, a rumor, and an island

Postby Mewzle » Wed Nov 03, 2010 9:21 pm UTC

Does the time matter? I thought we were working out the chance. If B and D converse at the same time as A and C, or at different times, as long as they're in the same order it won't affect the chance at all?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: puzzle puzzling me: 25 people, a rumor, and an island

Postby jestingrabbit » Wed Nov 03, 2010 11:14 pm UTC

I think it does matter, for precisely the reasons that qaanol mentioned. I think the best way to get at a formalisation would be to have something like "at any given time step, two people will be chosen uniformly at random from the group, and they will have an interaction". For the purposes of a simulation you could concern yourself only with those pairings where at least one of the participants knows the rumour as only those change the state of the system.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

GeorgeH
Posts: 527
Joined: Mon Aug 17, 2009 6:36 am UTC

Re: puzzle puzzling me: 25 people, a rumor, and an island

Postby GeorgeH » Thu Nov 04, 2010 2:32 am UTC

As has been mentioned, the problem is far from being well defined. More than that, without a very careful rephrasing I don't see this ever being a logic puzzle so much as a difficult^x math problem, with good potential for x>>1.

If you start with one person knowing the rumor, select a random pair of people to interact, have the rumor spread if one of those people is an "active" gossip and one hasn't heard the rumor, and make people "inactive" gossips if they attempt to transmit a rumor to someone who already knows it (discarding silly cases such as attempting to tell the person who told them in the first place and attempting to tell the same person twice) the chance of all 25 people on the island knowing the rumor is ~0.15%, and in general ~9.9 people will be ignorant of the rumor.

If you do basically the same thing, but instead of a random pair of people you iterate through each individual in an ordered fashion and select a random person for them to talk to, the chance of all 25 people on the island knowing the rumor is ~1.3%, and in general ~7.6 people will be ignorant of the rumor.

If again you do basically the same thing, but instead of a random pair you iterate through each individual and select a random person that they haven't yet had a conversation with, the chance of all 25 people on the island knowing the rumor is ~0.99%, and in general ~8.4 people will be ignorant of the rumor.

The quick, dirty, and very possibly buggy Python code used to arrive at those numbers:
Spoiler:

Code: Select all

from numpy import *

people=25
iterations=100000
#Available modes: 1, 2, 3
mode=2
islanders=zeros([people,2])
success=0
average=0

for i in range (0, iterations):
    islanders[:]=0
    islanders[0,0]=1
    rumor=1
    norumor=people-1
    person1=-1
    person2=-1
    if mode==3:
        conversations=zeros([people,people])   
   
    while rumor>=1 and norumor!=0:
        if mode==1:
            person1=random.randint(0,people)
            person2=random.randint(0,people)
            while person1==person2:
                person2=random.randint(0,people)
        elif mode==2:
            if person1<(people-1):
                person1=person1+1
            else:
                person1=0
            person2=random.randint(0,people)
            while person1==person2:
                person2=random.randint(0,people)
        elif mode==3:
            if person1<(people-1):
                person1=person1+1
            else:
                person1=0
               
            person2=random.randint(0,people)
            while (person1==person2) and (conversations[person1,person2]==1):
                person2=random.randint(0,people)
            conversations[person1,person2]=1
            conversations[person2,person1]=1
           
   
        if (islanders[person1,0]+islanders[person2,0])==1:
            norumor=norumor-1
            rumor=rumor+1
            if islanders[person1,0]==0:
                islanders[person1,0]=1
                islanders[person1,1]=person2
            else:
                islanders[person2,0]=1
                islanders[person2,1]=person1
        elif (islanders[person1,0]+islanders[person2,0])==2:
            if islanders[person1,1]!=person2 and islanders[person2,1]!=person1:
                islanders[person1,0]=2
                islanders[person2,0]=2
                rumor=rumor-2
        elif (islanders[person1,0]+islanders[person2,0])==3:
            if islanders[person1,1]!=person2 and islanders[person2,1]!=person1:
                if islanders[person1,0]==1:
                    islanders[person1,0]=2
                    rumor=rumor-1
                else:
                    islanders[person2,0]=2
                    rumor=rumor-1

    if norumor==0:
        success=success+1
    average = average+norumor
    #print "Iteration number ", i+1
    #print "Ignorant people ", norumor
   
print "Total number of trials ", iterations
print "Number of successful trials ", success
print "Success ratio ", float(success)/float(iterations)
print "Average number of ignorant people ", float(average)/float(iterations)

bobjoesmith
Posts: 43
Joined: Wed Feb 17, 2010 9:32 pm UTC

Re: puzzle puzzling me: 25 people, a rumor, and an island

Postby bobjoesmith » Thu Nov 04, 2010 3:34 pm UTC

thanks... i got a pretty good idea of what it could be... i didn't get anything more from the problem asked by a friend, but im kind of leaning toward assumption of

GeorgeH wrote:If again you do basically the same thing, but instead of a random pair you iterate through each individual and select a random person that they haven't yet had a conversation with, the chance of all 25 people on the island knowing the rumor is ~0.99%, and in general ~8.4 people will be ignorant of the rumor.

ralphmerridew
Posts: 19
Joined: Wed Jul 11, 2007 3:14 pm UTC

Re: puzzle puzzling me: 25 people, a rumor, and an island

Postby ralphmerridew » Wed Nov 24, 2010 5:48 pm UTC

Under the "two people meet at random" model, it's possible to get an exact rational solution:
Spoiler:
Classify people into 3 groups X (ignorant), Y (active gossip), and Z (passive gossip).

Define f(X, Y, Z) as follows:
if X = 0 and Y >= 0, f = 1
if X > 0 and Y = 0, f = 0
if X < 0 or Y < 0, f = 0. (Exact value doesn't matter; this will be multiplied by 0.)
otherwise,
let c1 = X*Y
let c2 = Y*(Y-1)/2
let c3 = Y*Z
let c4 = c1 + c2 + c3
f(X, Y, Z) = (c1*f(X-1, Y+1, Z) + c2*f(X, Y-2, Z+2) + c3*f(X, Y-1, Z+1))/c4

Then calculate f(24, 1, 0).

To calculate the probability that exactly N people remain ignorant, change the base cases to:
f'(N, 0, *) = 1; f'(k != N, 0, *) = 0; f'(0, *, *) = 0.

To calculate the average number of ignorant people at the end, calculate sum(N = 1 to 24: N*P(exactly N people remain ingorant at end)).


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 8 guests