[17] Let w(n) be the largest integer such that for every tournament T on N = {1,...,n} there exist disjoint sets A and B, each of cardinality w(n), in N such that A × B ⊆ T . Prove w(n) ≤ 2log n.

Comments. Hint: add 2w(n)log n bits to describe nodes, and save w(n)2 bits on edges. Source of the problem: [P. Erd˝os and J.H. Spencer, Probabilistic Methods in Combinatorics, Academic Press, 1974].