Chapter 258

How Many Sets Of Cards Can You Find?

The Riddler for March 20, 2020. The Express tracks a price marked down and up by $10\%$ each day. The Classic is three questions about the card game SET: the largest set-free hand, the most sets a board of twelve can hold, and the chance a random twelve contain a set.

Riddler Express

A widget’s price is cut $10\%$ each morning and then raised $10\%$ from the sale price each afternoon. After $N$ days the manager is horrified to find the price more than $50\%$ below the original. What is the smallest $N$ ?

The Riddler, FiveThirtyEight, March 20, 2020(original post)

Solution

A morning cut multiplies the price by $0.9$ ; the afternoon rise multiplies by $1.1$ . One full day is therefore a factor $0.9 \times 1.1 = 0.99,$ not $1$ : the price loses $1\%$ of its value every day. After $N$ days it stands at $0.99^N$ of the original, and we want this below $\tfrac12$ : $0.99^N < \tfrac12 \quad\Longleftrightarrow\quad N > \frac{\ln \tfrac12}{\ln 0.99} = 68.97\ldots$ Since $0.99^{68} = 0.5048$ is still above half and $0.99^{69} = 0.4998$ drops below it, the smallest $N$ is $\boxed{69}.$

The computation

Multiply by $0.99$ each day until the price falls below half.

N = 1
while 0.99**N >= 0.5:
    N += 1
print(N)                                          # 69

The price first drops below $50\%$ on day $69$ , as boxed.

Riddler Classic

In SET, each of $81$ cards has four attributes (number, shape, color, shading), each taking one of three values. Three cards form a “set” if, in every attribute, they are either all alike or all different. (1) What is the largest hand with no set among it? (2) What is the most sets a board of $12$ cards can contain? (3) If you draw $12$ cards at random, what is the probability they contain at least one set?

The Riddler, FiveThirtyEight, March 20, 2020(original post)

Solution

Represent each card as a point $(a,b,c,d)$ with each coordinate in $\{0,1,2\}$ , the four attributes. The “all alike or all different” rule on three cards is exactly the condition that their three values in each coordinate sum to a multiple of $3$ ; that is, three cards form a set precisely when they sum to $(0,0,0,0)$ modulo $3$ , the same as forming a line in this four-dimensional space over the integers mod $3$ . A useful consequence: any two cards lie on exactly one line, so they determine a unique third card completing a set. Hence the deck holds $\binom{81}{2}/3 = 3240/3 = 1080$ sets in all.

(1) Largest set-free hand. A set-free hand is a cap: a set of points containing no line. The maximum cap in this four-dimensional space has size $\boxed{20},$ a fact first proved by Pellegrino in $1971$ and genuinely hard (it rests on real combinatorial-geometry machinery, not case-checking, which is why we cite rather than re-derive it). The computation below exhibits a concrete $20$ -card hand with no set, confirming $20$ is attainable; that it cannot be beaten is the cited theorem.

(2) Most sets in twelve cards. A board of $12$ can be arranged to contain at most $\boxed{14}$ sets, found by local search over boards.

(3) Chance a random twelve contain a set. Drawing $12$ of the $81$ cards uniformly at random, the probability of at least one set is $\boxed{\approx 96.8\%},$ estimated by Monte Carlo. A random hand of twelve almost always contains a set; genuinely set-free hands (caps) are rare.

The computation

Cards are the points of $\{0,1,2\}^4$ ; three form a set when they sum to zero mod $3$ . Count all sets ( $1080$ ); verify a specific $20$ -card hand is set-free; hill-climb for the most sets in a board of $12$ ( $14$ ); and Monte-Carlo the chance a random twelve contain a set ( $\approx 0.968$ ).

import itertools, random
cards = list(itertools.product(range(3), repeat=4))
def is_set(a, b, c): return all((a[i]+b[i]+c[i]) % 3 == 0 for i in range(4))
def count_sets(board):
    return sum(1 for t in itertools.combinations(board, 3) if is_set(*t))

print(count_sets(cards))                          # 1080 total sets in the deck

cap = [(1,1,1,1),(0,1,2,0),(1,0,0,1),(0,2,0,0),(1,2,1,1),(1,2,0,2),(1,1,0,2),
       (0,0,0,2),(2,2,1,0),(2,1,1,2),(1,0,1,2),(2,2,2,1),(0,1,0,2),(2,0,2,1),
       (2,0,1,0),(2,1,0,0),(0,0,2,0),(2,1,2,2),(2,1,0,1),(0,2,2,2)]
print(len(cap), count_sets(cap))                  # 20 0  -> a maximal set-free hand

def max_sets_12(restarts=60, seed=1):
    rng = random.Random(seed); best = 0
    for _ in range(restarts):
        board = rng.sample(cards, 12); cur = count_sets(board); moved = True
        while moved:
            moved = False
            for i in range(12):
                for c in cards:
                    if c in board: continue
                    nb = board[:]; nb[i] = c; v = count_sets(nb)
                    if v > cur: board, cur, moved = nb, v, True
        best = max(best, cur)
    return best
print(max_sets_12())                              # 14

def prob_set(trials=100000, seed=2):
    rng = random.Random(seed)
    return sum(count_sets(rng.sample(cards, 12)) > 0 for _ in range(trials)) / trials
print(round(prob_set(), 3))                       # ~0.968

The deck holds $1080$ sets; the listed $20$ -card hand has none; the most sets in a board of $12$ is $14$ ; and a random twelve contain a set about $96.8\%$ of the time, all as boxed.