Too long to wait

This is a straightforward implementation to determine the Ramsey number $R(5,5)$ ; that is, the smallest positive integer $n$ such that no matter how the edges of the complete graph $K_n$ with $n$ vertices is colored with two colors, there exists five vertices whose edge between any two of them is colored by the same color. (This latter portion is called a monochromatic clique of size $5$ .)

To see how this implementation works, observe the following:

• n is the number of vertices in the graph; we will keep incrementing this value until we find the solution.
• f is a Boolean variable indicating whether we have found the value of n . Initially, for $n=4$ , clearly the answer is false; there are not even enough vertices.
• The while not f loop iterates until we find the value of n . At the beginning, we set f to be true and increment the value of n ; we will toggle f back to false when we find a counterexample, indicating that we need to continue to look for the value of n .
• Our graph has vertices labelled $0,1,2,\ldots,n-1$ . This is not written explicitly in the code, but is visible from the next line.
• e is the list of edges in our graph. The line e = [(i,j) for i in range(n) for j in range(i+1,n)] declares the edges.
• The double loop for k in range(len(e)+1): for b in itertools.combinations(e, k) is a well-known method to loop over all possible subsets b of e .
• c is a dictionary mapping each edge to its color ( $1$ or $2$ ).
• g is a Boolean variable indicating whether we have found the clique in the graph. Initially this is false.; we toggle this true once we find the clique (third line from bottom).
• The for i in e loop simply assigns the colors; b is the list of edges that are colored "blue" (color $2$ ), and the rest is the list of edges that are colored "red" (color $1$ ).
• for v in itertools.combinations(range(n), 5) iterates over all $5$ -element subset of the vertices. This is the vertices that we want to test, whether the edges between them are colored the same.
• a = c[(v[0], v[1])] takes the color of the first edge. Since itertools.combinations retains the order of elements in the iterable, in this case range(n) , and range(n) returns the vertices in increasing order, we are guaranteed that 0 <= v[0] < v[1] < n and thus c[(v[0], v[1])] is defined.
• for i in v: for j in v is a double loop that loops over all pairs of elements in v , not necessarily different. However, if i < j: afterwards forces the first element to be less than the second element.
• if c[(i, j)] != a: a = 0 changes the sought color to a non-existent color if the edge inspected is incorrect, indicating failure for the current set of vertices.
• if a: g = True states that this graph is correct; we just found the clique.
• if not g: f = False states that this value of n is incorrect; we just found a counterexample where there is no monochromatic clique.
• print((n-1)//7) is the only print statement in the problem; upon getting the value of n , we put this to the weird-looking function (n-1)//7 and print its value.

Now that we know the program computes the Ramsey number $R(5,5)$ , we need to figure out its value... but unfortunately, this implementation will take a very long time to finish. We have to look for help.

The given Wikipedia article above states that $43 \le R(5,5) \le 49$ , at the time of posting of this problem. Surprisingly, every value from $43$ to $49$ gives the same value when fed to the function $n \mapsto \left\lfloor \frac{n-1}{7} \right\rfloor$ ; all of them returns $\boxed{6}$ . This is our answer.

---

This problem is inspired from Halting Problem , a puzzle in MIT Mystery Hunt 2013.