Thread Tools
Old February 3, 2003, 19:44   #1
vovan
Apolyton UniversityCivilization IV CreatorsSporeApolyton Storywriters' GuildC3CDG Blood Oath HordeC4DG The Horde
Emperor
 
vovan's Avatar
 
Local Time: 09:40
Local Date: November 1, 2010
Join Date: Oct 2001
Posts: 5,725
Mathematical puzzle
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?
__________________
XBox Live: VovanSim
xbox.com (login required)
Halo 3 Service Record (I fail at FPS...)
Spore page
vovan is offline  
Old February 3, 2003, 20:45   #2
raghar
Chieftain
 
Local Time: 15:40
Local Date: November 1, 2010
Join Date: Oct 2002
Location: I wish somewhere else.
Posts: 34
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?
raghar is offline  
Old February 3, 2003, 21:14   #3
reds4ever
Prince
 
reds4ever's Avatar
 
Local Time: 16:40
Local Date: November 1, 2010
Join Date: Mar 2001
Location: of the Spion Kop
Posts: 861
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)?
reds4ever is offline  
Old February 3, 2003, 23:07   #4
Edan
Warlord
 
Edan's Avatar
 
Local Time: 11:40
Local Date: November 1, 2010
Join Date: Dec 2002
Posts: 234
Quote:
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.
Edan is offline  
Old February 4, 2003, 03:14   #5
Ramo
Apolytoners Hall of Fame
Emperor
 
Ramo's Avatar
 
Local Time: 10:40
Local Date: November 1, 2010
Join Date: Oct 1999
Location: of Fear and Oil
Posts: 5,892
Quote:
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 K1', 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 K1', 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, K1', K2',... Kn + 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 Kn+1', xn+1, are mutual friends with everyone in Kn', then the union of {xn+1} with Kj' is a set of k+1 elements of mutual friends, thus the set is constructed and we are done. Suppose not, then for all xn+1 in Kn+1', xn+1 is not friends with some element in Kn', xn. We can apply the same idea with Kn-1'. If some element in Kn-1', xn-1 is mutual friends with all elements in Kn' or xn-1 is mutual friends with all elements in Kn+1', we're done. If not, for all xn in Kn', xn is not friends with some element in Kn - 1', xn - 1; specifically it isn't friends with the aforementioned xn. Furthermore, it's not mutual friends with xn+1 for the same reasons. The same idea can continue to K1'. If a mutual friends hasn't been found by then, we have found a series of n+1 elements that are mutual strangers, {x1, x2,..., xn+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'.
__________________
"Beware of the man who works hard to learn something, learns it, and finds himself no wiser than before. He is full of murderous resentment of people who are ignorant without having come by their ignorance the hard way. "
-Bokonon
Ramo is offline  
Old February 4, 2003, 04:10   #6
Nubclear
NationStatesCall to Power II Democracy GameInterSite Democracy Game: Apolyton TeamRise of Nations MultiplayerACDG The Human HiveNever Ending StoriesACDG The Free DronesACDG The Cybernetic ConsciousnessGalCiv Apolyton EmpireACDG3 SpartansC4DG Team Alpha CentauriansCiv4 SP Democracy GameDiplomacyAlpha Centauri PBEMCivilization IV PBEMAlpha Centauri Democracy GameACDG Peace
PolyCast Thread Necromancer
 
Nubclear's Avatar
 
Local Time: 15:40
Local Date: November 1, 2010
Join Date: Jul 2002
Location: We are all Asher now.
Posts: 1,437
Math is incredibly boring.
Nubclear is offline  
Old February 4, 2003, 09:02   #7
LulThyme
Guest
 
Posts: n/a
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.
 
Old February 4, 2003, 09:29   #8
LulThyme
Guest
 
Posts: n/a
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....
 
Old February 4, 2003, 11:25   #9
vovan
Apolyton UniversityCivilization IV CreatorsSporeApolyton Storywriters' GuildC3CDG Blood Oath HordeC4DG The Horde
Emperor
 
vovan's Avatar
 
Local Time: 09:40
Local Date: November 1, 2010
Join Date: Oct 2001
Posts: 5,725
Quote:
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.
__________________
XBox Live: VovanSim
xbox.com (login required)
Halo 3 Service Record (I fail at FPS...)
Spore page

Last edited by vovan; February 4, 2003 at 11:41.
vovan is offline  
Old February 4, 2003, 11:46   #10
vovan
Apolyton UniversityCivilization IV CreatorsSporeApolyton Storywriters' GuildC3CDG Blood Oath HordeC4DG The Horde
Emperor
 
vovan's Avatar
 
Local Time: 09:40
Local Date: November 1, 2010
Join Date: Oct 2001
Posts: 5,725
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.
__________________
XBox Live: VovanSim
xbox.com (login required)
Halo 3 Service Record (I fail at FPS...)
Spore page
vovan is offline  
 

Bookmarks

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is On

Forum Jump


All times are GMT -4. The time now is 11:40.


Design by Vjacheslav Trushkin, color scheme by ColorizeIt!.
Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
Apolyton Civilization Site | Copyright © The Apolyton Team