BY. Guests at a Party
A short, but tricky puzzle: how many guests must you invite before you can be sure that there are at least three mutual acquaintances or three mutual strangers?
2 Comments »
RSS feed for comments on this post · TrackBack URL
Leave a Comment
You must be logged in to post a comment.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Karen Appleby said,
June 16, 2009 at 1:46 pm
Hi: I have only recently discovered The Math Factor on Itunes, so I am w-a-y behind the present — I’m only up to problem CA. But, I keep hearing you say, “send us an e-mail”, so I thought I would (of course I’m aware it’s possible that in the current podcasts, you don’t say that — I feel a bit like a stargazer in that what I’m hearing now left Arkansas two years ago).
I wanted to comment on two issues: this one (Ramsey numbers) and AO — choosing balls from a bag with a 50% of pulling four blue ones. First, AO. It’s been a couple weeks since I heard that one and the answer (8 balls) has been bothering me all that time — it made absolutely no sense to me, as somehow I was thinking that the rest of the “n” balls were not blue, and I knew that there were many, many ways to not get four blue ones if half of them weren’t blue!. Twice I started to write you to see if I could get some clarification and twice I thought, “I wonder if it means “x”, and FINALLY yesterday I had enough sense to brush up on my probability theory, and experiment with various combinations. So — now I’m thinking that the answer is: 8 balls, and seven are blue. It also seems improbable to me that you need that many to approach a 50% chance of drawing four blue, but at least I have a mathematical formula that backs it up. So the point of this comment is: it was great to have a problem like that to mull over and it was great to be able to use relatively simple math to finally understand it.
Now, on to the Ramsey numbers. When Chaim said that we didn’t know what the number was for R(5,5) but it was between 43 and 49, I thought, “how can you possibly not know the answer to a problem with such low numbers as upper and lower bounds?”. Which drove me to the web and now I know. It’s mind-blowing! So, the point of this comment is: this is why I really like the show — normally I can actually understand the mathematical issues (I have a highly deficient math background — no problem involving trigonometry or calculus need apply — occasionally I muse that people who lived 2,000 years ago knew more math than me) — and the puzzles are straightforward enough to keep all the factors in mind so I can think about them at odd moments. Many thanks to Kyle for carefully restating them every week!
Looking forward to joining you folks in “real-time” when I catch up. Thanks for making this available to the audience beyond “Ozarks at large”.
Karen
strauss said,
July 1, 2010 at 9:04 am
Tom G wrote us:
I was listening to one of your podcasts where you were talking about people at a party and what the minimum amount of people it took to have a triangle of either friends or strangers. It made me think about all the different combinations that people at a party would be friends and strangers. How can I figure out how many combinations there would be for a given number of people?
To which we replied:
It depends a little bit on whether we’re asking for friendships between
specific people or for overall patterns of friendships.
For example, suppose we have three people, Alice, Bob and Cynthia.
If we just want patterns, there are exactly four possibilities:
No one is friends with anyone else.
One pair is friends with each other, third person friends with no one.
One person is friends with both the others, but they’re not friends with
each other.
Everyone is friends.
If we want friendships between specific people, there are 8 possibilities.
XY means X and Y are friends:
No one is friends
AB
BC
CA
AB, BC
AB, AC
BC, AC
AB, BC, AC
So, first, we have to decide which question we’re asking!
If we’re interested in specific friendships, the answer is really easy:
among n people, there are exactly n(n-1)/2 pairs (lots of ways to show that)
and each pair is either friends or strangers– 2 possibilities. So the total
number of possibilities is 2^(n(n-1)/2)
If we’re interested in ‘patterns’ it’s a lot trickier and a lot more
interesting. To relate this to something better known, draw a dot for each
person and a line between dots if the people know each other. What we’re
looking at is a ‘graph’ with n ‘vertices’; the graph is ‘simple’ because
there’s at most one edge between any pair of vertices and there aren’t any
loops; the graph might not be ‘connected’ because it might not all be in one
piece; the graph is ‘unlabled’ since we’re looking at the pattern, not
caring which individuals particularly are the ones who are friends.
So what we’re asking for is: How many simple (but not necessarily connected)
unlabeled graphs are there on n vertices.
This is a pretty rich area that I’m not too familiar with, but here’s a list
of the first few values and many many links outwards from there.
http://www.research.att.com/~njas/sequences/A000088