#combinatorics

Color every point of the plane so that any two points at distance exactly 1 receive different colors. What is the smallest number of colors for which this is possible? It is known that the answer is 5, 6 or 7. Determine it.

$n$ runners start together on a circular track of length 1 and run forever, each at its own constant speed, with all speeds different. Prove that for each runner there is a moment when every other runner is at distance at least $1/n$ along the track. The speeds $0,1,\dots ,n-1$ show that $1/n$…

A finite family of finite sets is union-closed if the union of any two members is again a member. Prove that every finite union-closed family that contains at least one nonempty set has an element lying in at least half of the sets of the family.

A sorting network on $n$ wires is a fixed sequence of comparators, each of which swaps the values on two wires if they are out of order, such that every possible input comes out sorted. What is the minimum number of comparators in a sorting network for $n=13$ inputs?

Let $f(N)$ be the smallest number such that any $f(N)$ points in the plane, no three on a line, include $N$ points that are the vertices of a convex polygon. Prove or disprove that $f(N)=2^{N-2}+1$ for every $N\ge 3$.

A Hadamard matrix of order $n$ is an $n\times n$ matrix $H$ with entries $\pm 1$ whose rows are mutually orthogonal, so that $H{H}^T=nI$. Such a matrix can exist only if $n$ is 1, 2 or a multiple of 4. Prove that a Hadamard matrix exists for every multiple of 4.

Let $N(a)$ be the number of times the integer $a>1$ appears in Pascal's triangle. For example, $N(3003)=8$. Is there a constant $M$ with $N(a)\le M$ for every $a>1$?

Can the integers $1,2,\dots ,N$ be colored red and blue so that no Pythagorean triple $a^2+b^2=c^2$ has $a$, $b$ and $c$ all the same color? Find the largest $N$ for which this is possible, or show that it is possible for every $N$.

Prove that the regions of any map drawn in the plane can be colored with at most four colors so that any two regions sharing a border of positive length get different colors. Equivalently, prove that every planar graph is 4-colorable.

Keller conjectured in 1930 that in every tiling of ${\mathbb{R}}^n$ by unit cubes, some two cubes share an entire $(n-1)$-dimensional face. For which dimensions $n$ is this true?

A set of points in the plane is in general position if no three lie on a line. An empty hexagon in such a set is a convex hexagon whose vertices are points of the set and which contains no other point of the set. Find the smallest $N$ such that every $N$ points in general position contain an empty…

Let $x_1,x_2,x_3,\dots$ be any infinite sequence with every $x_i$ equal to $+1$ or $-1$. Prove that for every $C$ there are positive integers $k$ and $d$ with $\left|{\sum }_{i=1}^k{x}_{id}\right|>C.$

Königsberg had four land masses, two river banks and two islands. One island was joined to each bank by two bridges, the other island to each bank by one bridge, and a seventh bridge joined the two islands. Is there a walk that crosses every bridge exactly once? More generally, which connected…

A closed knight's tour on an $m\times n$ board is a sequence of knight moves that visits every square exactly once and ends a knight's move away from the starting square. For which $m\le n$ does a closed tour exist? As a first step, prove that none exists when $m$ and $n$ are both odd.

$n$ disks of different sizes are stacked on one of three pegs, largest at the bottom. A move takes the top disk from one peg and places it on another peg, never on top of a smaller disk. What is the minimum number of moves needed to transfer the whole stack to another peg? Prove your answer.

$n$ people numbered $1$ to $n$ stand in a circle. Going around the circle starting from person 1, every second person is removed (first person 2, then 4, and so on, continuing around the circle) until one person remains. Find a formula for the position $J(n)$ of the survivor.

Arrange the numbers $1,1,2,2,\dots ,n,n$ in a row so that for each $k$ exactly $k$ other numbers stand between the two copies of $k$. For $n=3$ the sequence 2, 3, 1, 2, 1, 3 works. For which $n$ is such an arrangement possible?

100 prisoners numbered 1 to 100 face a room with 100 drawers, into which the numbers 1 to 100 have been placed in random order. One at a time, each prisoner enters, opens at most 50 drawers looking for their own number, and leaves the room exactly as it was, with no communication afterwards. All are…

A simple polygon has all of its vertices at points with integer coordinates. It has $i$ integer points in its interior and $b$ integer points on its boundary. Find a formula for its area in terms of $i$ and $b$, and prove it.

Assume birthdays are independent and uniformly distributed over 365 days. What is the smallest number of people for which the probability that at least two of them share a birthday exceeds 1/2?