combinatorics

Van der Waerden Theorem

Can you color the integers red and blue such that there are no monochromatic arithmetic progressions (AP’s) extending infintely in both directions? Sure — just color zero and all the positive integers red, and all the negative integers blue. Now try coloring just the positive...

Continue reading...

Dinner Party Problem

How many people must you have at dinner to ensure that there are a subset of 3 people who all either mutual acquaintances, or mutual strangers? We can model this using graph theory; for background see the Fun Fact Six Degrees of Separation. Let people be vertices,...

Continue reading...

Continuum Hypothesis

We have seen in the Fun Fact Cantor Diagonalization that the real numbers (the “continuum”) cannot be placed in 1-1 correspondence with the rational numbers. So they form an infinite set of a different “size” than the rationals, which are countable. It is not hard to show that...

Continue reading...

Lucas’ Theorem

Lucas’ Theorem: If p is a prime number, and N has base p representation (aj,…,a1,a0) and k has base p representation (bj,…,b1,b0), then (N CHOOSE k) is congruent [mod p] to(aj CHOOSE bj)…(a1 CHOOSE b1)(a0 CHOOSE b0). Example: Let N = 588, k = 277, p = 5. N...

Continue reading...

Cantor Diagonalization

We have seen in the Fun Fact How many Rationals? that the rational numbers are countable, meaning they have the same cardinality as the set of natural numbers. So are all infinite sets countable? Cantor shocked the world by showing that the real numbers are not countable… there...

Continue reading...

Envy-free Cake Division

Say you and a friend wish to share a cake. What is a “fair” way to split it? Probably you know this solution: one cuts, the other chooses. This is called a fair division algorithm, because by playing a good strategy, each player can guarantee she gets...

Continue reading...

Farmers and Pesky Birds

Alice and Bob are two farmers each wanting to plant a (countably infinite) row of seeds, side by side in a field. Both of them have pesky birds that hinder their efforts in funny ways. As Alice walks along the row, sequentially dropping her seeds,...

Continue reading...

Odd Numbers in Pascal’s Triangle

Pascal’s Triangle┬áhas many surprising patterns and properties. For instance, we can ask: “how many odd numbers are in row N of Pascal’s Triangle?” For rows 0, 1, …, 20, we count: row N: 0 1 2 3 4 5 6 7 8 9 10 11...

Continue reading...

How many Rationals?

How many rational numbers are there? Yes, infinitely many, I hear you say. But how large is that infinity? Are there just as many rational numbers as integers? Well, this requires us to be precise about “just as many”. A mathematician would say that set...

Continue reading...

Dominoes on a Chessboard

A standard 8×8 chessboard can easily be covered (tiled) with non-overlapping dominoes (1×2 pieces): simply use 4 dominoes in each row. But what if we remove two squares—one each from diagonally opposite corners of the chessboard? Can this modified chessboard be completely covered by non...

Continue reading...