30  Globaalit argumentit

30.1 Johdanto

Joissakin kombinatoriikan tehtävissä idea on katsoa kokonais­kuvaa. Saatetaan esimerkiksi ”summata kaikki”. Tällaisia menetelmiä kutsutaan globaaleiksi ideoiksi. Globaalin menetelmän vasta­kohta on lokaali menetelmä, jossa tutkitaan vain pientä osaa ongelmasta kerrallaan.

Globaalius ja lokaalius ovat pikemminkin ajatus­työ­kaluja, joista on hyötyä joissain tilanteissa, kuin tarkkoja luokitteluja. Kyseessä on siis veteen piirretty viiva, mikä tekee konseptin oppimisesta¹ vaikeaa.

Alla esitetään esimerkkejä, jotka demonstroivat näitä ajatuksia.

30.2 Esimerkki­tehtäviä

Tehtävää voi visualisoida ruudukkona, jossa on seitsemän saraketta ja yhtä monta riviä kuin kilpailijoita. Raksi kertoo, että kisaaja on ratkaissut tehtävän.

Tehtävän ratkeaa seuraavasti: Olkoot $x_1, x_2, \ldots , x_7$ niiden kisaajien määrät, jotka ratkovat tehtävät $1, 2, \ldots , 7$ (eli kussakin sarakkeessa olevien raksien määrät). Olkoot $y_1, y_2, \ldots , y_n$ kunkin kisaajan ratkaisemien tehtävien määrät (eli kullakin vaaka­rivillä olevien raksien määrät). Tiedetään, että $y_i \ge 3$ ja $x_j \le 3$ kaikilla $i$ ja $j$. Lisäksi tiedetään, että $$x_1 + x_2 + \ldots + x_7 = y_1 + y_2 + \ldots + y_n.$$ Tästä saadaan, ettei $n$ voi olla liian suuri: vasen puoli on enintään $21$ ja oikea puoli on vähintään $3n$, joten $n \le 7$.

Lokaali lähestymis­tapa olisi tutkia jonkin pienen alueen lukuja ja tapaus­käsittelyllä todistaa, että sieltä löytyy halutunlainen ruutu. Tämä vaatii paljon tapaus­käsittelyä: esimerkiksi seuraavassa $3 \times 4$ -ruudukossa yhdelläkään luvulla ei ole haluttua ominaisuutta, eli tutkittavan alueen pitää olla suurempi (ja tapauksia olisi siten hyvin monta).

Globaali lähestymis­tapa on ovelampi. Oletetaan, että väite ei päde. Täten jokaisella ruudulla on enintään kolme naapuria, joissa on sitä suurempia lukuja.

Toisaalta ruuduilla on (ruudukon reunoja lukuun ottamatta) kahdeksan naapuria, joten voisi kuvitella, että ruuduilla on keskimäärin neljä naapuria, joissa on suurempi luku.

Nämä ehdot eivät tunnu yhteensopivilta. Tämän saa formalisoitua laskemalla asioita. Piirretään ruudusta $A$ nuoli sen naapuri­ruutuun $B$, jos ruudun $A$ luku on pienempi kuin ruudun $B$. Tiedämme oletuksen nojalla, että jokaisesta ruudusta lähtee enintään kolme nuolta, eli nuolia on enintään $3 \cdot 100 \cdot 100$.

Toisaalta nuolia on paljon, koska jokaisen kahden naapuri­ruudun välillä on nuoli. Pysty­suunnassa olevia nuolia on $99$ per pysty­rivi eli yhteensä $99 \cdot 100$. Vaaka­suunnassa nuolia on sama määrä. Molempiin kahdesta eri vino­suunnasta osoittaa $$\begin{eqnarray} & & 1 + 2 + 3 + \ldots + 98 + 99 + 98 + \ldots + 3 + 2 + 1 \\ &=& \frac{99 \cdot 100}{2} + \frac{98 \cdot 99}{2} = 99 \cdot 99 \end{eqnarray}$$ nuolta. Nuolia on siis $$2 \cdot 99 \cdot 100 + 2 \cdot 99 \cdot 99 = 2 \cdot 199 \cdot 99 > 3 \cdot 100 \cdot 100,$$ mikä on risti­riita.

Tehtävä on vaikea, joten paljastetaan aluksi vastaus: maksimi­määrä kaaria on $50 \cdot 50 = 2500$ ja tämän saavuttaa verkko, jossa on $50$ solmua toisella puolella ja $50$ solmua toisella ja eri puolien solmut on yhdistetty toisiinsa kaarella. (Tämän voi keksiä tutkimalla pieniä tapauksia.)

Tehtävässä on annettu verkolle lokaali ominaisuus (minkä tahansa kolmen solmun välillä on enintään kaksi kaarta) ja tästä halutaan globaali ominaisuus (kaarien määrä on enintään $2500$). Lokaalit lähestymis­tavat, kuten ”yritetään osoittaa, että mistä tahansa solmusta lähtee enintään näin monta kaarta” eivät anna riittävän hyviä rajoja. Yritetään globaaleja ideoita.

Ensimmäisenä mieleen voisi tulla seuraava idea: Tutkitaan kaikkia ${100 \choose 3}$ kolmen solmun joukkoa. Jokaisessa niistä on enintään kaksi kaarta, eli yhteensä kaaria tulee enintään $2{100 \choose 3}$. Jokainen kaari esiintyy $98$ eri kolmiossa, eli sama kaari tulee laskettua $98$ kertaa. Täten kaarien määrä on enintään $$\frac{2{100 \choose 3}}{98} = \frac{100 \cdot 99}{3} = 3300.$$

Tämä on liian huono raja. Mistä huonous johtuu? Ongelma on siinä, että kaikissa kolmen solmun joukoissa ei ole kahta kaarta. Esimerkiksi optimaalisesta ratkaisusta voidaan valita kolme solmua samalta puolelta. Näiden solmujen välillä ei ole yhtäkään kaarta.

Tästä syystä on järkevää käydä solmu­kolmikoiden sijasta läpi kaaria ja summata asioita niiden kautta.

Valitaan jokin kaari, joka yhdistää kaksi solmua $A$ ja $B$. Solmuilla $A$ ja $B$ ei ole yhteisiä naapureita annetusta ehdosta johtuen. Täten solmujen $A$ ja $B$ asteiden summa on enintään $100$: muihin $98$ solmuun lähtee solmuista $A$ ja $B$ enintään yksi kaari, ja lisäksi $A$:n ja $B$:n välillä oleva kaari kasvattaa asteiden summaa kahdella.

Täten $$\sum_{\text{v\"alill\"a } A-B \text{ on kaari}} \deg(A) + \deg(B) \le 100E,$$ missä $E$ on verkon kaarien määrä. Huomataan, että kullakin solmulla $V$ termi $\deg(V)$ esiintyy vasemman puolen summassa yhteensä $\deg(V)$ kertaa, joten epäyhtälön voi kirjoittaa muotoon $$\sum_{V \text{ on solmu}} \deg(V)^2 \le 100E.$$ Tätä summaa saadaan arvioitua käyttämällä Epäyhtälöitä-tekstissä esitettyä QM-AM-epäyhtälöä: $$\sum_{V \text{ on solmu}} \deg(V)^2 \ge \frac{1}{100}\left(\sum_{\text{solmut } V} \deg(V)\right)^2 = \frac{1}{100}(2E)^2,$$ missä käytettiin tietoa siitä, että asteiden summa on kaksi kertaa kaarien määrä. Täten $$\frac{1}{25}E^2 \le 100E,$$ eli $E \le 2500$.

Idea: Valitaan suuri $n$ ja valitaan satunnainen turnaus. Tämä toimii.

Ratkaisu: Valitaan sellainen turnaus, jossa jokaisen pelin voittaja ratkaistaan heittämällä kolikkoa. Osoitetaan sitten, että haluttu ehto toteutuu suurella todennäköisyydellä (kun $n$ on suuri). Tämä riittää: jos ei olisi yhtäkään halutunlaista turnausta, niin todennäköisyys onnistumiselle olisi nolla.

Valitaan jotkin viisi turnauksen pelaajaa. Millä todennäköisyydellä jokin tietty kuudes pelaaja voittaa heidät kaikki? Todennäköisyys tälle on $$\left(\frac{1}{2}\right)^5 = \frac{1}{32}.$$ Todennäköisyys sille, ettei tämä kuudes pelaaja voita heitä kaikkia on siis $31/32$. Täten todennäköisyys sille, ettei kukaan muu $n-5$ pelaajasta voita kaikkia näistä viidestä pelaajasta on $$\left(\frac{31}{32}\right)^{n-5}.$$ Oleellista on, että tämä todennäköisyys on hyvin lähellä nollaa (kyseessähän on eksponentti­funktio, jonka kanta­luku on alle yksi).

Nyt todennäköisyys sille, että on olemassa vähintään yksi viiden pelaajan joukko, jolle halutunlaista kuudetta henkilöä ei löydy, on enintään $${n \choose 5}\left(\frac{31}{32}\right)^{n-5},$$ koska näitä viiden hengen joukkoja on ${n \choose 5}$.

Yllä oleva todennäköisyys on edelleen hyvin pieni (kun $n$ on suuri): se on polynomi kertaa eksponentti­funktio, jonka kanta­luku on alle yksi. Siis jos $n$ on riittävän suuri, on kyseinen luku esimerkiksi alle $50\%$. Tämä tarkoittaa, että $n$ pelaajan satunnaisella turnauksella on yli $50$ prosentin todennäköisyydellä haluttu ominaisuus, joten erityisesti näitä turnauksia on vähintään yksi.