18. FEJEZET: Skatulyaelv a kombinatorikus számelméletben
A skatulyaelv számelméleti alkalmazásához érdemes végiggondolni, hogy hogyan bizonyítjuk azt a nevezetes állítást, hogy ha egy
n teljes maradékrendszert megszorzunk egy
n-hez relatív prím
d számmal, akkor ismét teljes maradékrendszert kapunk. A bizonyítás két lépésen múlik, az egyik az, hogy ha
da és
db ugyanazt a maradékot adják
n-nel osztva és
d relatív prím
n-hez, akkor
a és
b is ugyanazt a maradékot adja
n-nel osztva. Minket itt most a bizonyítás másik lényeges eleme érdekel. Az, hogy
n egész szám között vagy van egy
n-nel osztható, vagy mind különböző maradékot ad
n-nel osztva.
Ezt a gondolatot - amelyet nevezhetünk a ,,számelméleti skatulyaelvnek" is - a fejezet számelméleti feladataiban többször fogjuk használni.
Feladat: 18.1. (M)
[
186], 111. oldal.
Egy síkbeli négyzetrácsot egységoldalú négyzetek alkotnak. Bizonyítsuk be, hogy bárhogyan is választunk ki 101 rácspontot, lesz köztük legalább 2 olyan, amelyeknél mindkét megfelelő koordináta különbsége 0-ra végződő egész szám, bármely olyan koordinátarendszerben, amelynek tengelyei rácsegyenesek. (Ki miben tudós? 1966/elődöntő)
Feladat: 18.2. (S)
Hogyan szól a
18.1. feladat térbeli megfelelője?
Feladat: 18.3. (M)
Hány rácspontot lehet megadni a síkon úgy, hogy semelyik kettő által alkotott szakasz felezőpontja ne legyen rácspont? (OKTV, 2002)
Feladat: 18.4. (M)
Egy futóversenyen
1,2,…,n rajtszámú versenyzők indultak, holtverseny nem volt. Minden versenyző rajtszámához helyezése sorszámát hozzáadva a kapott számok csupa különböző maradékot adnak
n-nel osztva. Milyen
n-ekre lehetséges ez? (Arany Dániel-verseny, 1990H)
Feladat: 18.5. (M)
Igazoljuk, hogy 102 darab pozitív egész szám közül kiválasztható kettő úgy, hogy azok különbsége vagy összege osztható legyen 200-zal! (OKTV, 2005 1. ford.)
Igaz-e az állítás, ha csak annyit kötünk ki, hogy a 102 szám egész szám legyen?
Igaz-e az állítás 101 darab egész szám esetén is?
Hogyan általánosítható a feladat?
Feladat: 18.6. (S)
Az első
2n pozitív egész szám közül hányat tudunk úgy kiválasztani, hogy semely kettő ne legyen egymáshoz relatív prím?
Feladat: 18.7. (SM)
Adjunk meg az első 60 pozitív egész szám közül negyvenet úgy, hogy azok közül bárhogyan választunk ki hármat, van közöttük kettő, amelynek legnagyobb közös osztója egynél nagyobb.
Feladat: 18.8. (SM)
Bizonyítsuk be, hogy
a) megadható 1324 olyan 1987-nél kisebb különböző pozitív egész, amelyek között nincs három egymáshoz páronként relatív prím;
b) akárhogyan is adunk meg 1325 különböző 1987-nél kisebb pozitív egész számot, szükségképpen lesz közöttük három egymáshoz relatív prím!
(OKTV, 1987)
Feladat: 18.9.
Adott öt rácspont a síkon. Bizonyítandó, hogy van közöttük néhány (legalább egy, esetleg mind), amelyek összegének mindkét koordinátája osztható hárommal.
Feladat: 18.10. (M)
Az első 20 pozitív egész szám közül hányat lehet úgy kiválasztani, hogy közülük egyik se legyen osztója a másiknak?
Feladat: 18.11. (SM)
Az első
2n pozitív egész szám közül hányat lehet úgy kiválasztani, hogy közülük egyik se legyen osztója a másiknak?
Mi a helyzet, ha az első
2n+1 számból választhatunk?
Feladat: 18.12. (SM)
([
173], 240. old.)
Bizonyítsuk be, hogy
2n-ig megadható
n darab különböző természetes szám úgy, hogy bármely kettő legkisebb közös többszöröse nagyobb legyen
2n-nél, de
n+1 szám már nem adható meg e tulajdonsággal.
Feladat: 18.13. (SM)
* Legyen
a tetszőleges valós szám. Igazoljuk, hogy az
(a,a+1/n) nyílt intervallumban legfeljebb
⌈n/2⌉ olyan tört lehet, amelynek nevezője nem nagyobb
n-nél.
Feladat: 18.14. (SM)
Adott 20 egész szám. Egyiknek sincs 10-nél nagyobb prímosztója. Bizonyítandó, hogy van közöttük kettő, amelyek szorzata négyzetszám. (Vö. Arany Dániel-verseny, 2005H)
Feladat: 18.15. (M)
Adott 300 egész szám. Egyiknek sincs 20-nál nagyobb prímosztója. Bizonyítandó, hogy van közöttük kettő, amelyek szorzata négyzetszám.
Feladat: 18.16. (SM)
Az 1-től
3n-ig terjedő egész számok közül kiválasztunk
n+2 darabot. Bizonyítandó, hogy ha
n>1, akkor mindig van a kiválasztott számok között kettő, melyek különbsége
n-nél nagyobb, de
2n-nél kisebb. (Kürschák verseny, 1952. [
176])
Feladat: 18.17. (SM)
Bizonyítsuk be, hogy ha adott
n darab egész szám, ezek közül mindig kiválasztható néhány (legalább egy, esetleg mind), amelyek összege osztható
n-nel. (Kürschák verseny, 1948. [
176])
Feladat: 18.18. (SM)
Adott a síkon kilenc rácspont, semelyik három nincs egy egyenesen. Bizonyítsuk be, hogy van közöttük három, amelyek által alkotott háromszög súlypontja is rácspont.
Igaz-e az állítás nyolc rácspontra is?
Feladat: 18.19. (SM)
A
-3-as számrendszert a következőképpen definiáljuk. A számjegyek a
0,1,2 számok. Az
n-edik helyen álló jegyet
(-3
)n-1
-gyel kell megszorozni, s az így kapott számokat kell összeadni. Tehát például az
121
‾
szám értéke
9-6+1=4.
Bizonyítsuk be, hogy a
-3-as alakú számrendszerben is egyértelmű az egész számok felírása: minden egész szám egyértelműen írható fel ilyen alakban.
Feladat: 18.20. (S)
Adva van az
n természetes számnál kisebb s egymástól különböző pozitív számoknak egy sorozata, adva van továbbá egy másik ugyanilyen tulajdonságú sorozat. Bizonyítandó, hogy ha a két sorozat elemeinek együttes száma legalább
n, akkor található a két sorozatnak egy-egy eleme, melyeknek összege éppen
n. (Kürschák verseny, 1953. [
176])
Feladat: 18.21. (M)
Anna kiválasztott néhány egész számot és megállapította, hogy ezek összesen
k darab különböző maradékot adnak
n-nel osztva, Barna is kiválasztott néhány egész számot és megállapította, hogy ezek
l darab különböző maradékot adnak
n-nel osztva. Tudjuk, hogy
k+l>n. Bizonyítsuk be, hogy van egy-egy olyan szám Annánál és Barnánál, amelyek összege osztható
n-nel.
Vagy másképp fogalmazva:
Anna kiválasztott
k darab maradékosztályt mod
n, Barna kiválasztott
l darab maradékosztályt mod
n. Tudjuk, hogy
k+l>n. Bizonyítsuk be, hogy van egy-egy olyan maradékosztálya Annának és Barnának, amelyek összege a 0 maradékosztály.
Feladat: 18.22. (SM)
*
Legyen
p egy tetszőleges prímszám és bizonyítsuk be, hogy van olyan
x és
y egész szám, amelyre
x2
+
y2
+1 osztható
p-vel.
Megjegyzés. Ebből a tételből bebizonyítható az a másik nevezetes tétel, hogy bármely egész szám felírható négy négyzetszám összegeként. A bizonyítás szintén használja a skatulyaelvet, egy meglehetősen ,,cseles" formában. Erről olvashatunk Erdős Pál és Surányi János
Válogatott fejezetek a számelméletből c. könyvében ([
173] 246-251. oldal).
Megjegyzés. A
18.22. feladat bizonyítása során beláttuk, hogy az első
(p+1)/2 nem-negatív szám négyzete mind különböző maradékot ad
p-vel osztva. Másrészt nyilvánvaló, hogy
i és
-i négyzete ugyanazt a maradékot adja
p-vel osztva, és hogy azonos maradékosztályban levő számok négyzetei is azonos maradékosztályban vannak. Ezzel beláttuk, hogy
pontosan
(p+1)/2 ,,kvadratikus maradék" van, vagyis olyan maradékosztály, amelyben van négyzetszám. Ez azt is jelenti, hogy ha eltekintünk a 0 maradékosztálytól, akkor ugyanannyi (nevezetesen
(p-1)/2) kvadratikus maradék van
modp, mint kvadratikus nem-maradék. Erre szükségünk lesz a következő feladatban. Összefoglaljuk:
Definíció. Legyen
p egy prímszám. Az
a egész számról akkor és csak akkor mondjuk, hogy
kvadratikus maradék a
p modulusra nézve, ha van olyan
x egész szám, amelyre
x2
-a osztható
p-vel. Ha ilyen
x egész szám nincsen, akkor
a-t a
p modulusra nézve kvadratikus nem-maradéknak mondjuk. Ha nem okoz félreértést, a ,,
p modulusra nézve" kitételt elhagyjuk.
Ha
a kvadratikus maradék, akkor az
amodp maradékosztály minden eleme az.
Bebizonyítottuk, hogy pontosan
(p+1)/2 olyan maradékosztály van, amelynek elemei kvadratikus maradékok, vagyis ha eltekintünk a nullától, akkor ugyanannyi kvadratikus maradék és kvadratikus nem-maradék van egy adott prím modulusra nézve.
Feladat: 18.23. (M)
Bizonyítsuk be, hogy ha
p prímszám, akkor
a) két mod
p kvadratikus maradék szorzata kvadratikus maradék;
b) egy-egy mod
p kvadratikus maradék és kvadratikus nem-maradék szorzata kvadratikus nem-maradék;
c) két mod
p kvadratikus nem-maradék szorzata kvadratikus maradék.
Megjegyzés. A feladat állításai együtt azt mondják ki, hogy a kvadratikus maradékok és nem-maradékok hasonlóan viselkednek, mint a valós számok között a pozitív és a negatív számok. Egy másik analógia, ha azt mondjuk, hogy úgy viselkednek, mint a valós és a képzetes számok, csak azzal a különbséggel, hogy itt minden szám vagy ,,valós", vagy ,,képzetes".
Feladat: 18.24. (SM)
Nyilvánvaló, hogy ha
α irracionális szám, akkor bármely pozitív egész
n számhoz van olyan
m/n nevezőjű tört, amely
α-tól kevesebb, mint
1/2n-nel tér el. Kérdés azonban, hogy nem lehet-e ennél jobban is megközelíteni egy tetszőleges irracionális számot. Dirichlet bizonyított egy tételt, amelyből következik, hogy itt a kettes szám helyett akármilyen nagyobb számot is írhatunk. Mint a
Skatulyaelv c. fejezet bevezetőjében említettük, a tétele bizonyításához ő használta először - legalábbis kimondva és hangsúlyosan - a skatulyaelvet. Mi most ennek a tételnek csak a következő alakjával foglalkozunk:
* Legyen
α egy irracionális szám,
n tetszőleges pozitív egész. Ekkor létezik olyan
n-nél nem nagyobb pozitív
b egész szám és hozzá egy
a egész szám, amelyre igaz, hogy az
a/b tört csak
1/bn-nél kevesebbel tér el
α-tól.
Ezt a tétel a skatulyaelv nagyon egyszerű alkalmazásával Riesz Frigyes bizonyította (l. [
177]. 176sk.). Vajon hogyan?
Feladat: 18.25. (SM)
Bizonyítsuk be, hogy Dirichlet tételéből (l. a
18.24. feladatot) következik, hogy bármely irracionális
α számhoz végtelen sok olyan
n pozitív egész nevezőjű tört létezik, amely
1/
n2
-nél jobban megközelíti
α-t.
Feladat: 18.26. (SM)
Jelöljük
||x||-gal az
x valós szám eltérését a hozzá legközelebbi egész számtól. Bizonyítsuk be, hogy minden
x valós számhoz végtelen sok olyan
n pozitív egész van, amelyre
||nx||<1/n.
Feladat: 18.27. (SM)
*
Adott egy
p prímszám és adott
p darab különböző pozitív egész:
a1
,
a2
,…,
ap
. Tekintjük az összes
i,j=1,2,…,p számpárra az
ai
/(
ai
,
aj
) számot. Bizonyítandó, hogy ezek közül a legnagyobb legalább
p.
Megjegyzés. Az állítást
p prímszámok helyett
tetszőleges
n számra is ki lehet mondani. Ez volt Graham nevezetes sejtése, amelyet (elég nagy
n-ekre) Szegedi Márió bizonyított be még egyetemista korában 1985-ben.
Feladat: 18.28. (SM)
*
Tekintsünk 1997 különböző pozitív egészt, amelyek közül bármely tíznek ugyanaz a legkisebb közös többszöröse. Maximálisan hány szám lehet közöttük, amelyek páronként relatív prímek (azaz közülük semelyik kettőnek sincs egynél nagyobb közös osztója)? (OKTV, 1997.)
Feladat: 18.29. (M)
a) Bizonyítsuk be, hogy az
1,2,3,…,18 számok közül akárhogyan választunk ki kilencet, a kiválasztott számokból képzett kéttagú összegek között lesz két egyenlő!
b) Bizonyítsuk be, hogy
n>8 esetén az
1,2,3,…,2n számok közül akárhogyan választunk ki
n darabot, a kiválasztott számokból képzett kéttagú összegek között lesz két egyenlő!
Vö. Arany Dániel-verseny, 1999H.
Feladat: 18.30. (M)
* 2001 darab különböző pozitív egész számról tudjuk, hogy a számok szorzatának pontosan 2000 darab különböző pozitív prímosztója van. Bizonyítsuk be, hogy a 2001 darab szám közül kiválasztható egy vagy több úgy, hogy azok szorzata négyzetszám legyen (vagy az egy kiválasztott szám maga négyzetszám)! (Arany Dániel-verseny, 2001H)
Feladat: 18.31. (SM)
*
Bizonyítandó, hogy
nk+1 egész szám közül kiválasztható
n+1, amelyek közül mindegyik osztható a következővel, vagy kiválasztható
k+1, amelyek közül egyik sem osztható semelyik másikkal. ([
173], 240. oldal.)