Megoldás: 1.28
Válasszunk ki először két pontot, a közöttük futó él legyen
e=xy, színe legyen 1-es. Nézzük meg, hogy egy harmadik mikor ,,nem illik" e két ponthoz. Nyilván akkor nem, ha valamelyikükkel az 1-es szín köti össze. Mármost a feladat feltételét
x-re alkalmazva azt kapjuk, hogy nem lehet két olyan pont, amellyel
x-et 1-es színű él köt össze. Ugyanígy nem lehet két olyan pont sem, amellyel
y-t 1-es színű él köt össze. Tehát összesen legfeljebb két pont van kizárva, a többi 1989 pontból bármelyiket hozzávehetjük
xy-hoz. Attól nem kell félnünk, hogy az új pontot
x-szel és
y-nal ugyanolyan színű él fogja összekötni, hiszen a feladat feltétele az új pontra is vonatkozik.
Tegyük fel ezek után, hogy találtunk már
k darab pontot, amelyek között futó
k(k-1)/2 él színe páronként különböző. Megint nézzük meg, hány olyan pont van a maradók között, amelyik ,,nem illik" a kiválasztott
k-hoz. Nyilván csak az olyan pontok nem illenek, amelyek a kiválasztott
k pont valamelyikével a
k(k-1)/2 él színe köti össze. Legyen
x a
k pont valamelyike. A feladat feltételét rá alkalmazva azt kapjuk, hogy a ki nem választott pontok között nincsen kettő, amelyikhez azonos színű él futna belőle. Vagyis
x legfeljebb
k(k-1)/2 pontot zár ki. Ha ezt mind a
k pontra végigvisszük, azt kapjuk, hogy összesen legfeljebb
k2
(k-1)/2 pont van kizárva. Ha tehát valamely
k-ra ehhez a számhoz
k-t adva még 1993-nál kevesebbet kapunk, akkor ki tudunk választani egy
k+1-edik pontot, amelyik ,,illik" hozzájuk a feladat értelmében.
Mivel
k+
k2
(k-1)/2
k-val szigorúan monoton növekszik és
16+
162
15/2=1936<1993, 17 megfelelő pontot még ki tudunk választani.