Veralgemeende Sylvester-Gallai Stelling

Abstract

Ons gee 'n algoritmiese bewys vir die kontrapositief van die volgende stelling wat onlangs deur die outeurs bewys is: Laat S 'n eindige versameling van punte in die vlak wees, met elke punt rooi, blou of met beide kleure gekleur. Veronderstel dat daar vir enige twee verskillende punte A en B in S wat 'n kleur k deel, 'n derde punt in S is wat (o.a.) die kleur anders as k het en wat saamlynig met A en B is. Dan is al die punte in S saamlynig. Hierdie stelling is 'n gemeenskaplike veralgemening van die Sylvester-Gallai Stelling en die Motzkin-Rabin Stelling. ENGLISH: We give an algorithmic proof for the contrapositive of the following theorem that has recently been proved by the authors: Let S be a finite set of points in the plane, with each point coloured red, blue or with both colours. Suppose that for any two distinct points A and B in S sharing a colour k, there is a third point in S which has (inter alia) the colour different from k and is collinear with A and B. Then all the points in S are collinear. This theorem is a generalization of both the Sylvester-Gallai Theorem and the Motzkin-Rabin Theorem.