Thread: Tricky word problem

There is a group of 30 people who communicate only by phone. During any one to one phone conversation the two members exchange all their information. Find the number of calls needed so that everyone finds out every bit of news.

It cannot be done. Whenever two communicate, that communication represents new information and there are immediately 28 who do not know what they discussed.

My views. I welcome others'.

If there are only 2 people, 1 phone call is required to exchange all information.
If there are three people (A, B, & C), a minimum of three calls must be made. (A calls B then A and B have each others info. C calls B then C and B have everyone's info. A calls either B or C and then A has everyone's info)
If there are 4 people, a minimum of 4 phone calls is required.
If there are 5 people, a minimum of 6 phone calls is required.
If there are 6 people, a minimum of 8 phone calls is required.

What I have come up with to find the minimum number of calls required:
Where n = # of people, 2n - 4; n >3

Math not philosophy

I dare you to put logic exclusively in either of those buckets you have named.

Very good point. However, all logic should be in the "math bucket" when dealing with the "Math Help Forum." Do you think your answer would fly with a math professor? I think it might with a philosophy professor... Anyways, I hope I did not offend you. What do you think of my work so far? I think my formula may be flawed when n > 6.

I would put it on an exam in a methematics class. I suppose I could be different.

Your formula is interesting. How do you propose to prove it?

This doesn't quite do it...
Four, for example:

A<==>B ==> A(b) and B(a)
B(a)<==>C ==> B(ac) and C(ab)
C(ab)<==>D ==> C(abd) and D(abc)
D(abc)<==>A(b) ==> D(abc) and A(bcd)
A(bcd)<==>B(a) ==> A(bcd) and B(abc)

It's a little irritating that A has to call B twice, but this may establish an absolute maximum number of necessary calls, one greater than the number of participants.

A<==>B ==> A(b) and B(a)
C<==>D ==> C(d) and D(c)
D(c)<==>A(b) ==> A(bcd) and D(abc)
B(a)<==>C(d) ==> B(acd) and D(abc)

One Shorter!

Maybe five participants.

A<==>B ==> A(b) and B(a)
B(a)<==>C ==> B(ac) and C(ab)
C(ab)<==>D ==> C(abd) and D(abc)
D(abc)<==>E ==> D(abce) and E(abcd)
E(abcd)<==>A(b) ==> A(bcde) and E(abcd)
A(bcde)<==>B(ac) ==> A(bcde) and B(acde)
B(acde)<==>C(abd) ==> B(acde) and C(abde)

Okay, now I have to revise the absolute maximum. I'm going with (n-1)+(n-2) = 2n-3. I could prove that.

Fine, I think we have an absolute maximum. If you can ALWAYS do it with one fewer, maybe you have something. Are you sure you cannot EVER do it in two fewer? This is mathematics. You must PROVE it.

Originally Posted by TKHunny

I would put it on an exam in a methematics class. I suppose I could be different.

Your formula is interesting. How do you propose to prove it?

This doesn't quite do it...
Four, for example:

A<==>B ==> A(b) and B(a)
B(a)<==>C ==> B(ac) and C(ab)
C(ab)<==>D ==> C(abd) and D(abc)
D(abc)<==>A(b) ==> D(abc) and A(bcd)
A(bcd)<==>B(a) ==> A(bcd) and B(abc)

It's a little irritating that A has to call B twice, but this may establish an absolute maximum number of necessary calls, one greater than the number of participants.

A<==>B ==> A(b) and B(a)
C<==>D ==> C(d) and D(c)
D(c)<==>A(b) ==> A(bcd) and D(abc)
B(a)<==>C(d) ==> B(acd) and D(abc)

One Shorter!

Maybe five participants.

A<==>B ==> A(b) and B(a)
B(a)<==>C ==> B(ac) and C(ab)
C(ab)<==>D ==> C(abd) and D(abc)
D(abc)<==>E ==> D(abce) and E(abcd)
E(abcd)<==>A(b) ==> A(bcde) and E(abcd)
A(bcde)<==>B(ac) ==> A(bcde) and B(acde)
B(acde)<==>C(abd) ==> B(acde) and C(abde)

Okay, now I have to revise the absolute maximum. I'm going with (n-1)+(n-2) = 2n-3. I could prove that.

Fine, I think we have an absolute maximum. If you can ALWAYS do it with one fewer, maybe you have something. Are you sure you cannot EVER do it in two fewer? This is mathematics. You must PROVE it.

very helpful. My only question is where did the (n-1)+(n-2) come from? I can see how your absolute maximum can be easily proved through induction. I am not sure that I cannot do it in 2 fewer.

Follow the path.

1st Call - Nothing
2nd Call - Nothing
...
(n-1)st call - 2 winners
nth call - 1 winner
(n+1)th call - 1 winner
...
[(n-1)+(n-2)]th call - 1 winner and done.