A solution to a problem of Grünbaum and Motzkin and of Erdo{double acute}s and Purdy about bichromatic configurations of points in the plane

摘要

Let P be a set of n blue points in the plane, not all on a line. Let R be a set of m red points such that P ∩ R = ? and every line determined by P contains a point from R. We provide an answer to an old problem by Grünbaum and Motzkin [9] and independently by Erdo{double acute}s and Purdy [6] who asked how large must m be in terms of n in such a case? More specifically, both [9] and [6] were looking for the best absolute constant c such that m ≥ cn. We provide an answer to this problem and show that m ≥ (n-1)/3.