16. FEJEZET: Az egyszerű skatulyaelv
A 18.24. feladatban (l. a Skatulyaelv a kombinatorikus számelméletben c. fejezetet) szerepel Dirichlet úgynevezett approximációs tétele. Ez a tétel arról is nevezetes, hogy egy komoly tétel bizonyításához itt használták először - legalábbis kimondva és hangsúlyosan - a skatulyaelvet.
A történethez tartozik, hogy amikor Dirichlet szemére vetették, hogy ilyen primitív gondolatot használva tett szert hírnévre, azt válaszolta: ,,ez igaz, de erre is rá kellett jönni". Andreas Speiser, aki csoportelméleti kutató és filozófus volt egy személyben,
Die geistige Arbeit című könyvében ([
179] 141. oldal) e történethez hozzáteszi: a skatulyaelv ugyan látszólag triviális, valójában a véges halmazok alaptulajdonságát ,,mozgósítja". A következő fejezetek feladatai is illusztrálják, mennyire igaz Speiser állítása: látni fogjuk, hogy ez a látszólag ,,ártalmatlan" elv milyen erős eszköz.
A K.I.8. fejezetben már bőségesen megismerkedtünk az egyszerű skatulyaelvvel. Itt csak pár ismétlő feladattal felelevenítjük, majd pár nehezebb versenyfeladattal vagy hasonlóval foglalkozunk.
Bevezető és ismétlő feladatok
Feladat: 16.1. (M)
Egy gulyában két falu 65 tehene legel, vörösek, fehérek, feketék és tarkák. Igazoljuk, hogy ha nincsen öt különböző korú, azonos színű tehén a gulyában, akkor található három azonos színű és egyidős tehén ugyanabból a faluból. (Arany Dániel-verseny, 1988H)
Feladat: 16.2. (SM) [
39]
Egy számsorozatot ,,bumfordinak" nevezünk, ha csak kétféle szám szerepel benne. (Ilyen például az
(1,2,2,1,2,1). Két egyforma hosszú sorozat ,,összegét" kapjuk, hogy a megfelelő tagokat összeadjuk. Így például
(1,1,-1,-1,1,-1,-1,1,-1)+(1,2,2,1,1,2,2,1,1)=(2,3,1,0,2,1,1,2,0)
|
.
a) Állítsuk elő a kilenctagú
(1,2,3,4,5,6,7,8,9) számsorozatot elő minél kevesebb bumfordi sorozat összegeként!
b) Legkevesebb hány 1994 tagú bumfordi sorozat összegeként lehet előállítani az
(1,2,3,4,5,…,1994) sorozatot? (OKTV 1994)
Feladat: 16.3. (M)
[
177]
Legyen
n páratlan szám, legyen továbbá
{
a1
,
a2
,…,
an
} az
{1,2…,n} számok egy permutációja. Bizonyítsuk be, hogy az
(
a1
-1)(
a2
-2)…(
an
-n) szorzat páros. (Kürschák-verseny, 1906.)
Feladat: 16.4. (SM)
[
176]
Ha a
8×8-as sakktáblán tetszésünk szerint egy egyenes vonalat rajzolunk, ez legfeljebb hány mezőnek belsején fog keresztülmenni? (Kürschák-verseny, 1930.)
Feladat: 16.5. (SM)
(Lukács Ottó, vö. [
173], 240. oldal.)
Egy pozitív egész számokból álló sorozat első két eleme 1 és 2. A sorozat semelyik két különböző tagjának az összegét nem tartalmazza. Maximálisan hány olyan tagja van a sorozatnak, amely nem nagyobb
n-nél?
Feladat: 16.6. (M)
a) Egy
4×4-es sakktábla mezőire pozitív egész számokat írtunk. Bármely két szomszédos mezőn álló szám különbségének abszolútértéke 0,1 vagy 2. Bizonyítsuk be, hogy van két egyforma a felírt számok között.
Van-e mindig három egyforma is?
b) Egy
12×12-es sakktábla mezőire pozitív egész számokat írtunk. Bármely két szomszédos mezőn álló szám különbségének abszolútértéke 0,1, 2 vagy 3. Bizonyítsuk be, hogy van három egyforma a felírt számok között.
Két mezőt akkor nevezünk szomszédosnak, ha van közös oldaluk.
Feladat: 16.7. (M)
Egy
n2
×
n2
-es sakktábla mezőire pozitív egész számokat írtunk. Bármely két szomszédos mezőn álló szám különbségének abszolútértéke legfeljebb
n. Bizonyítsuk be, hogy van
⌈n/2⌉ darab egyforma a felírt számok között. (Vö. OKTV 1999.)
Két mezőt akkor nevezünk szomszédosnak, ha van közös oldaluk.
Feladat: 16.8. (M)
[
80]
Adott
n-1 valós szám. Bizonyítandó, hogy kiválasztható közülük néhány (esetleg csak egy, esetleg mind) úgy, hogy a kiválasztott számok összege alkalmas
c egész számra a
[c-
1
n
,c+
1
n
] intervallumba essen.
Feladat: 16.9. (M)
*
Bizonyítsuk be, hogy a
f0
=0,
f1
=1, és
n>1-re
fn
=
fn-1
+
fn-2
képlettel definiált Fibonacci-sorozatnak van olyan tagja, amelyik a tízes számrendszerben ezer darab kilencesre végződik.
Feladat: 16.10.
Egy tízpontú összefüggő egyszerű gráfnak 15 éle van. Bizonyítsuk be, hogy bármelyik két favázának van közös éle. Legalább hány közös éle van két faváznak?
Feladat: 16.11.
a) Egy
n pontú összefüggő gráfnak van két olyan faváza, amelyek élhalmaza diszjunkt. Mit mondhatunk a gráf élszámáról?
b) Egy
n pontú gráfnak
n+k éle van. Mit mondhatunk két favázának közös éleiről?
Néhány versenyfeladat
Feladat: 16.12. (M)
Hét ember néhány napos kirándulásra készül. Mindennap egy kör alakú asztal köré ülve ebédelnek. Elhatározzák, hogy úgy ülnek le az ebédekhez, hogy ugyanaz a két ember ne kerüljön kétszer egymás mellé. Maximum hány naposra tervezhetik a kirándulást? (Arany Dániel-verseny, 2000H)
Feladat: 16.13. (M)
[
94].
Egy 6x6 mezőből álló ,,sakktáblát" hézagmentesen és átfedés nélkül dominólapokkal fedünk le. Mindegyik dominólap két szomszédos mezőt takar le. Bizonyítandó, hogy a mezőket elválasztó 5 vízszintes és 5 függőleges vonal között van olyan, amely egyetlen dominólapot sem vág ketté. (OKTV 1963D)
Feladat: 16.14. (M)
Végtelen sok cédula mindegyikére egy-egy egész szám van írva. Tudjuk, hogy bármely két cédulán álló szám között legfeljebb egymillió a különbség. Igazoljuk, hogy valamelyik szám végtelen sok cédulán szerepel. (OKTV)
Feladat: 16.15. (M)
[
176].
Legyen a síkban végtelen sok oly derékszögű négyszög kijelölve, amelyeknek szögpontjai valamely derékszögű koordináta-rendszerben így adhatók meg:
(0,0), (0,m), (n,0), (n,m)
|
,
hol
m és
n pozitív egész számok. Bebizonyítandó, hogy mindig van a kijelölt négyszögek közt két olyan, hogy egyik a másikban bennfoglaltatik. (Kürschák-verseny, 1934., eredeti szöveggel.)
Feladat: 16.16. (M)
* [
183] 239sk. oldal
Bizonyítsuk be, hogy bármely tíz - páronként különböző - kétjegyű természetes számból álló halmaznak mindig van két, közös elem nélküli részhalmaza, amelyben az elemek összege egyenlő egymással. (IMO, 1973.)
Feladat: 16.17. (M)
* [
176].
Bizonyítsuk be, hogy egy konvex
n-szög átlói közül nem lehet
n-nél többet úgy kiválasztani, hogy bármely kettőnek legyen közös pontja.
(Kürschák-verseny, 1962.)
Feladat: 16.18. (SM)
*
Legyenek
k és
n pozitív egészek,
n/2≤k≤n és legyen adva
k darab pozitív,
n-nél nem nagyobb különböző egész. Bizonyítsuk be, hogy van közöttük kettő (nem feltétlenül különböző), amelyek összege kettőhatvány. (OKTV 1996.)
Feladat: 16.19. (SM)
* [
174].
Valaki
55
szelvénnyel lottózik az ötös lottón. Bármely két szelvényét nézzük, van olyan szám, amely mindkét szelvényen meg van ikszelve.
Bizonyítsuk be, hogy az 1-től 90-ig terjedő számok között található négy olyan, hogy az illető mindegyik szelvényén a négy szám közül legalább az egyik meg van ikszelve. Feltesszük, hogy a különböző szelvények különböző módon vannak ikszelve. (Kürschák-verseny, 1976.)
Feladat: 16.20. (M)
Egy értekezletre két delegáció érkezik,
A és
B, mindkettőnek ugyanannyi tagja van. A két delegáció tagjai közül némelyek már ismerik egymást. Bizonyítsuk be, hogy az
A delegációból kiválasztható néhány ember (legalább egy) úgy, hogy a
B delegáció minden tagja páros sokat ismer a kiválasztottak közül, vagy úgy, hogy minden tagja páratlan sokat ismer a kiválasztottak közül.
Egy nevezetes Erdős-Szekeres feladat
Feladat: 16.21. (SM)
** Bizonyítsuk be, hogy egy
nk+1 tagú sorozatban vagy van
n+1 szám, amelyek a sorozatbeli sorrendjükben szigorúan monotonan növekednek, vagy van
k+1 szám, amelyek a sorozatbeli sorrendjükben monotonan csökkennnek. (Erdős Pál, Szekeres György, vö. [
173], 240. oldal.)
Feladat: 16.22. (S)
Bizonyítsuk be, hogy ha egy valós számokból álló sorozatnak nincs
n+1 olyan tagja, amelyek szigorúan monotonan növekvő sorozatot alkotnának, akkor a sorozat felbontható
n darab monoton csökkenő sorozatra.