Find the smallest number that...
Two seemingly unrelated problems that share a common structure and strategy.
I’m proud of myself for managing to go four weeks without writing a bridge post. That streak ends today, though. Today’s post is a two-parter. First, I’ll show you a problem that was posed at the Lake Norman Bridge Club in Cornelius, NC. Next, I’ll present a classic problem from the early 1900s about friends and strangers at parties. While this might seem like an odd couple, the two problems share a common structure and proof strategy. Let’s jump in.
High-card points
Per my earlier post about bridge, each hand is preceded by an auction in which the two teams bid on how many tricks they think they can take with a given suit as trump. One player on the team that wins the auction becomes the declarer, meaning that they play both their own and their partner’s hands.1 Because of this, it’s really the combined strength of the two hands that matters when determining the appropriate level to play at. The auction is the time when players can describe their hands to their partners (through their bids). In order for this communication to be effective, there needs to be an agreed upon valuation methodology for bridge hands. You can imagine that all the following are valuable for taking tricks.
Lots of high-valued cards (i.e., a strong hand)
Lots of cards in the trump suit
Shortness in suits that aren’t trump (so you can trump leads in those suits)
Long “side suits” for taking lots of tricks once all the trump are out
The primary strategy for hand valuation in bridge is to convert hand features to scalar point values. You then add up all the points in the two hands and compare the total to benchmarks for making particular contracts. For example, 25 points is usually, but not always, sufficient for making a contract of three no trump (3NT). The backbone of the point count method concerns the first bullet, which is how many “good cards” a hand has. High-card points (HCP) are calculated as follows: one point for each jack (J), two points for each queen (Q), three points for each king (K), and four points for each ace (A). Since there are four suits in the deck, the total number of high-card points is 4*(1+2+3+4) = 40. The idea is that the more “honors” you hold, the better your hand is. The method isn’t perfect: I’d rather hold Q-J-10-9-8 than K-5-4-3-2, even though both have three HCP. Nonetheless, it is a successful and widely used point system. We now have enough background to state the question of the day.
Bridge trivia question
Assuming that you can arrange the 52 cards however you want, what is the smallest number of high-card points you can have and still take all 13 tricks (also known as a “grand slam”)?
To clarify, the premise is that you can take the 52 cards and put them in whichever hands you want (provided that each hand has 13 cards). I’ll also stipulate that this a suit contract, meaning that there is a trump suit. (In no trump contracts, you generally need more high-card points to make the same number of tricks.) For concreteness, let’s say that the trump suit is clubs. One challenge with a problem like this is that you have to prove two things:
You can make a grand slam with x high-card points.
If y < x, then you can’t make a grand slam with y high-card points.
This type of problem arises frequently in math, which is partially why you see some conjectures hang around for centuries before getting resolved (if ever). We’ll come back to that in the next section. To answer the bridge question, I’ll try to converge on the answer by bounding it from above and below and gradually improving those bounds.
For starters, suppose that you had all 13 clubs in your hand. With clubs as the trump suit, you’ll take every trick, regardless of the cards in the other three hands. (Don’t hold your breath for this hand, by the way.) That hand has 10 HCP: one A, one K, one Q, and one J. This means that the answer is no bigger than 10. On the flip side, the ace of trump wins any trick in which it is played. In order to make a grand slam, you must therefore have the ace of trump, meaning that your hand has at least 4 points.
It turns out that 4 HCP is insufficient. If you have 4 HCP, then you’re missing the KQJ of trump. By playing the ace of trump, you can eliminate 2 of the 3 if they’re in opposing hands. However, one hand must have at least two honors, and the remaining one will be the top card left after the ace is played. This is a consequence of the “pigeonhole principle” (future post alert). This tells us that you must have at least 5 HCP to make a grand slam. I’ll finish the proof by producing a grand slam hand with 5 HCP.
If you have 5 HCP, then your opponents have 35, which is to say that they have almost all the good cards. The only way you can possibly take 13 tricks is if you can trump any card that’s led. You also don’t want to lead trump; if you lead it, then dummy is obligated to follow suit, which means you’ll expend your trump twice as fast. This means you’ll have to employ a strategy called cross-ruffing, which is where you keep leading cards from both hands that the other hand can trump. Thus, each of your hand and dummy’s hand will be roughly half trump and half low cards in another suit. Without further ado, here are the hands where the pair with five combined HCP will make a grand slam, regardless of the lead by the opposition.
Let’s say that South is the declarer, which means that West leads (into the dummy, North). West can lead any of the four suits. If West leads a club—not a terrible choice if the declarer is planning to cross-ruff, since it takes two trump off the board—South will take the trick with the ace of clubs. South will return a spade, which North trumps. North and South will then cross-ruff leads of red cards (North) and spades (South). After South plays the fourth spade, East will be out of spades, which means that remaining 3 spades will be good and don’t need to be trumped. If you’re keeping track at home, that means North-South wins 10 tricks with trump and three with spades for a total of 13. If West leads a red card instead, South trumps trick one, then plays the ace of clubs to void East-West of trump. North-South then cross-ruffs as before. Finally, if West leads a spade, North trumps the first trick. They then lead a club to South’s ace to clear the trump before resuming the cross-ruff. In the last case, North uses a trump on the first trick, but that’s okay because East is forced to play a spade. (Of the five trump in North’s hands, one is spent on drawing East-West’s trumps, and the other four must cover the spades in East’s hand.
Friends and strangers at parties
I want to switch gears now to a slightly more practical application of the same line of reasoning. Here’s the new problem:
At a minimum, how many people must attend a party for it to be guaranteed that at least three of them are mutual friends or mutual strangers?
Three mutual friends (respectively, strangers) are three people, each of whom knows (respectively, doesn’t know) the other two. Why is the line of reasoning the same as bridge? In each case, you need to find a positive integer that is the smallest number satisfying some condition. For bridge, we wanted the smallest number of high-card points you could have and still make a grand slam. Now, we want to know the smallest party size that guarantees the existence of three mutual friends or mutual strangers.
As before, I’m going to approach this problem from above and below and see if I can land on the answer. Let’s start with small parties first. This is the easier case because 1) the numbers are smaller, and 2) we only have to produce once example of a party that lacks three mutual friends or mutual strangers. If three people attend, it’s possible that two people know each other, but the third is a stranger to the other two. Such a party only has two mutual friends (or strangers), so the answer is bigger than three. What about a party with four attendees? Let’s call them A, B, C, and D. Suppose that A and B are friends and that C and D are friends, but that neither A nor B knows either C or D. Again, it’s only possible to find two mutual friends or two mutual strangers at this party.
A party with five people is a little more complicated. To analyze this case, I will use a graph to demonstrate a party of five without three mutual friends or strangers. The nodes in the graph are the five attendees: A, B, C, D, and E. Edges denote friendship, thus the absence of an edge indicates that the two nodes are strangers. This means that a set of three friends is a triangle in the graph (cf., picture below).2 Suppose the five attendees are seated at a round table, and that each person is friends only with the two people seated on either side of them. The two friends of any attendee are not seated next to each other, thus they are not friends. This proves that there is no set of three mutual friends. On the other hand, the two people that a given attendee does not know are seated next to each other and hence are friends. This proves that there is no set of three mutual strangers.
If we try the same trick with six attendees, the argument breaks down. In that case, each person has three strangers (i.e., nonadjacent nodes), and two of those three have a seat between them at the table, meaning that they’re also strangers. This yields a set of three mutual strangers. While this doesn’t prove that any party of six must have three mutual friends or mutual strangers, it does suggest that we might want to start thinking about a proof, rather than looking for a counterexample.
To that end, add F to the party to give us six attendees. Pick any attendee (let’s say A) and consider their relationship with the other five attendees. Since each person is either a friend or stranger to A, there must be at least three A-friends or A-strangers. (Coo! Coo!) Assume that there are at least three A-friends. (The ensuing argument is easy to adapt to the case where there are three or more A-strangers.) Now, one of two things is possible. Either no one knows each other in the group of A-friends, or at least two people are friends in the group of A-friends. In the first case, we can take any three people from the set of A-friends to create a set of three mutual strangers. In the second case, suppose that B and C are friends in the set of A-friends. (It could be any two people.) Then {A, B, C} forms a set of three mutual friends, since B and C are A-friends by construction. Since those two cases are exhaustive, we can conclude that this party of six must have a group of three mutual friends or three mutual strangers. We didn’t make any other assumptions about the party, so the same would be true for any party of six people.
The party problem is a basic example from a branch of mathematics called Ramsey theory. Ramsey theory is in the area of combinatorics, which is the field of math devoted to counting stuff. The typical result in Ramsey theory asserts that there is structure hiding inside an object, as long as that object is big enough. This is actually an intensely difficult field about which I know next to nothing. To give you an idea of the difficulty, you need 18 attendees at a party to guarantee at least four mutual friends or strangers. How many attendees do you need to guarantee five mutual friends or strangers? No one knows the answer. We know it’s between 43 and 48, but, as a species, we are yet to nail it down. It’s common to write R(n) for the answer to the party problem with n mutual friends/strangers. (i.e., R(3) = 6, R(4) = 18, etc.) Paul Erdos, the most prolific mathematician of the 20th century, once said (paraphrasing):3
If aliens invaded the earth and threatened to obliterate it within a year’s time unless human beings can find R(5), we could marshal the world’s best minds and computers and probably compute the value. If they demanded R(6), we would have no choice but to launch a preemptive strike.
I mentioned that Erdos was prolific. Have you heard of six degrees of Kevin Bacon? The source of this idea was Erdos, except with movie connections replaced with publications. For example, my Erdos number is 4: I coauthored a paper with someone who coauthored a paper with someone who coauthored a paper with Erdos. All told, he published about 1,500 papers, mostly while couch surfing. Pretty amazing.
Thank you for reading today, and Happy 4th. If you enjoyed this or any earlier posts, please share with others who may enjoy it too.
The declarer is the first person on the team that wins the auction who mentions the suit that ultimately becomes trump (including no trump).
It’s more common to state these problems with red and blue edges for friends and strangers respectively, as opposed to edges and lack of edges. When you have more nodes, it can be harder to “see” the absence of an edge.
"Ramsey Theory" by Ronald L. Graham and Joel H. Spencer, in Scientific American (July 1990), p. 112-117