Adott 100 piros és 100 kék pont úgy, hogy semelyik 3 nem esik egy egyenesre. Hogyan lehet megmutatni, hogy alkotható belőlük 100 piros-kék pontpár úgy, hogy a párokat összekötő szakaszok nem metszik egymást?

Talán ez egy jó eljárás lehet: két ellentétes színű ponton át húzzunk egy egyenest, ami két részre osztja a síkot. Akkor jó az egyenes, hogyha a két síkrészben a pirosok és a kékek száma megegyezik (például az egyik oldalon 30, a másikon 69 piros és kék pont van). Ez után csak az egyes oldalakon belül húzzuk be a szakaszokat, persze ügyelve a fenti megállapításra, vagyis abban a síkrészben az egyenes (ami valójában csak félegyenes, mivel ha a két egyenes találkozik, azután már nem húzzuk tovább) két olyan részre osztja a pontokat, hogy a részekben ugyanannyi szín van.

Kérdés, hogy hogyan lehet bizonyítani, hogy tetszőlegesen elrendezett pont esetén fog ilyen létezni. Lehet, hogy nem nagy ördöngösség, a bizonyításban sosem voltam jó :)

@4: Nem kell ennyire speciális egyenes.

A négyzetekre osztás ötlete jónak tűnik. Válasszunk ki két négyzetet, amiknek két kék és két piros csúcsa van. Ha a k-p oldalak metszik egymást, akkor hogyan lehet ezt kiküszöbölni? Ha nem, akkor vegyünk egy harmadik négyzetet, és ismételjük a vizsgálatot.

Esetleg indirekt módon. Tegyük fel, hogy van olyan elrendezés, hogy két szakasz mindig metszi egymást. Mi következik ebből? Mik a feltételei?

#5: Négyzetek helyett nyilván négyszögeket akartál írni...

Én nem tudom a kérdéseidre a választ. Te igen?

#1 megoldotta a problémát:

Az eljárás NEM ESHET végtelen ciklusba, ugyanis a szakaszok összhossza minden lépés során csökken (a négyszög két átlójának összege nagyobb, mint két szemközti oldalának összege, háromszög-egyenlőtlenség alapján könnyen bizonyítható).

#4-es is megoldotta a problémát, nicsak...

Bizonyítás, hogy létezik megfelelő egyenes: Veszel egy P pontot, amely semelyik két piros/kék ponttal nincs egy egyenesen. Veszel egy tetszőleges egyenest P-n keresztül, amely nem megy át piros/kék ponton, és annak az egyik oldalán megnézed, mennyivel van több kék pont, mint piros. A válasz egy N egész szám.

Ha N=0, máris nyerés van. Ha N pozitív vagy negatív, akkor elkezded az egyenest P körül forgatni, közben figyeled az N értéket. 180°-ot forgatsz, tehát önmagába érkezik vissza az egyenes. Igen ám, de most már az egyenes másik oldalára vonatkozik az N érték, ahol pont fordított a pontok aránya, vagyis N értéke a 180°-os forgatás során éppen az ellentettjére változott a kiindulási állapothoz képest.

Viszont a forgatás során egyesével jönnek/mennek a piros/kék pontok, tehát N értéke is csak egyesével változhat.

Mármost, ha egy kezdeti N nem nulla értékről 1-esével változik, és végül éppen az ellentettje lesz, akkor közben valamikor át kellett, hogy menjen a 0-n is. Tehát volt olyan P-n keresztülmenő egyenes, amelynek két oldalán ugyanannyi piros és kék pont van éppen. Tehát veszed azt az egyenest, onnantól a #4-es gondolatmenete szerint állítás igaz az egyenes egy-egy oldalára külön-külön (teljes indukció a pontok száma szerint).

Ez a módszer a "söprő egyenes" technika.

(A bizonyításban elrejtettem 1 darab hiányosságot, azt keressétek meg, könnyű javítani.)