11. FEJEZET: Vegyük a legnagyobbat, a legszélsőt! Bevezető feladatok
A fejezet témájához kapcsolódó korábbi feladatok: 4.3., 6.20., 9.11., 10.9.
Egy klasszikus Kürschák-feladat
Feladat: 11.1. (SM)
Egy kocka csúcsaira egy-egy valós számot írtunk úgy, hogy minden csúcsra a szomszédos csúcsokon álló számok számtani közepe került. A nyolc csúcs közül hányon állhat különböző szám?
Feladat: 11.2. (S)
Hogyan változik az előző (
11.1.) feladat, ha azt tudjuk, hogy minden csúcsra egy szomszédos csúcson álló szám felének és a többi szomszédján álló számok hatodának az összege került?
Feladat: 11.3. (SM)
Hogyan változik a
11.1. feladat, ha azt tudjuk, hogy minden csúcsra a szomszédos csúcsokon álló számok közül a legnagyobb kerül?
Feladat: 11.4. (SM)
Hogyan változik a
11.1. feladat, ha kocka helyett egy három oldalú hasábról van szó? (L. Kürschák-verseny, 1935. [
176])
És ha valamely más egyszerű poliéderről van szó?
Feladat: 11.5. (SM)
Egy véges gráf minden csúcsára egy-egy valós számot írtunk úgy, hogy minden csúcsra a szomszédos csúcsokon álló számok számtani közepe került. Legfeljebb hány különböző számot használhattunk?
Feladat: 11.6. (S)
Hogyan változik a helyzet, ha a gráf minden csúcsára a szomszédos csúcsokon álló számok közül a(z egyik) legkisebbet írjuk?
Feladat: 11.7.
Fogalmazzuk meg, min múlt a fejezet eddigi feladatainak a megoldása!
Feladat: 11.8. (SM)
Igaz-e a
11.5. feladat megoldásában (
11.5M) kapott állítás végtelen gráfokra is?
Feladat: 11.9. (SM)
Hol használtuk a
11.5. feladat megoldásában, hogy véges gráfról van szó?
További feladatok
Feladat: 11.10. (SM)
Bizonyítsuk be, hogy egy egyszerű poliédernek van két azonos élszámú lapja.
Feladat: 11.11. (SM)
a) Adott tíz (páronként különböző) valós szám. Képezzük az összes kéttagú összeget e tíz számból. Legalább hány különböző érték lesz közöttük?
b) Adott
n darab (páronként különböző) valós szám. Képezzük az összes kéttagú összeget ebből az
n számból. Legalább hány különböző érték lesz közöttük?
Feladat: 11.12. (M)
a) Adott
n darab (páronként különböző) valós szám. Képezzük az összes háromtagú összeget ebből az
n számból. Legalább hány különböző érték lesz közöttük?
b) Legalább hány különböző érték lesz
n (páronként különböző) szám
k tagú összegei között?
Feladat: 11.13. (M)
Egy 105 tagú társaságban 100 fiú és öt lány van. A 100 fiú mindegyike ismer legalább kettőt a lányok közül. Az ismeretségek kölcsönösek. Bizonyítsuk be, hogy
a) van egy lány, aki legalább 40 fiút ismer;
b) van három lány, akik ha összeadják, hogy hány fiút ismernek, az eredmény legalább 120.
Feladat: 11.14. (M)
Egy
n gyöngyből álló nyaklánc mindegyik gyöngyszemére egy egész szám van írva. A számok összege
n-1. Bizonyítsuk be, hogy szétvágható a nyaklánc úgy, hogy a kapott gyöngyfűzér balról számított első
k gyöngyén álló számok összege minden szóba jövő
k-ra kisebb legyen
k-1-nél.
Feladat: 11.15. (SM)
Adott véges sok pont a síkon úgy, hogy semelyik három nincs egy egyenesen és bármely három által alkotott háromszög területe legfeljebb egységnyi. Bizonyítandó, hogy az összes pont lefedhető egy legfeljebb négy területű háromszöggel. (Vö. Arany Dániel-verseny, 2005H)
Helyettesíthető-e kisebb számmal a négyes szorzó ebben az állításban?
Feladat: 11.16. (SM)
Adott véges sok pont a síkon úgy, hogy semelyik három nincs egy egyenesen és bármely három által alkotott háromszög területe legfeljebb egységnyi. Bizonyítandó, hogy az összes pont lefedhető egy legfeljebb négy területű téglalappal.
Helyettesíthető-e kisebb számmal a négyes szorzó ebben az állításban?
Feladat: 11.17. (M)
Hol használtuk a
11.15. feladatban, hogy véges sok pont van adva?
Egy másik Kürschák-feladat és az egydimenziós Helly-tétel
Feladat: 11.18. (SM)
Egy könyvtárban egy napon mindenki egyszer járt. Bármely két könyvtárlátogató találkozott aznap. Bizonyítsuk be, hogy volt olyan időpont, amikor minden látogató egyszerre volt ott a könyvtárban.
Megjegyzés. Ezt lehet az egydimenziós Helly-tételnek is tekinteni. A kétdimenziós Helly-tételt lásd a
Kombinatorikus geometria című fejezet
15.19. feladatában.
Feladat: 11.19. (SM)
[
176].
Egy könyvtárban egy napon mindenki egyszer járt. Bármely három könyvtárlátogató közül volt kettő, aki találkozott aznap. Bizonyítsuk be, hogy volt két olyan időpont, amelyeken együttvéve az összes látogató ott volt a könyvtárban. (Kürschák verseny, 1950.)
Feladat: 11.20. (M)
Hogyan általánosítható a
11.19. feladat?
Feladat: 11.21. (S)
a) Adott egy egyenesen véges sok zárt intervallum úgy, hogy bármelyik kettőnek van közös pontja. Bizonyítsuk be, hogy az összes intervallumnak is van közös pontja.
b) Adott egy egyenesen véges sok zárt intervallum úgy, hogy bármelyik
k+1 között van kettő, amelyik metszi egymást. Bizonyítsuk be, hogy az összes intervallum lefogható
k ponttal. (Azaz van
k pont, amelyekre igaz, hogy minden intervallum tartalmaz közülük legalább egyet.)
Két versenyfeladat
Feladat: 11.22. (SM)
[
174] *Három iskola mindegyikében
n tanuló van. Minden iskola minden tanulója a másik két iskolából együttvéve
n+1 tanulót ismer. Bizonyítsuk be, hogy választható a három iskola mindegyikéből egy-egy tanuló úgy, hogy mindegyikük ismeri a másik kettőt. Az ismeretségeket kölcsönösnek tételezzük fel. (Kürschák-verseny, 1977.)
Feladat: 11.23. (SM)
*
Egy számot 3-univerzális számnak nevezünk, ha belőle jegyeket letörölve megkapható minden különböző számjegyekből álló
abc háromjegyű szám. Például az 134356 számból letörléssel megkapható a 456 szám, de nem kapható meg a 465 szám.
Hány számjegyű a legrövidebb 3-univerzális szám? (Arany Dániel-verseny, 1986H.)