Partitions of a Set

Try this

$n = 4$ : split $1, 2, 3, 4$ into two classes so that no class contains $x, y, x + y$ ( $x = y$ counts too, e.g. $1, 1, 2$ ). Did you manage it?
Set $n$ to $5$ and try again. If several attempts fail, tap “Ask the computer”.
Read the “Addition principle” meter below: however you color, what do the class sizes add up to?
How many successful colorings are there in all? Does swapping the two colors give a new partition?

If a set $M$ is the union of non-empty subsets $A_{1}, A_{2}, \dots, A_{n}$ that are pairwise disjoint:

A_{i} \cap A_{j} = \emptyset (i \neq = j), A_{1} \cup A_{2} \cup \dots \cup A_{n} = M,

then ${A_{1}, \dots, A_{n}}$ is called an $n$ -partition of $M$ . The most direct consequence is the addition principle: $∣ M ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ + \dots + ∣ A_{n} ∣$ .

The handiest way to think of a partition is as a coloring: everything in one piece gets the same color. “Can it be partitioned as required?” becomes “Can it be colored as required?”

Predict first

In how many ways can ${1, 2, 3, 4}$ be split into two pieces (unordered, each non-empty)?

ways

Choose an answer first; then you can see the result.

Why 5 numbers cannot escape

{1,2,3,4,5} cannot be split into two pieces that both avoid x+y=z

Step 1 / 5

Start with 1, without loss of generality
Suppose a valid split exists. The two colors play the same role, so without loss of generality $1$ is in the first class (●).
2 is pushed out
4 is pushed out
3 and 5 are both forced into the second class
Contradiction

“Without loss of generality” and “forced” are the two key phrases in proofs like this: symmetry halves the case work, and each step leaves only one choice, so the argument ends in a few moves. ${1, 2, 3, 4}$ , on the other hand, can be split: ${1, 4}$ and ${2, 3}$ . Between $4$ and $5$ lies the border between “possible” and “impossible”.

Another restriction: equal sums

Now split into $3$ pieces so that every piece has the same sum. Before you start, think: what must the total $1 + 2 + \dots + n$ satisfy?

For

n = 8

the total is

36

. What should each piece add up to? Set

n

7

and tap “Ask the computer” again.

A total divisible by $3$ is necessary, but it is not enough: for $n = 3$ the total is $6$ , so each piece should be $2$ , yet $3$ on its own is already too big. A necessary condition rules out a lot of cases; the ones that remain have to be settled one by one with a construction.

Practice

Exercise 1Basic

In how many ways can ${1, 2, 3, 4, 5}$ be split into two pieces (unordered, each non-empty)?

Exercise 2Basic

For which $n$ among $1, 2, \dots, 10$ can ${1, 2, \dots, n}$ be split into two pieces with equal sums? (List all such $n$ , separated by commas.)

Exercise 3Advanced

In how many ways can ${1, 2, 3, 4, 5}$ be split into three pieces (unordered, each non-empty)?

Exercise 4Challenge

For which $n$ among $1, 2, \dots, 12$ can ${1, 2, \dots, n}$ be split into three pieces with equal sums?

Try this

Why 5 numbers cannot escape

{1,2,3,4,5} cannot be split into two pieces that both avoid x+y=z

Another restriction: equal sums

Practice

Mistake Museum · Exhibits from this stop

Counting an empty piece when counting partitions

Adding pieces that overlap