7.01a–7.01c - Problem types, sets and pigeonholes

Four types of problem

If you choose any $17$ different integers from $1$ to $32$, must two of your choices add to $33$? Try choosing awkwardly: all the small numbers, all the odd numbers, or numbers scattered across the interval. A systematic argument will settle every possible choice at once.

Before solving a problem, identify what its answer must look like. “Can it be done?” and “How many ways?” may describe the same setting but demand different answers.

For a seating problem, these questions are different.

A problem can belong to more than one category. “Find a shortest route” asks you both to construct a route and to optimise its length. A valid construction proves existence, but it does not count all solutions or prove that yours is best. Conversely, proving existence need not tell you where the solution is: that is precisely what our opening puzzle will illustrate.

The distinction changes the last line of your answer: a count cannot replace a requested construction, and one successful example cannot establish an optimum.

Describing sets and their elements

A set records which objects are present, without giving those objects an order or counting an object twice.

Thus $\{2, 5, 2\}$ is the same set as $\{5, 2\}$. Repeating $2$ in a written list does not create a new element. The braces matter: $2$ is a number, whereas $\{2\}$ is a set containing that number.

Choose a universal set $\mathcal{E}$ containing every object under discussion. Then the following operations describe new sets.

Two sets are disjoint when their intersection is empty. Notice that $\varnothing$ is a subset of every set: there is no element in it that could fail the subset condition. However, $\varnothing$ and $\{\varnothing\}$ differ: their sizes are $0$ and $1$.

[DIAGRAM: asset_name: Set operations in a finite universal set; asset_slug: h245_7_01_sets; caption: Each integer from 1 to 12 occupies exactly one region, determined by membership of the even numbers A and the multiples of 3 B; description: A rectangular universal set contains two overlapping circles labelled A even numbers and B multiples of 3. The A-only region contains 2, 4, 8, 10; the overlap contains 6, 12; the B-only region contains 3, 9; the region outside both contains 1, 5, 7, 11. A lower key describes union as all three circle regions, intersection as the overlap, and complement of A as everything outside A]

Work with actual elements before trying to count regions. This avoids counting an element twice just because it satisfies two descriptions.

The next example changes only the universal set. This matters because complements depend on the universe, even when the named sets do not change.

Sets of elements and individual elements require different notation.

For a complement, state or read the universal set before listing anything.

Partitions of a set

A partition divides a set into groups so that every element belongs to exactly one group.

For $S=\{a,b,c\}$, the groups $\{a,b\}$ and $\{c\}$ form a partition. The groups $\{a,b\}$ and $\{b,c\}$ do not, because $b$ is used twice. The one-block collection $\{S\}$ is a partition; so is the collection of three singleton groups.

This last point makes counting partitions different from placing people into named teams. A red team and a blue team are labelled; the two blocks of a partition are not. For small sets, organise an exhaustive list by block sizes rather than inventing a formula. No general formula for counting partitions is in the formula booklet.

[DIAGRAM: asset_name: All partitions of a three-element set; asset_slug: h245_7_01_partitions; caption: The five partitions of a three-element set are organised by their block sizes, and reversing the order of the blocks creates no new partition; description: Three horizontal panels show the one partition with a block of size 3, the three partitions with block sizes 2 and 1, and the one partition with three singleton blocks. Elements a, b, c appear once in every displayed partition, enclosed together in pale rounded rectangles exactly when they belong to the same block]

The picture gives a useful surprising count: a set of only three elements already has five partitions. Each element is used once in every row, but the group boundaries change.

The next example adds only the restriction that the two blocks must have equal size. Their order still creates no extra partitions.

A constraint about two named elements can be applied directly to this list.

When blocks have different sizes, their sizes can distinguish them; when sizes coincide, fixing one named element is often the cleanest way to avoid duplicates.