HOOFDSTUK 2: DE STELLING VAN RAMSEY 1.a) Bewijs dat n 2(4

HOOFDSTUK 2: DE STELLING VAN RAMSEY
1.a) Bewijs dat n2 (4, 4) ≥ 18 door in een volledige graaf op 17 punten, de punten te
laten corresponderen met de restklassen 0, 1, . . . , 16 (mod 17) en twee punten i, j
door een rode boog te verbinden als i − j = ±1, ±2, ±4, ±8 (mod 17) en anders
door een blauwe boog.
b) Bewijs m.b.v. a) dat n2 (3, 4) = 9.
2.a) Bewijs dat n2 (3, 5) ≥ 14 door in een volledige graaf op 13 punten, de punten the
laten corresponderen met de restklassen 0, 1, . . . , 12 (mod 13), twee punten i, j
door een rode boog te verbinden als i − j = ±1, ±5 (mod 13) en anders door een
blauwe boog, en vervolgens te laten zien dat er geen deelverzameling van 3 punten
is waarvan alle onderlingen bogen rood zijn, en geen deelverzameling van 5 punten
met alle onderlinge bogen blauw.
b) Bewijs dat n2 (3, 5) = 14.
3.a) Bewijs dat n2 (k1 , k2 , k3 ) ≤ n2 (k1 −1, k2 , k3 )+n2 (k1 , k2 −1, k3 )+n2 (k1 , k2 , k3 −1)−1
voor k1 , k2 , k3 ≥ 2.
b) Bewijs dat n2 (k1 , k2 , k3 ) ≤
4.
(k1 +k2 +k3 −3)!
(k1 −1)!(k2 −1)!(k3 −1)! .
Bewijs dat 3k/2 ≤ n2 (k, k, k) ≤ 33k−3 voor k ≥ 3.
5.a) Zij nh = n2 (3, 3 . . . , 3) (h keer). Bewijs dat nh ≤ hnh−1 − h + 2 voor h ≥ 3.
b) Bewijs de volgende verscherping van de Stelling van Schur: zijn h ≥ 2, N ≥ 3h!
natuurlijke getallen. Dan geldt voor elke verdeling van de getallen {1, . . . , N } in
disjuncte niet-lege deelverzamelingen S1 , . . . , Sh dat minstens ´e´en van de verzamelingen Sj getallen x, y, z bevat met x + y = z.
6.
Bewijs de volgende verscherping van de Stelling van Schur: voor elk natuurlijk getal
h ≥ 2 is er een natuurlijk getal N zodat voor elke verdeling {1, . . . , N } in disjuncte
deelverzamelingen S1 , . . . , Sh , er minstens ´e´en verzameling Sj is die verschillende
getallen x, y, z bevat met x + y = z.
Opmerking: in de Stelling van Schur uit het dictaat wordt niet geeist dat x, y, z
verschillend zijn.
Aanwijzing: neem N = n2 (4, . . . , 4) (h keer).
1
7.a) Bewijs dat n1 (q1 , q2 , . . . , qn ) = q1 + · · · + qn − n + 1.
Opmerking: dit is het ladenprincipe van Dirichlet.
b) Bewijs dat er bij elke rij van nm + 1 re¨ele getallen hetzij een deelrij van lengte n + 1
is die monotoon daalt, hetzij een deelrij van lengte m + 1 die monotoon stijgt.
c) Zij V een deelverzameling van {1, 2, . . . , 2n} bestaande uit n + 1 getallen. Bewijs
dat V twee getallen a en b bevat zodat a een deler is van b.
8.
Bewijs dat er in elke symmetrische afstandstabel van 4n−1 plaatsen (met n ≥ 2 ´
of
n plaatsen zijn waarvan alle onderlinge afstanden even zijn, of n plaatsen met alle
onderlinge afstanden oneven.
9.
Bewijs dat 7 ≤ n3 (4, 4) ≤ 19.
Aanwijzing: neem de verzameling {1, 2, 3, 4, 5, 6} en kleur een deelverzameling
van 3 elementen {i1 , i2 , i3 } rood als i1 + i2 + i3 even is en anders blauw.
10.
Bewijs dat er voor elk paar natuurlijke getallen k, m een natuurlijk getal N bestaat
met de volgende eigenschap: onder elke verzameling van N punten in het platte
vlak R2 is er ´
of een deelverzameling van k punten waarvan geen drietal op dezelfde
lijn ligt, ´
of een deelverzameling van m punten die allemaal op dezelfde lijn liggen.
11.
Formuleer en bewijs een analogon van opgave 10 voor verzamelingen punten in de
drie-dimensionale ruimte R3 .
2

Download Report