Mathematical puzzle

[vovan]

Well, I suppose most of the people here, who like math have heard of the party problem. The very basic case of it poses the following question:

What is the minimum number of people that need to form a group, so that in any combination of acquaintances there would either be a subgroup of at least three mutual friends or three mutual strangers.

As can be easily proven by the pigeonhole principle, the answer to that problem is

Spoiler:

six

. (For those of you who don't know, I put the answer in a spoiler. )

Now, I propose to you a more advanced riddle. Show that for whatever number of mutual acquaintances / strangers we choose, there exists a group with finite number of people, such that in any combination of relations, there is either at least that number of acquaintances or mutual strangers. Put in more formal terms, the question is this:

Show that for any positive integer k, there exists a finite R(k), where
R(k): P -> P
R(k) = minimum n, such that any graph on n vertices has either a k-clique or a k-independent set.

Any takers?

[raghar]

I use computer program to count 2+2. I write it each time and compile it just to have simple program no enter or + or other silly thing that are on calculator.

Could you use less amount of Math terms, and more clear speach?

[reds4ever]

raghar,

you're in a room with 22 other people, what are the odds that at least two of you share the same birthday (not date)?

[Edan]

Originally posted by reds4ever
you're in a room with 22 other people, what are the odds that at least two of you share the same birthday (not date)?

Rhe probability that none have the same birthday is p=(365*364*363*...*344)/(365^^22), so the possibility that one or more have the same birthday are 1-p.

[Ramo]

Show that for any positive integer k, there exists a finite R(k), where
R(k): P -> P
R(k) = minimum n, such that any graph on n vertices has either a k-clique or a k-independent set.

The notation is bugging me : does R(k) map "P" to "P" (the set of all people, presumably) or N (the set of natural numbers) to N? Also, it's slightly irritating when you mention groups when you mean sets (taking algebra right now, so I'm sensitive around the word group).

Anyways, an inductive proof would work best.

The base case is trivial.

As for the inductive step, assume that you can find a set of people (in P?), S, such that all members of a k-sized subset of S, K, are mutually friends or strangers. We have to prove that we can find a set of people, S', such that all members of a k+1-sized subset of S', K', are mutually friends or strangers.

Now, let's construct S'. First add all elements in S to S'. We know that K in S' are either mutually friends or strangers. Suppose that they are mutually friends. Then we need another element in S such that he is friends with everyone in K. If we have such an element in S already, then we add it to K to form K₁', and we are done with the construction. Suppose that they are mutually strangers. Then if there is another element in S that's mutually strangers with all elements in K₁', then we're done.

But suppose that we don't have such an element in S already. Then we can add 2n + 1 sets of n (size of S) more people in P to S'. In each of these sets, there is group of k elements that are either mutually friends or strangers due to the inductive hypothesis. Since we have 2n + 2 sets of mutual friends or strangers, n + 1 of these are sets, K₁', K₂',... K_{n + 1}', of either mutual friends or they sets of mutual strangers.

Let's suppose that these are sets of mutual friends. Then if any of the people in K_n+1', x_n+1, are mutual friends with everyone in K_n', then the union of {x_n+1} with K_j' is a set of k+1 elements of mutual friends, thus the set is constructed and we are done. Suppose not, then for all x_n+1 in K_n+1', x_n+1 is not friends with some element in K_n', x_n. We can apply the same idea with K_n-1'. If some element in K_n-1', x_n-1 is mutual friends with all elements in K_n' or x_n-1 is mutual friends with all elements in K_n+1', we're done. If not, for all x_n in K_n', x_n is not friends with some element in K_{n - 1}', x_{n - 1}; specifically it isn't friends with the aforementioned x_n. Furthermore, it's not mutual friends with x_n+1 for the same reasons. The same idea can continue to K₁'. If a mutual friends hasn't been found by then, we have found a series of n+1 elements that are mutual strangers, {x₁, x₂,..., x_n+1}. Thus we are done as we have found an obviously finite set at most a size of n*(2n + 2).

If the sets are mutual strangers, we can apply similar logic, and construct the S'.

[Nubclear]

Math is incredibly boring.

[Guest]

for 22 people the answer is just under 50% i believe (i seem to remember that 23 is the first integer with above .5 for this one)
the first question is part of ramsey theory, its looking for cliques in graph (put in graph theory term) let me think about it ill get u back on it.

[Guest]

This is a famous problem in Ramsey Theory.
Determining the actual integer is considered one of the hardest computationnal probleme in mathematics.
Even though the ansewr for three is very easy, the one for five is considered almost impossible....

[vovan]

Originally posted by Ramo
The notation is bugging me : does R(k) map "P" to "P" (the set of all people, presumably) or N (the set of natural numbers) to N?

Well, the function cannot map the sets of natural numbers because it wouldn't make sense to compute R(0). Therefore, I say that it maps P to P, as in the set of positive integers to the set of positive integers.

As for the proof itself - very nice, Ramo. It's just one of the possible proofs, of course, but still it's good.

[vovan]

LulThyme, that's right, good ol's Rasmey.

In fact, there is a formula to compute a number that satisfies the given conditions. But it doesn't give the minimum one, just one of the possibilities.

And you are correct: it hase been proven that for groups of three the minimum party size would be six, and for four - 18. But it is believed that for five the number is somewhere between 43 and 49... No definite answer yet.