15. FEJEZET: Kombinatorikus geometria
Ez a fejezet még fejlesztés alatt áll.
Ide tartozó feladatok más fejezetekből:
a
11.1.,
11.4.,
11.10.,
11.15.,
13.11.,
13.12.,
13.13.,
13.14.,
13.16.,
13.18.,
13.20.,
13.23.,
13.24.,
13.25.,
13.26., feladatok; továbbá a
17.1.,
17.2.,
18.18., feladatok.
Általános feladatok
Feladat: 15.1. (M)
Adott a síkon két véges ponthalmaz,
S és
T. Megadhatók-e olyan párhuzamos egyenesek, amelyek
S minden pontját lefedik, de
T egyetlen pontját sem fedik le?
Feladat: 15.2.
Kutató munka:
Milyen véges síkbeli ponthalmazokra igaz, hogy feloszthatók két részre úgy, hogy a két rész pontjait nem lehet egyenessel szétválasztani? (Vö. [
33]. 8. feladat.)
Egy egyenesről akkor mondjuk, hogy elválasztja a két részt, ha az egyik rész pontjai az egyenes egyik oldalán vannak, a másik rész pontjai az egyenes másik oldalán vannak.
Feladat: 15.3.
[
176]
Négy félsík úgy helyezkedik el egy síkban, hogy együttesen az egész síkot lefedik, azaz a síknak mindegyik pontja legalább az egyik félsíknak belső pontja. Bizonyítandó, hogy a négy félsík közül kiválasztható három úgy, hogy e három félsík is lefedi együttesen az egész síkot. (Kürschák-verseny, 1951.)
Feladat: 15.4. (M)
Adott véges sok fehérre és véges sok feketére színezett pont a síkon. Mindkét színűből legalább három van. A pontok közül semelyik három nincs egy egyenesen. Tudjuk továbbá, hogy bármely négy pont közül a fehérek és a feketék egy egyenessel szétválaszthatók. Bizonyítandó, hogy az összes fekete pont elválasztható egy egyenessel az összes fehér ponttól. (Ki miben tudós? 1984)
Egy egyenesről akkor mondjuk, hogy elválaszt két ponthalmazt, ha az egyik ponthalmaz az egyenes egyik oldalán van, a másik ponthalmaz az egyenes másik oldalán van.
Feladat: 15.5. (SM)
* Adott a síkon
n darab általános helyzetű pont. Bizonyítsuk be, hogy összeköthetők egy önmagát nem metsző zárt törött vonallal! (Arany Dániel-verseny 2001H)
Feladat: 15.6. (M)
a) Mutassuk meg, hogy minden
n>2 egész számra megadható
n elemű ponthalmaz a síkon, amelynek pontosan
n átmérője van.
b) * Bizonyítsuk be, hogy egy
n pontból álló síkbeli ponthalmaznak legfeljebb
n darab átmérője lehet. (IMO 1965/6, [
183])
Feladat: 15.7.
[
187]. Book 2.
Kutató munka:
Kiszínezhetők-e a sík rácspontjai három színnel úgy, hogy
a) minden színhez végtelen sok olyan, az
x-tengellyel párhuzamos egyenes legyen, amelyen e szín végtelen sokszor fordul elő,
b) ha három pont egy egyenesen van, akkor legyen köztük két azonos színű?
Feladat: 15.8.
Kutató munka:
Adott véges sok általános helyzetű egyenes a síkon. Az általuk meghatározott tartományokat akarjuk két színnel kiszínezni úgy, hogy azonos színű tartományoknak ne legyen közös határvonala (vagyis közös egyenes szakasza, csúcsban érintkezhetnek). Van-e olyan helyzete az egyeneseknek, amikor ez nem lehetséges?
Feladat: 15.9.
Kutató munka:
Adott
n pont a síkon, semelyik kettő távolsága nem egyenlő. Mindegyiket összekötjük a hozzá legközelebbivel. Minimálisan hány szakaszt kell így behúznunk?
És maximálisan?
Mit mondhatunk az így kapott alakzatról, ha olyan gráfnak tekintjük, amelynek az adott pontok a csúcsai és a behúzott összekötő szakaszok az élei?
Feladat: 15.10.
Kutató munka:
Mi a helyzet, ha
15.9. feladatban minden pontot a tőle
legtávolabbival kötünk össze?
Konvex halmazok
Feladat: 15.11.
[
33]. 9. feladat, kissé módosítva.
Kutató munka:
Adott
n általános helyzetű pont a síkon. (Tehát semelyik három nem esik egy egyenesbe.) Melyik állítások ekvivalensek?
a) A pontok konvex burka
n-szög.
b) A pontok konvex
n-szöget alkotnak.
c) A pontok megszámozhatók úgy, hogy a megadott sorrendben egy konvex
n-szög csúcsai.
d) Semelyik három pont által alkotott háromszög nem tartalmaz további pontot a belsejében.
Feladat: 15.12.
Kutató munka:
Igaz-e a következő:
a) Ha adott öt általános helyzetű pont a síkon úgy, hogy közülük bármely négy konvex négyszöget alkot, akkor az öt pont is konvex ötszöget alkot?
b) Ha adott
n általános helyzetű pont a síkon úgy, hogy közülük bármely négy konvex négyszöget alkot, akkor az
n pont is konvex
n-szöget alkot? ([
33]. 10. feladat.)
Feladat: 15.13.
[
33]. 11. feladat.
Adott a síkon öt pont, közülük semelyik három nem esik egy egyenesbe. Bizonyítsuk be, hogy közülük valamelyik négy konvex négyszöget alkot.
Feladat: 15.14.
Kutató munka:
Adott a síkon
n pont (
n>4), közülük semelyik három nem esik egy egyenesbe. A
15.13. állítása segítségével próbáljunk alsó becslést adni arra, hogy hány olyan négyes van e pontok között, amelyek konvex négyszöget határoznak meg.
Feladat: 15.15. (M)
[
183]
Adott a síkon
n pont (
n>4), közülük semelyik három nem esik egy egyenesbe. Bizonyítsuk be, hogy legalább
(
n-3
2
) olyan konvex négyszög van, amelyeknek csúcspontjai az adott pontok közül valók! (IMO 1969.)
Helly tétele
Feladat: 15.16. (S)
Kutató munka:
Milyen
k-ra igaz a következő állítás:
Ha adott a síkon véges sok téglalap úgy, hogy mindegyik oldalai párhuzamosak a koordinátatengelyekkel és bármelyik
k téglalapnak van közös pontja, akkor van olyan pont a síkon, amelyet mindegyik téglalap tartalmaz.
Feladat: 15.17.
Kutató munka:
Milyen
k-ra igaz a következő állítás:
Ha adott véges sok téglatest úgy, hogy mindegyik oldalai párhuzamosak a koordinátatengelyekkel és bármelyik
k téglatestnek van közös pontja, akkor van olyan pont, amelyet mindegyik téglatest tartalmaz.
Feladat: 15.18. (SM)
Adott a síkon négy konvex alakzat, amelyek közül bármely háromnak van közös pontja. Bizonyítsuk be, hogy akkor mind a négynek is van közös pontja.
Feladat: 15.19. (SM)
Bizonyítsuk be a
Kétdimenziós Helly-tételt: Adott véges sok síkbeli konvex alakzat, közülük bármely háromnak van közös pontja. Ekkor az összesnek is van közös pontja.
Feladat: 15.20.
Kutató munka:
Milyen
a valós számra igaz a következő állítás:
Ha adott a síkon véges sok pont úgy, hogy semelyik három nincs egy egyenesen és bármelyik három körül írt körének a sugara legfeljebb egységnyi, akkor az összes pont lefedhető egy
a sugarú körrel.
Feladat: 15.21.
Kutató munka:
Hogyan gyengíthető a
15.20. feladat állításának feltétele?
Feladat: 15.22.
Kutató munka:
Milyen
t számokra igaz a következő állítás:
Ha adott a síkon véges sok pont úgy, hogy bármely kettő távolsága legfeljebb egységnyi, akkor az összes pont lefedhető egy legfeljebb
t sugarú körrel. (Jung tétele, l. [
189].)
Feladat: 15.23.
Egy köralakú biliárdasztalon 2400 darab 1 cm sugarú golyó helyezkedik el. Bizonyítsuk be, hogy legalább még egy ugyanekkora golyó lerakható az asztalra a többi elmozdítása nélkül, ha az asztal sugara legalább 1 méter.
Feladat: 15.24. (S)
Elhelyezhető-e egy egységkörben három 1/2 oldalú négyzet úgy, hogy közülük semelyik kettőnek ne legyen közös belső pontja?