Feladat: 1.11.
[
188]
Adottak az
a1
,
a2
,…,
a3
n egész számok, és képezzük belőlük az összes
ai
-
aj
különbséget (
i<j). Bizonyítsuk be, hogy az így kapott
3n(3n-1)/2 különbség közül legfeljebb
3
n2
nem osztható hárommal. (Arany Dániel verseny, 1977/K, döntő)
Megoldás: 1.11
1. megoldás.
Osszuk be a számokat a hármas maradékuk szerint három csoportba, legyen
k a hárommal oszthatók száma,
l a hárommal osztva egy maradékot adók száma és
m a hárommal osztva
-1 maradékot adók száma. Az egy csoportban levők különbsége osztható hárommal, a különböző csoportokban levőké nem, tehát pontosan
kl+lm+km olyan különbség van, amelyik nem osztható hárommal. Tudjuk, hogy
k+l+m=3n, és azt kell bizonyítani, hogy
kl+lm+km≤3
n2
=(k+l+m
)2
/3. Ebből hárommal való szorzás és rendezés után az ismert
kl+lm+km≤
k2
+
l2
+
m2
egyenlőtlenséget kapjuk.
Egyenlőség csak
k=l=m=n esetén van.
2. megoldás.
Azt tudjuk, hogy a gráf pontjai három csoportba sorolhatók úgy, hogy az egy csoportba tartozó pontok között nem fut él. Vagyis három részre vághatók úgy, hogy a három rész egy-egy független pontrendszert alkosson.