Cím: A zsák meg a foltjai
Szerző(k):  fordította: Paulin Elemér ,  I. M. Jaglom 
Füzet: 2001/január, 10 - 20. oldal  PDF file
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A Kvant című, orosz ifjúsági matematika‐fizika folyóiratban jelent meg a következő feladat:*A feladat kitűzője E. B. Denkin, sorszáma M. 185. A rövid megoldás megtalálható a Kvant 1973. évi 10. számában.
Egy egységnyi területű zsákon öt folt található, amelyek bármelyikének a területe legalább 12. Mutassuk meg, hogy van a foltok között kettő, melyek közös részének területe legalább 15.
A következőkben egyszerűbb feladatokon keresztül a probléma általánosításához is eljutunk. A felmerülő nehezebb feladatokat *-gal jelöltük. Az alábbiakban a zsákot, valamint annak területét is (a feladatban ez egységnyi) M betűvel jelöljük majd, a foltokat és azok területeit pedig M1, M2, M3, M4, M5-tel. Szükségünk lesz például az M1 és M2 foltok közös részére; ezt M12 jelöli majd, és hasonlóan, az M1, M2, M3 foltok közös részét M123 stb. Reméljük, a szövegből világosan kiderül majd, mikor beszélünk egy alakzatról és mikor annak területéről.
Lássunk hozzá a feladat megoldásához!
Abból, hogy a foltok területének összege, M1+M2+M3+M4+M552, tehát nagyobb a zsák területénél (hiszen M=1), következik, hogy a foltok között vannak átfedések. A feladatban alsó korlátot kell keresnünk a foltok páronkénti közös részének a területére, meg kell becsülnünk az M12, M13, ..., M45 számok legnagyobbikát.
Először megmutatjuk, hogy

M-(M1+M2+M3+M4+M5)+(M12+M13+M14+...+M45)0.(1)
Ha a foltok között nem volnának átfedések, akkor már az M-(M1+M2+M3+M4+M5) különbség sem lenne negatív; ez a különbség egyenlő volna a zsák azon részének a területével, ahol egyáltalán nincsen folt. Mivel a foltok metszik egymást, az M1+M2+M3+M4+M5 összeg lényegesen nagyobb, mint a zsák foltokkal fedett részének S területe; itt természetesen SM=1. Valóban, az M1+M2+M3+M4+M5 összegben az M12 részt kétszer is számoltuk, mivel az M1 és az M2 tagok is tartalmazzák; ugyanígy, az M123 részt háromszor, és így tovább.
Most bebizonyítjuk, hogy
SMi-Mij,(1')
ahol a képletben Mi=M1+M2+M3+M4+M5; Mij=M12+M13+...+M45, és a továbbiakban is eszerint használjuk a jelölést. Mivel MS, innen már következik az (1) egyenlőtlenség, annak alapján pedig már megbecsülhetjük a legalább kétszer lefedett területek M12, M13, ... nagyságát. Valóban, (1)-ből következik, hogy
M12+M13+...+M45(M1+M2+M3+M4+M5)-M52-1=32.
A foltok páronkénti átfedéseinek száma (52)=10, azért az M12, M13, ..., M45 számok legnagyobbika nem kisebb, mint 32:10=320. Becslésünk sajnos gyengébbnek bizonyult a szükségesnél, mivel 15>320.
 
1. feladat. Az egységnyi területű zsákon kilenc, egyenként 15 területű folt található. Mutassuk meg, hogy van közöttük kettő, amelyek közös részének területe legalább 145.
 
 
 
A szitaformula
 
 

A fentiekben a zsák foltozott részének S területére kapott (1') becslés nem bizonyult eléggé élesnek. Próbálkozzunk finomabb módszerrel: hagyjuk el (1') jobb oldaláról az olyan, Mij alakú részek területeit, amelyeket egyszerre legalább három folt fed le. Eddig ugyanis M123 például megtalálható a pozitív előjellel szereplő M1, M2, M3 és a negatív előjellel szereplő M12, M13, M23 tagokban is, ezért az M123 terület egyáltalán nem szerepel (1') jobb oldalán. Így S pontosabb becslését adja a Mi-Mij+Mijk összeg. Természetesen még ez sem pontos, itt ugyanis kétszer számoltuk a zsák azon részét, amit egyszerre legalább négy folt fed le; az M1234 mennyiséget például a páratlanszor fedő M1, M2, M3, M4, M123, M124, M134, M234 tagokban összesen 8-szor pozitív, a párosszor fedő M12, M13, M14, M23, M24 és M34 tagokban pedig összesen 6-szor negatív előjellel vettük figyelembe.
A korábbinál jobban közelíti tehát S értékét a
Mi-Mij+Mijk-Mijkl
összeg; ez már ,,majdnem egyenlő" S pontos értékével. Itt már a zsák minden olyan részét figyelembe vettük, amelyet legfeljebb négy folt fed le. De a zsák ,,legkényesebb'', ötszörösen foltozott része kiesik a fenti összegből, mivel egyszerre van ott az M1, M2, M3, M4, M5; M123, M124, ..., M345 tagokban (ez 15 pozitív előjelű tag) és az M12, M13, ..., M45, M1234, M1235, M1245, M2345 tagokban is (ez 15 negatív előjelű tag). Tehát S pontos értékét úgy kapjuk, ha az utolsó összeghez hozzáadjuk az M12345 tagot. Ekkor
S=Mi-Mij+Mijk-Mijkl+M12345(2)
(itt i, j, k, l=1, 2, 3, 4 vagy 5).
Legyen σ a zsák ép részének a területe, amelyet egyetlen folt sem fed le. Mivel σ=M-S és természetesen σ0, így
σ=M-Mi+Mij-Mijk+Mijkl-M123450.(3)
A (3) összefüggést az M zsák többszörösen foltozott részeinek szakaszos eltávolításával és azoknak a részeknek a visszaillesztésével kaptuk, amelyeket többször is eltávolítottunk; az összefüggést magyarul szitaformulának nevezik. A módszert és a formulát ‐ amelynek más alakja is ismeretes ‐ sok kombinatorikai feladatban használják. Érdemes átgondolni és felírni a képletet akkor is, ha a foltok száma n. Talán bonyolultnak tűnik, de csak a fenti egyszerű elv matematikai formája.
σ=M-Mi1+Mi1i2-Mi1i2i3+Mi1i2i3i4-......+(-1)n-1Mi1i2i3...in-1+(-1)nM123...n0(4)
(itt az i1, i2, ..., in=1 indexek az 1, 2, 3, ..., n értékek bármelyikét fölvehetik, de az Mi1i2...ik rész i1, i2, ..., in indexei feltétlenül különbözők).
 
 
Feladatok
 


 
2. Írjuk fel és bizonyítsuk be a szitaformulát, ha n=6.
 
3*. Bizonyítsuk be a (4) formulát.
 
4. Egy táborban 220 gyerek nyaral. Hatféle sportra van lehetőség, ezek: atlétika (a), röplabda (r), kosárlabda (k), labdarúgás (l), birkózás (b) és sakk (s). Az egyes sportágakban résztvevő gyerekek száma rendre: (a)-30, (r)-26, (k)-32, (l)-31, (b)-28, (s)-36. Az említettek közül 53-an többféle sporttal is megpróbálkoztak: közülük 24-en három vagy annál is több, 9-en legalább négy és a 3 leglelkesebb legalább ötféle sportot is kipróbált. Az utóbb említett 3 között van 1 ,,csodabogár", aki mind a hat sportággal szerencsét próbált. Hány lusta gyerek nyaralt ebben a táborban, aki tehát egyetlen sportággal sem próbálkozott?

 
 
A kiinduló feladat megoldása
 
 

Láttuk, hogy az M-Mi+Mij0 egyenlőtlenség nem adja meg kellő pontossággal a minket érdeklő maxMij mennyiség értékét (így jelöljük az Mij mennyiségek legnagyobbikát). Szükségképpen a teljes becslést használjuk majd, amely tehát a következő:
M-Mi+Mij-Mijk+Mijkl-M123450(3')
A másik ötlet, hogy a (4) formula, mint általános összefüggés, valamennyi szóbajövő halmazra alkalmazható, így például ha Mi-re írjuk fel, akkor azt kapjuk, hogy
σ1=M1-M1i+M1ij-M1ijk+M123450,
ahol σ1 az M1 foltnak az a része, amelyet más folt nem fed le. Az i, j, k indexek a 2, 3, 4, 5 számok összes lehetséges értékét felveszik. Hasonló egyenlőtlenségeket írhatunk fel az M2, M3, M4, M5 foltokra is:
σ2=M2-M2i+M2ij-M2ijk+M123450,σ5=M5-M5i+M5ij-M5ijk+M123450.
Ha összeadjuk az így kapott öt egyenlőtlenséget, akkor a
Mi-2Mij+3Mijk-4Mijkl+5M123450.(5)
egyenlőtlenséget kapjuk. (Ellenőrizzük az együtthatókat!)
Próbáljuk most elkészíteni a (3') és az (5) egyenlőtlenségek olyan kombinációját, amelyben nem szerepelnek a Mijk típusú összegek, tehát a zavaróan ,,nagy'', hármasan fedett részek. Látható, hogy ehhez (5)-öt 13-dal kell szorozni, és ezt kell hozzáadni (3')-höz. Így a következő egyenlőtlenséget nyerjük:
M-23Mi+13Mij-13Mijkl+23M123450.(6)
Megmutatjuk, hogy ebből
M-23Mi+13Mij0(7)
következik.
Valóban, hiszen M12345 része az Mijkl halmazok mindegyikének, azért Mijkl5M12345, és így még inkább -13Mijkl+23M123450. A (7) egyenlőtlenséget átrendezve kapjuk, hogy
Mij2Mi-3M2(512)-3=2.

Mivel az Mij ,,dupla lefedettségek'' száma 10, ezért közülük legalább egynek az értéke nem kisebb, mint 2:10=15, és éppen ezt kellett bizonyítani! A felhasznált egyenlőtlenségek láncolatát végignézve látható, hogy a fenti becslésben lehetséges egyenlőség, mégpedig pontosan akkor, ha S=M, vagyis ha a foltok a zsák teljes területét lefedik, továbbá, ha minden Mi=12, minden Mij=15, és minden Mijkl=0. Eredményünk éles:
   12   13   14   15   23    24   25   34   35   45    123   124   125   134   135    145   234   235   245   345 
Az 1. ábrán látható elrendezésben az M területű (nagy) téglalap játssza a zsák szerepét, az egyes négyzeteken szereplő számok pedig azt mutatják, hogy hányas számú folt vesz részt a szóban forgó terület lefedésében. Talán zavaró lehet, hogy a ,,foltok'' most nem összefüggő darabok, de a feladatban csak a területük fontos, alakjuk és szerkezetük nem.
Fogalmazzuk most meg az általánosabb feladatot, amelynek a most megoldott csak speciális esete.
 
 
A kétszeresen foltozott terület általában
 
 

Az egységnyi területű M zsákon n folt található, ezek M1, M2, ..., Mn; egyikük területe sem kisebb egy adott pozitív α számnál. Becsüljük meg az Mij számok legnagyobbikának területét. Más szavakkal: minden n-szeresen foltozott zsákon megkeressük a kétszeresen fedett Mij területek legnagyobbikát, és azt kérdezzük, hogy mennyi az így talált maximumok legkisebb értéke. Feltételezzük, hogy ez a minimum létezik, bár végtelen számhalmazról lévén szó ez egyáltalán nem nyilvánvaló. Ilyen jellegű ,,minimax'' feladatok megoldása, amikor maximumként értelmezett számok minimumát keressük, nagyon fontos a modern matematikában. A keresett minmaxMij természetesen függ az adott α számtól, annak függvénye; mivel a foltok számától, az n-től is függ, ezért jelöljük fn(α)-val. (Itt természetesen 0α1 és n2). A kiinduló ,,zsák‐folt'' feladatot megoldva az f5(12)=15 egyenlőséget bizonyítottuk be. A feladat általánosításában az fn(α)
függvényt kellene megadni α és n segítségével.
Tapasztalatok gyűjtése érdekében vizsgáljuk először az egyszerűnek tűnő n=2 esetet. Legyen tehát az egységnyi területű M zsákon két folt (M1 és M2) úgy, hogy mindkettejük területe legalább α; feladatunk, hogy megtaláljuk az M1 és M2 foltok M12 közös részének a legkisebb f2(α) területét. Világos, hogy ha α12, akkor lehetséges, hogy egyáltalán nincsen átfedés (2.a ábra); ha pedig α12, akkor kétszeresen fedett M12 terület legkisebb értéke 2α-1 (2.b ábra). Így
f2(α)={0,ha  0α12,2α-1,ha  12α1,(8)
a függvény grafikonja látható a 3. ábrán.
 
 
 
Feladat
 
 


 
5. Jellemezzük az y=f3(α) függvényt.
Útmutatás: vizsgáljuk az M körlap olyan egybevágó M1, M2, M3 körcikkeit, amelyek szimmetriatengelyei páronként 120-os szöget zárnak be, középponti szögük mérőszáma pedig α, pontosabban a teljesszög α-szorosa. Kezdjük kicsi értékekkel (4. ábra), majd fokozatosan növeljük α értékét egészen 1-ig.
 


 
 
Öt folt
 
 

Térjünk most vissza az eredeti feladathoz, keressük, hogy legalább mekkora a kétszeresen lefedett terület, amennyiben az M zsákon található M1, M2, M3, M4, M5 foltok bármelyikének területe legalább α. Világos, hogy f5(α)0, vagyis az y=f5(α) függvény grafikonja nem helyezkedhet el az x tengely alatt (5. ábra). A függvény értéke lehet nulla, ha a foltok elrendezhetők úgy, hogy mindegyik Mij értéke nulla. Ez pontosan akkor lehetséges, ha a foltok területének összege, amely a feltételek szerint legalább 5α, nem nagyobb 1-nél (mivel a zsák területe egységnyi): f5(α)=0, ha 0α15. Továbbá az (1) egyenlőtlenségből következik, hogy MijMi-M5α-1. Figyelembe véve, hogy a foltok ,,páronkénti (dupla) átfedéseinek'' száma egyenlő 10-zel, kapjuk, hogy
f5(α)110(5α-1)=12α-110.(9)
A (9) egyenlőtlenség minden szóba jövő α-ra igaz; így az y=f5(α) függvény grafikonja nem helyezkedhet el az y=12α-110 egyenes alatt (6. ábra). Ahhoz, hogy a (9)-ben éppen egyenlőség álljon, szükséges, hogy 12α-110 nagyobb legyen nullánál; ezen kívül még az is, hogy az (1) egyenlőtlenségben is az egyenlőség teljesüljön ‐ tehát mindegyik Mijk értéke nulla kell, hogy legyen, és minden Mij értéke ugyanannyi, 12α-110 kell legyen. De ha az összes Mijk=0, akkor mindegyik α területű folton, például az M1-en, az egyenként 12α-110 területű M12, M13, M14 és M15 foltoknak már átfedések nélkül kell elhelyezkedniük. Ez csak akkor lehetséges, ha 4(12α-110)α, azaz α25. Sikerült tehát az f5(α) függvényt kiterjesztenünk: f5(α)=12α-110, ha 15α25.
A továbbiakban ismét a (7) egyenlőtlenséget használjuk. Ebből az egyenlőtlenségből következik, hogy Mij2Mi-3M2(5α)-3=10α-3, tehát
f5(α)110(10α-3)=α-310.(10)
A (10) egyenlőtlenség minden α esetén teljesül, vagyis az f5(α) függvény grafikonja teljes egészében az y=α-310 egyenes felett helyezkedik el (7. ábra); megjegyzendő, hogy (10)-ben csak akkor lehetséges egyenlőség, ha 25α35 (lásd a 6.a feladatot). A továbbiakban a szitaformulát nem csak a foltok Mi területére alkalmazzuk majd, mint a megoldásban tettük, hanem a kétszeresen és a háromszorosan fedett Mij, Mijk területekre is. Így, ha például az említett képletet az M12 területre használjuk, amelyen az M123, M124 és M125 foltok helyezkednek el, a következőt kapjuk:
σ12=M12-M12i+M12ij-M123450.
Összesen tíz ilyen egyenlőtlenség írható fel; ezeket összeadva kapjuk, hogy
Mij-3Mijk+6Mijkl-10M123450.(11)
Hasonlóan, az M123-ra (ezen az M1234 és M1235 foltok találhatók) felírt szitaformula azt adja, hogy
σ123=M123-M123i+M123450.
Mivel a foltok Mijk hármas átfedéseinek a száma 10, azért ha összeadjuk a megfelelő tíz egyenlőtlenséget, akkor kapjuk, hogy:
Mijk-4Mijkl+10M123450.(12)
Mostanra rendelkezésünkre állnak a (3'), (5), (11) és (12) egyenlőtlenségek, amelyek kapcsolatot teremtenek az M, Mi, Mij, Mijk, Mijkl és M12345 mennyiségek között. Most tekintsük az (5) egyenlőtlenség 12-szeresének, a (11) 16-szorosának és a (3') egyenlőtlenségnek az összegét:
M-12Mi+16Mij-16M123450(13)
Az együtthatók megválasztása miatt ez már nem tartalmazza a háromszoros és a négyszeres Mijk, valamint a Mijkl tagokat. Elhagyva az ötszörösen fedett negatív tagot innen következik, hogy
M-12Mi+16Mij0
és ezért
Mij3Mi-6M3(5α)-6,
tehát
f5(α)110(15α-6)=32α-35.

Eszerint az f5(α) függvény grafikonja nem helyezkedhet el az y=32α-35 egyenes alatt (8. ábra). Készítsük most el a (3'), (5), (11), (12) egyenlőtlenségek
(3')+35(5)+310(11)+110(12)
lineáris kombinációját; kapjuk, hogy
M-25Mi+110Mij0. (15)
Itt már csak az M, Mi és Mij tagok szerepelnek. A (15)-ből következik, hogy
Mij4Mi-10M4(5α)-10=20α-10,
tehát
f5(α)110(20α-10)=2α-1.
Az f5(α) függvény grafikonja tehát nem haladhat az y=2α-1 egyenes alatt, végeredményben tehát nem helyezkedhet el az 9. ábrán látható töröttvonal alatt; könnyen belátható, hogy a függvény grafikonja éppen azonos ezzel a töröttvonallal.
 

 
Feladatok
 


 
6. Bizonyítsuk be, hogy

a) f5(α)=α-310, ha 25α35;  b) f5(α)=32α-35, ha 35α45;
c) f5(α)=2α-1, ha 45α1.

 
7. Jellemezzük az  a) f4(α) b) f6(α) függvényt.

 
 
A feladat általánosítása
 
 

Ezt az esetet az n=5 esethez hasonlóan tárgyaljuk. Világos, hogy n folt esetén az M1, M2, ..., Mn foltok (ezek bármelyikének területe legalább α) akkor nem fedik egymást, ha az összterületük Minα, és ez az összterület nem nagyobb M=1-nél (hiszen a zsák területe egységnyi). Ezért fn(α)=0, ha 0α1n. A továbbiakban ismét a (4) egyenlőtlenségből (a szitaformulából) indulunk ki. Ebből most
M-Mi+Mij0(16)
következik. (Miért?) Így
MijMi-Mnα-1.
Mivel az Mij átfedések száma általában (n2)=n(n-1)2, azért
fn(α)1n(n-1)/2(nα-1)=2n-1α-2n(n-1).(17)

A (17) egyenlőtlenség csakis akkor válik egyenlőséggé, ha egyenlőséggé alakul a (16), vagyis ha (4)-ben az összes olyan tag, amelyik a Mij tag után következik, nulla. Szükséges ezen kívül még az is, hogy az egyenként α területű Mi foltok teljesen lefedjék az M zsákot. De ez esetben az M1 kétszeres lefedései, tehát az M12, M13, ..., M1n (ezekből n-1 db van) az M1 foltot további átfedések nélkül fedik le mivel az összes Mijk=0. Miután ekkor M1i=2n-1α-2n(n-1), azért
(n-1)[2n-1α-2n(n-1)]α,
tehát α2n (és természetesen α1n).
A továbbiakban a már megszokott módon az Mi foltokra alkalmazzuk a szitaformulát, majd azok Mij, Mijk stb. átfedéseire. Alkalmazzuk ezt a képletet, például az M1 foltra, amelyet az M12, M13, ..., M1n ,,másodrendű foltok'' fednek:
M1-M1i1+M1i1i2-M1i1i2i3+......+(-1)n-2M1i1i2...in-2+(-1)n-1M123...n0
(ahol i1, i2, ..., in-2=2, 3, ..., n). Ha összeadjuk az M1, M2, ..., Mn foltokra felírt n db egyenlőtlenséget, akkor a következőt kapjuk:
Mi-2Mi1i2+3Mi1i2i3-......+(-1)n-2(n-1)Mi1i2...in-1+(-1)n-1nM123...n0(18)
(hasonlítsuk össze az (5) egyenlőtlenséggel).
A (4)-ból és a (18)-ból a szokott módon iktathatók ki a Mi1i2i3 tagok ‐ ehhez (18) 13-szorosát kell hozzáadni a (4)-hez:
M-23Mi1+13Mi1i2-13Mi1i2i3+...+(-1)n-1n-33M123...n0.(19)
A (19)-ből következik
M-23Mi1+13Mi1i20,(19a)
és így
Mi1i22Mi1-3M2(nα)-3=2nα-3.
Tehát
fn(α)1n(n-1)2(2nα-3)=4n-1α-6n(n-1),(20)
ahol egyenlőség csakis 2nα3n esetén lehetséges (lásd a 8. feladatot). A fentiekhez hasonlóan folytatva a következő általános képlethez jutunk:
fn(α)=2r-1n-1α-r(r-1)n(n-1),(21)
ha r-1nαrn, ahol r=1, 2, 3 ..., n.
 
 
Feladatok
 


 
8. Mutassuk meg, hogy (20)-ban csak akkor állhat egyenlőség, ha 2nα3n.
 
9*. Mutassuk meg, hogy fn(α)=6n-1-12n(n-1), ha 3nα4n.
 
10*. Bizonyítsuk be a (21) összefüggést.

 

 I. M. Jaglom
fordította: Paulin Elemér
 

Ennek a cikknek a nyomán tűztük ki a B. 3378. feladatot, amelynek megoldása a 30. oldalon olvasható. A szerk.
 

 

 

 

 

 

 

 

*1