170 Normat 57:4, 170–172 (2009)
Et kombinatorisk kuriosum
Olav Gebhardt
a
and Marius Overholt
b
a
Marikåpeveien 24, 9100 Kvaløysletta
b
Institutt for Matematikk og Statistikk
Universitetet i Tromsø, 9037 Tromsø
marius.overholt@uit.no
Vi tenker oss n perlekjeder, satt sammen av sorte og hvite perler. Alle kjedene har
lengde k. Forutsett at hvert par av kjeder stemmer overens i farge minst m ≥ 0
flere steder enn de ikke stemmer overens. (Kjedene er lagt parallelle på et bord).
Forutsett også at i hver tverrad er det høyst d flere perler av en farge enn av den
andre. Eksempelet under har n =7, k =7, m =1og d =5.
Prøving og feiling med små n og k indikerer at det ikke er så lett å finne ikketrivielle
mønstre av dette slaget. Derfor bør vi kunne utlede restriksjoner på n, m, k og d
som utelukker eksistens. Å bevise restriksjonen
mn
2
+(k − m)n ≤ kd
2
er en oppgave som har en viss didaktisk interesse, fordi den kan løses på to helt for-
skjellige måter; ved et kombinatorisk telleresonnement eller ved enkel lineæralgebra.
I det kombinatoriske beviset starter vi med å feste oppmerksomheten på et
vilkårlig valgt par av perlekjeder. Betegn antall overenstemmelser for paret med a;
da er antall uoverensstemmelser lik k−a. Etter forutsetning er a−(k−a) ≥ m så a ≥
Normat 4/2009 Olav Gebhardt og Marius Overholt 171
(m + k)=2. Siden antall par av kjeder som kan dannes er lik binomialkoesienten
n(n −1)=2 vil det totale antall overensstemmelser for alle par av kjeder være større
enn eller lik
n(n −1)
2
m + k
2
:
Så flytter vi oppmerksomheten til tverradene. I en vilkårlig valgt tverrad betegner
vi antall perler av den farge som det er flest av med s. Hvis det er like mange
av hver farge, betegner s dette felles antallet. Antall perler av motsatt farge i den
samme tverraden blir da n−s. Etter forutsetning er s−(n−s) ≤ d så s ≤ (n+d)=2.
Antall overensstemmelser i denne tverraden blir da
s(s − 1)
2
+
(n − s)(n − s − 1)
2
=
n
2
− n
2
− s(n − s):
Fordi s ≥ n=2 så vokser dette uttrykket når s vokser, og oppnår sin største verdi når
s antar sin største tillatte verdi, som er s = (n + d)=2. Innsetting gir da ulikheten
s(s − 1)
2
+
(n − s)(n − s − 1)
2
≤
n
2
+ d
2
− 2n
4
;
hvor høyre side altså er det høyest mulige antall overensstemmelser mellom par av
perler i en tverrad. Siden det er k tverrader, blir det totale antall overensstemmelser
høyst lik k(n
2
+ d
2
− 2n)=4. Dermed følger ulikheten
n(n − 1)
2
m + k
2
≤ k
n
2
+ d
2
− 2n
4
;
som vi kan forenkle til mn
2
+ (k − m)n ≤ kd
2
.
I det andre beviset bruker vi prikkproduktet i R
k
. Vi skal utlede den ønskede
restriksjonen fra en ulikhet i lineæralgebra: Hvis x
1
; : : : ; x
n
er vektorer i R
k
slik
at x
i
x
j
≥ kx
i
kkx
j
k for 1 ≤ i; j ≤ n med en ikkenegativ konstant , så gjelder
ulikheten
kx
1
+ + x
n
k
2
≥ (1 − )(kx
1
k
2
+ + kx
n
k
2
) + (kx
1
k + + kx
n
k)
2
:
Vi utsetter beviset for denne lineæralgebra-ulikheten og bruker den til å utlede
restriksjonen ovenfor på nytt.
Perlekjedene representeres ved vektorer x
j
2 R
k
for 1 ≤ j ≤ n. Komponentene
i vektorene er lik 1 eller −1 etter som den tilsvarende perlen er sort eller hvit,
respektive. Etter forutsetning er x
i
x
j
≥ m for 1 ≤ i; j ≤ n. Siden kx
i
k = kx
j
k =
p
k følger
x
i
x
j
≥ kx
i
kkx
j
k
med = m=k. Videre er hver komponent til vektoren x
1
+ + x
n
lik overvekten
av en farge over den andre i den tilsvarende tverraden, med positivt fortegn hvis
det er overvekt av sorte perler, med negativt fortegn hvis det er overvekt av hvite
perler. Etter forutsetning er da
kx
1
+ + x
n
k
2
≤ kd
2
172 Olav Gebhardt og Marius Overholt Normat 4/2009
og dermed følger
1 −
m
k
kn +
m
k
(n
p
k)
2
≤ kd
2
ved innsetting i lineæralgebra-ulikheten ovenfor. Forenkling gir så den ønskede re-
striksjonen mn
2
+ (k − m)n ≤ kd
2
.
Det står igjen å vise ulikheten som er brukt. Vi har
kx
1
+ + x
n
k
2
=
X
1≤i≤n
x
i
X
1≤j≤n
x
j
=
X
1≤i,j≤n
x
i
x
j
= kx
1
k
2
+ + kx
n
k
2
+
X
i6=j
x
i
x
j
≥ kx
1
k
2
+ + kx
n
k
2
+
X
i6=j
kx
i
kkx
j
k
= (1 − )(kx
1
k
2
+ + kx
n
k
2
) + (kx
1
k + + kx
n
k)
2
ved velkjente regneregler for norm og prikkprodukt. Merk at hvis nesten er så
stor som 1 så sier ulikheten at hvis alle vektorene x
1
; : : : ; x
n
peker i nesten samme
retning så er lengden til vektoren x
1
+ + x
n
nesten like stor som summen av
lengdene til x
1
; : : : ; x
n
.
