MathDB

Alice, who works for the Graph County Electric Works, is commissioned to wire the newly erected utility poles in

k

days. Each day she either chooses a pole and runs wires from it to as many poles as she wishes, or chooses at most

17

pairs of poles and runs wires between each pair. Bob, who works for the Graph County Paint Works, claims that, no matter how many poles there are and how Alice connects them, all the poles can be painted using not more than

2009

colors in such a way that no pair of poles connected by a wire is the same color. Determine the greatest value of

k

for which Bob's claim is valid.

Problem Statement