I am not sure if he would still be willing to pay out, but Vaughan Pratt offers 2000 smackers for the solution to the following:
http://thue.stanford.edu/puzzle.html
Let D be a set of subsets of a set A with the following three properties.
(i) D contains A and the empty set.
(ii) Let C be any set of pairs (a,b), a,b in A, such that for all a in A, the sets {b | (a,b) is in C} and {b | (b,a) is in C} are in D. Then {b | (b,b) is in C} is in D.
(iii) (T1) For any two distinct elements a,b of A, D contains a set containing a but not b, and another containing b but not a.
The set D consisting of all subsets of A evidently satisfies (i)-(iii). Does any other set of subsets of A do so?