Time for a light exercise -->

[bnashier]

After all trifles in a daily life, coming back to mathematics is always refreshing. Here is an exercise.

In any meeting of 20 people, there always is a bunch of at least four who either mutually agree with each other or mutually disagree with each other.

What is the largest such bunch guaranteed?

[ajmer]

That should be 16.

-ajmer

[bnashier]

[quote]Ajmer Dahiya (Apr 02, 2004 07:39 p.m.):
That should be 16.


Dear Ajmer:

16 is a high number. Number will not exceed 10.

Think of the same problem when the language is changed a bit. Stating a problem in different ways always helps to understand it better.

In any collection of 20 people, there always is a bunch of at least four who are either mutual friends or mutual strangers.

What is the largest such bunch guaranteed?

You can take 10 mutual friends. Then collect 10 folks from a place so that none of them knows the earlier bunch. Put them together.

[bnashier]

Bhai Ajmer:

A close analysis reveals that the number won't exceed 5. Let us do this: we take 5 groups (A, B, C, D, E) of people such that

a) each group contains exactly 4 people
b) all members of each group are mutual friends
c) no member of a group knows anybody in the other groups.

Now we put them together. What we have is this:

(i) maximum number of mutual friends is 4.
(ii) maximum number of strangers is 5. (you will have to pick just one person from each group to make a group of strangers.)

Now the problem is this: Is 5 always guaranteed?

[anujkumar]

Dear Nashier Sir,

What about the following proposition:

5 should be guranteed. Infact if we were to choose N people. We can contruct such set (with minimum i.e. guranteed max (#(friends),#(strangers)) as follows

Choose largest interger k such that k*k is less than N. (in case N is a perfect square, answer is ofcourse k). Than the answer is k+1, simply because we know we can do (K+1)*(K+1) with in K+1. So for

k*k < N <=(k+1)*(K+1),

answer would be k+1.

Thus we can answer this one for 1234567345 also :)

[bnashier]

Dear Anuj Bhai:

Let us first get a proof of that:

In a group of 20 people there are either 4 mutual friends or 4 mutual strangers.

For any N, your general answer:

(i) root(N) if N is a perfect square
(ii) {root(N)} + 1, otherwise
seems convincing.

Let us get a formal proof.

Regards,

Budh