Normat 58:2, 93–95 (2010) 93
Et kombinatorisk kuriosum
Olav Gebhardt
a
og 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
På grund av att vissa tecken föll bort när denna artikel
publicerades i nummer 2009:4 så publicerar vi den igen här.
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 = 1 og 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.
94 Olav Gebhardt og Marius Overholt Normat 2/2010
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 ≥
(m + k)/2. Siden antall par av kjeder som kan dannes er lik binomialkoeffisienten
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
∈ 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 =
√
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
Normat 2/2010 Olav Gebhardt og Marius Overholt 95
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
og dermed følger
1 −
m
k
kn +
m
k
(n
√
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
.
