Well, duh. After running my Perl program to find the maximum number of cards in which no set can be found, I came to the stunning conclusion: I should've known.

There are 4 traits, and the maximum number of cards that can exist and not produce a set is 2**4, 16.

Here's the proof. Here, the numbers 1, 2, and 4 are octal bits that represent one of the three possible values for each trait.

Set-> ABCDEFGHIJKLMNOP
count 1111111122222222
color 1111222211112222
shade 1122112211221122
shape 1212121212121212
[download]

Read them in columns. Here we have 16 cards (A through P) and there's not a set among them. However, as soon as I introduce a card with any number of 4's anywhere in it, we have a set.

japhy -- Perl and Regex Hacker