The Joy of Set: Hint 2

Edit: Clearly there's something wrong here: http://www.math.rutgers.edu/~maclagan/papers/set.pdf calculates that you can have 20 Set cards in-play without forming a Set...what's worse, it provides a counterexample to my calculation that you're guaranteed a Set at 14 or more cards.

So what's my mistake below? Simple: a single card may complete more than one Set, and I didn't take that into account. The rest of this post stands as a testament to the human need to simplify, the difficulty of problems in combinatorics and the addictive nature of writing posts with mathematical equations.

---

What is the largest number of Set cards that can be in play without having a set present?

We saw in hint 1 that given two Set cards, exactly one card will complete a Set. So for any \(n\)-card Set board containing zero sets, it means we don't have any of the \(\binom{n}{2}\) cards that would complete our set. Since the problem assumes that no Sets have been called, those cards are all hiding in the deck, out of play.

The possible largest \(n\), then, for which we can have n Set cards in play out of the 4³ = 81 without a Set is the greatest integer \(n\) for which \(\binom{n}{2} \le 81 - n\):

\[\binom{n}{2} \le 81 - n\]
\[\frac{n!}{2!(n-2)!} \le 81 - n\]
\[n(n-1) \le 162 - 2n\]
\[n^2 + n - 162 \le 0\]
Testing near the following values of \(n\):
\[-1 \pm \sqrt{649} \over 2\]
Well, really just \(-1 + \sqrt{649} \over 2\), since a negative number of Set cards in play is nonsensical:
\[\frac{-1 + \sqrt{649}}{2} \approx 12.24\]

\(n\) needs to be a whole number. Since \(n^2 + n - 162\) needs to be less than or equal to zero, we'll take the floor for \(n = 12\). Let's check our work:
\[\binom{12}{2} \le 81 - 12\]
\[\frac{12 \cdot 11}{2} \le 69\]
\[66 \le 69\]
checks out. Pushing \(n\) up to 13 doesn't seem promising:
\[\binom{13}{2} \le 81 - 13\]
\[\frac{13 \cdot 12}{2} \le 68\]
\[78 \not{\le} 68\]

Since \(n = 12\) is our last chance to have a board with zero sets, it's tempting to say \(p(n) = 1\) for \(n \ge 13\). This actually isn't the case. Let's look at our interpretation a little closer and go back to the beginning just for a moment:

Since there is exactly one card which will complete a Set from a pair of Set cards, we need all of those \(\binom{n}{2}\) cards to be hiding in the deck. When there are 12 cards in play, the deck has 69 cards in it, and only 66 of those cards are refugee Set-completers. This means that from what's left in the deck, we have three choices for our 13^th card which will not complete the set! The fact that there aren't enough hiding spots in the deck for Set-completing refugees at \(n = 13\) actually means that \(p(14) = 1\). The fact that there are three extra hiding spots for the 66 Set-completers at \(n = 12\) just means that from a board with 12 cards and zero sets we have a \(\frac{3}{66} = \frac{1}{22}\) chance of making it to 13 without a Set. This segues nicely into Hint 3....

\(n\)	\(p(n)\)
0	0
1	0
2	0
3-12	No spoilers!
13	allllmost 1 (not fair, I've already worked out the full answer)
\(\ge 14\)	1