Dirixle (Göyərçin Yuvası) Prinsipi

Nümunə 1.1 (izah). $13$ nəfərdən ibarət qrupda ən azı iki nəfər mütləq eyni ayda anadan olub. Burada göyərçinlər — $13$ nəfər, yuvalar isə — $12$ aydır.

Nümunə 1.2 (izah). $17$ evli cütlükdən ($34$ nəfərdən) ibarət qrupdan ən azı neçə nəfər seçmək lazımdır ki, seçilənlər arasında mütləq bir ər-arvad cütlüyü olsun?$17$ nəfər seçmək kifayət etməyə bilər: hər cütlükdən yalnız bir nəfərin seçilməsi mümkündür. Lakin $18$ nəfər seçdikdə yuvaların sayı ($17$ cütlük) göyərçinlərdən ($18$ nəfər) az olur, deməli, ən azı bir cütlükdən iki nəfər (həm ər, həm də arvad) seçilmiş olacaq. Cavab: $18$.

Nümunə 2.1 (izah). $25$ alma $3$ uşaq arasında paylanır. Ən çox alma alan uşaq ən azı neçə alma alıb?$\lceil 25/3\rceil = 9$. Doğrudan da, hər uşaq $8$ və ya daha az alma alsaydı, cəmi $24<25$ olardı. ($9$ qiymətinin alınması mümkündür: $9+8+8=25$.)

Nümunə 2.2 (izah). Qutuda $10$ qırmızı, $8$ mavi, $8$ yaşıl və $4$ sarı qələm var. Qaranlıqda ən azı neçə qələm götürməliyik ki: (a) eyni rəngdən ən azı $4$ qələm mütləq olsun; (b) hər rəngdən ən azı bir qələm mütləq olsun; (c) ən azı $6$ ədəd mavi qələm mütləq olsun?(a) Ən əlverişsiz hal: hər rəngdən $3$ qələm çıxır — $12$ qələm və hələ də eyni rəngdən dörd qələm yoxdur. $13$-cü qələm isə mütləq rənglərdən birini dördə çatdırır. Cavab $13$.(b) Ən əlverişsiz hal: bütün qırmızı, mavi və yaşılları götürürük — $10+8+8=26$ qələm, lakin sarı yoxdur. Deməli, növbəti qələm sarı olacaq və cavab $27$-dir.(c) Ən əlverişsiz hal: bütün qeyri-maviləri ($10+8+4=22$) və yalnız $5$ mavi qələmi çıxarırıq — $27$ qələm. Deməli, cavab $28$-dir.

Nümunə 3.1 (izah). İxtiyari seçilmiş $6$ tam ədəd arasında fərqi $5$-ə tam bölünən ən azı iki ədəd mövcuddur.Yuvalar: $5$-ə bölmədən alınan qalıqlar, yəni $\{0,1,2,3,4\}$ — $5$ yuva. Göyərçinlər: $6$ ədəd. Dirixle prinsipinə əsasən iki ədəd eyni yuvaya düşür, yəni eyni qalığı verir. Onda həmin ədədlərin fərqi $5$-ə tam bölünəcəkdir.

Nümunə 3.2 (izah). $1,2,\dots,10$ ədədlərindən ixtiyari $6$-sı seçilir. Sübut edin ki, seçilənlər arasında cəmi $11$ olan ən azı iki ədəd var.Yuvalar — cəmi $11$ olan cütlüklərdir:

$$\{1,10\},\{2,9\},\{3,8\},\{4,7\},\{5,6\}$$

— cəmi $5$ yuva (cütlük). $6$ ədəd seçdiyimizə görə ən azı bir cütün hər iki elementi seçilmiş olacaqdır.

Nümunə 3.3 (izah). $1,2,\dots,100$ ədədlərindən $51$-i seçilir. Sübut edin ki, seçilənlər arasında fərqi $1$ olan (ardıcıl) iki ədəd var.Yuvalar: $\{1,2\},\{3,4\},\dots,\{99,100\}$ — yəni $50$ yuva. $51$ ədəd seçilib, deməli hansısa yuvanın hər iki ədədi seçilmişdir; onların fərqi isə $1$-dir.

Nümunə 3.4 (izah). $1,2,\dots,100$ ədədlərindən $51$-i seçilir. Sübut edin ki, seçilənlər arasında biri digərini tam bölən iki ədəd mövcuddur.Artıq burada qalıq yuvası metodu işləmir. Burada ən uyğun yuva ədədin ən böyük tək bölənidir (tək hissəsidir). İxtiyari $n$ ədədini yeganə şəkildə $n=2^a\cdot q$ kimi göstərə bilərik, burada $q$ tək ədəddir. $1$-dən $100$-ə qədər olan tək ədədlər $1,3,5,\dots,99$ — dəqiq olaraq $50$ ədəddir. Bunları yuva kimi götürək.$51$ ədəd seçildiyinə görə, ən azı ikisinin tək böləni ($q$) eynidir: $n_1=2^{a}q$, $n_2=2^{b}q$. Onda, əgər $a<b$ olarsa $n_1\mid n_2$, əks halda isə $n_2\mid n_1$ alınar.

Nümunə 3.5 (izah). $1,2,\dots,2n$ ədədlərindən $n+1$-i seçilir. Sübut edin ki, onlardan ikisi mütləq qarşılıqlı sadədir.Yuvalar: $\{1,2\},\{3,4\},\dots,\{2n-1,2n\}$ — cəmi $n$ yuva. $n+1$ ədəd seçildiyinə görə ən azı bir yuvanın hər iki üzvü eyni vaxtda seçilib; ardıcıl iki ədədin ƏBOB-u isə həmişə $1$-ə bərabərdir.

Nümunə 4.1 (izah). Tərəfi $1$ olan kvadratın daxilində $5$ nöqtə qeyd olunub. Sübut edin ki, bu nöqtələrdən hər hansı ikisi arasındakı məsafə $\dfrac{\sqrt2}{2}$-dən böyük deyil.Kvadratı tərəfi $\frac12$ olan $4$ bərabər kvadrata bölək. $5$ nöqtə, $4$ yuva — deməli, ən azı bir kiçik kvadratda mütləq iki nöqtə yerləşir. Kiçik kvadratın diametri isə $\frac12\sqrt2=\frac{\sqrt2}{2}$-dir, yəni eyni kvadratdakı nöqtələr bundan uzaq ola bilməz.

Nümunə 4.2 (izah). Tərəfi $1$ olan kvadratın daxilində $51$ nöqtə verilib. Sübut edin ki, onlardan ən azı üçünü radiusu $\frac17$ olan bir dairə ilə örtmək mümkündür.Kvadratı $5\times 5=25$ sayda bərabər kvadrata bölək. $51>2\cdot 25$ olduğuna görə gücləndirilmiş Dirixle prinsipinə əsasən ən azı bir kiçik kvadratda heç olmasa $3$ nöqtə var ($\lceil 51/25\rceil=3$).Bu kiçik kvadratın tərəfi $\frac15$-dir; onun xaricinə çəkilmiş çevrənin radiusu isə

$$r=\frac{1}{5}\cdot\frac{\sqrt2}{2}=\frac{\sqrt2}{10}\approx 0{,}1414 <\frac17\approx 0{,}1429 .$$

Deməli, həmin kiçik kvadratı (və uyğun olaraq içindəki üç nöqtəni) radiusu $\frac17$ olan dairə ilə tam örtmək olar.

Nümunə 4.3 (izah). Tərəfi $2$ olan bərabərtərəfli üçbucağın daxilində $5$ nöqtə qeyd edilib. Sübut edin ki, onlardan hər hansı ikisi arasındakı məsafə $1$-dən böyük deyil.Üçbucağı tərəflərinin orta xətləri vasitəsilə $4$ bərabərtərəfli kiçik üçbucağa bölək; onların hər birinin tərəfi $1$-dir və eyni zamanda diametri də $1$-dir. $5$ nöqtə, $4$ yuva, iddia aydındır.

Nümunə 4.4 (izah). Müstəvidə heç ikisi bir-birinə paralel olmayan $7$ düz xətt çəkilib. Sübut edin ki, onlardan ikisi arasındakı iti bucaq $26^\circ$-dən kiçikdir.Bütün xətləri müstəvinin bir $O$ nöqtəsinə paralel köçürək — paralel köçürmədə bucaqlar dəyişmir. İndi $7$ düz xətt eyni $O$ nöqtəsindən keçir və müstəvini bölür; hər bir xəttin istiqamətini $[0^\circ,180^\circ)$ intervalındakı bir bucaqla ifadə edək.Əgər bu intervalı $7$ bərabər hissəyə bölsək, hər hissə $\frac{180}{7}\approx 25{,}7^\circ$ olardı — amma bu bölgü hər bir hissəyə bir xəttin düşməsinə imkan verir (Dirixle işləmir). Ona görə də $6$ hissəyə bölsək: hər hissə $30^\circ$ edir — lakin bu da bizə tələb olunan $26^\circ$ şərtini vermir.Düzgün yol: intervalı $7$ hissəyə bölürük, lakin məhz $7$ xəttin $7$ fərqli istiqaməti arasındakı qonşu bucaqların ən kiçik fərqinə baxırıq. İstiqamətləri artan sıra ilə $\alpha_1<\alpha_2<\dots<\alpha_7$ şəklində yazaq. Qonşu fərqlərin cəmi (sonuncu $\alpha_7$-dən birinci $\alpha_1$-ə qədər $180^\circ$ tamamlanmaqla birlikdə) dəqiq $180^\circ$-dir və belə $7$ bucaq fərqi mövcuddur. Əgər onların hamısı $26^\circ$ və ya daha böyük olsaydı, cəm $\ge 7\cdot 26=182>180$ olardı — ki, bu da ziddiyyətdir. Deməli mütləq ən azı bir fərq $26^\circ$-dən kiçik olmalıdır.

Nümunə 5.1 (izah). Tutaq ki, $a_1,a_2,\dots,a_n$ ixtiyari $n$ tam ədəddir. Sübut edin ki, onların içərisində ardıcıl gələn bir neçəsinin cəmi $n$-ə tam bölünür.Prefiks (əvvəldən gələn ardıcıl) cəmlərini quraq:

$$S_0=0,\quad S_1=a_1,\quad S_2=a_1+a_2,\quad\dots,\quad S_n=a_1+\dots+a_n .$$

Gördüyümüz kimi bunlar $n+1$ ədəddir. Yuvalar isə — $n$-ə bölmədən alınan qalıqlar çoxluğudur, yəni $n$ yuva var. Dirixle prinsipinə görə elə $i<j$ indeksləri mövcuddur ki, $S_i\equiv S_j \pmod n$. Onda

$$a_{i+1}+a_{i+2}+\dots+a_j = S_j-S_i$$

cəmi mütləq $n$-ə bölünəcəkdir.

Nümunə 5.2 (izah). $2$-yə və $5$-ə bölünməyən ixtiyari $n$ natural ədədinin yalnız $1$ rəqəmlərindən ibarət olan bölünəninin (mislinin) mövcudluğunu isbat edin.Belə bir ardıcıllığa baxaq:

$$1,\quad 11,\quad 111,\quad \dots,\quad \underbrace{11\cdots1}_{n+1}.$$

Bu $n+1$ sayda ədədi $n$-ə bölək; yuvalar $n$ qalıqdır, deməli onlardan ikisi eyni qalığı verir. Onların fərqi mütləq $n$-ə bölünür və fərq aşağıdakı formadadır:

$$\underbrace{1\cdots1}_{j}-\underbrace{1\cdots1}_{i} = \underbrace{1\cdots1}_{j-i}\cdot 10^{\,i}$$

Verilənlərə görə $(n,10)=1$ olduğundan, $n$ ədədi $10^i$ vuruğunu bölə bilməz, deməli $n \mid \underbrace{1\cdots1}_{j-i}$ olar.

Nümunə 5.3 (izah). Koordinat müstəvisində koordinatları tam ədədlər olan $5$ nöqtə verilib. Sübut edin ki, onlardan hər hansı ikisini birləşdirən parçanın orta nöqtəsi də mütləq tam koordinatlıdır.Hər $(x,y)$ nöqtəsi üçün koordinatların tək-cütlüyünə (paritetinə), yəni $(x \bmod 2,\ y \bmod 2)$ cütünə baxaq — cəmi $4$ fərqli imkan var: $(0,0),(0,1),(1,0),(1,1)$. Bunlar bizim yuvalarımızdır. $5$ nöqtə olduğu üçün, ən azı ikisinin hər iki koordinatının cütlüyü eyni olar. Onda həmin nöqtələrin koordinat cəmləri hər iki oxda cüt ədəd olacaq və uyğun olaraq orta nöqtənin $\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right)$ koordinatları da tam ədəd olacaqdır.

Nümunə 5.4 (izah). $\{1,2,\dots,99\}$ çoxluğundan təsadüfi $10$ elementli $X$ altçoxluğu seçilib. Sübut edin ki, $X$-in bir-biri ilə kəsişməyən, boş olmayan və elementlərinin cəmi eyni olan ən azı iki altçoxluğu mövcuddur.Göyərçinlər: $X$-in boş olmayan bütün mümkün altçoxluqları — yəni $2^{10}-1=1023$ ədəd.Yuvalar: hər bir altçoxluğun elementləri cəmidir. Ən böyük mümkün cəm $90+91+\dots+99=945$-dir, ən kiçik cəm isə $1$-dir. Deməli, cəm üçün maksimum $945$ fərqli imkan var.$1023>945$ olduğuna görə elə iki müxtəlif altçoxluq var ki, onların elementlərinin cəmləri eynidir: yəni $A\ne B$ ikən $s(A)=s(B)$. Onlar öz aralarında kəsişə (ortaq elementlərə malik ola) bilərlər — amma biz ortaq elementləri silsək, yəni $A'=A\setminus B$, $B'=B\setminus A$ götürsək, həmin ortaq hissə hər iki çoxluğun cəmindən çıxılacaq və $s(A')=s(B')$ bərabərliyi qorunacaq. $A\ne B$ olduğuna görə $A'$ və $B'$ çoxluqlarının hər ikisi eyni anda boş ola bilməz; cəmləri bərabər olduğu üçün əgər biri boş olarsa, o biri də məcburən boş olmalıdır. Deməli, onların heç biri boş deyil və artıq kəsişmirlər.

Nümunə 6.1 (izah). Müstəvidə $n$ mavi və $n$ qırmızı nöqtə verilmişdir (heç üçü bir düz xətt üzərində deyil). Sübut edin ki, hər bir mavi nöqtəni bir qırmızı nöqtəyə elə birləşdirmək mümkündür ki, alınan cəmi $n$ parça heç vaxt kəsişməsin.Mavi nöqtələri qırmızı nöqtələrə birləşdirməyin müəyyən sonlu sayda üsulu var ($n!$ qədər fərqli eşləşmə). Hər bir uyğunlaşdırma (eşləşdirmə) üsulu üçün $n$ parçanın ümumi (cəm) uzunluğunu hesablayaq və ümumi uzunluğu ən kiçik olan eşləşməni seçək.İddia edirik ki, məhz bu eşləşmədə heç iki parça kəsişmir. Fərz edək ki, seçilmiş eşləşmədə $M_1Q_1$ və $M_2Q_2$ parçaları müəyyən bir $P$ nöqtəsində kəsişir. Onda bu uyğunlaşdırmanı ləğv edib yerinə $M_1Q_2$ və $M_2Q_1$ parçalarını götürək (çarpazlaşdıraq). Üçbucaq bərabərsizliyinə əsasən

$$M_1Q_2 < M_1P+PQ_2,\qquad M_2Q_1<M_2P+PQ_1,$$

bu bərabərsizlikləri topladıqda isə

$$M_1Q_2+M_2Q_1 < (M_1P+PQ_1)+(M_2P+PQ_2)=M_1Q_1+M_2Q_2 .$$

Yəni parçaların ümumi uzunluğu azaldı — bu isə bizim əvvəldə seçdiyimiz eşləşmənin minimal uzunluğa malik olmasına (minimallığına) ziddir. Deməli, ilkin qəbul etdiyimiz kəsişmə əslində yoxdur.

Nümunə 6.2 (izah). $n$ nəfər bir-biri ilə əl sıxaraq görüşür. Sübut edin ki, prosesin istənilən anında eyni sayda adamla əl sıxmış ən azı iki nəfər mütləq var.Hər bir nəfər üçün əl sıxdığı adamların sayı $0$-dan $n-1$-ə qədər müxtəlif qiymətlər ala bilər — görünüşə görə $n$ yuva var və Dirixle dərhal işləmir (çünki adam sayı da $n$-dir). Amma burada mühüm bir detal var: $0$ və $n-1$ qiymətləri eyni anda mövcud ola bilməz (çünki əgər kimsə heç kimlə əl sıxmayıbsa, otaqdakı başqa kimsə hamı ilə əl sıxmış ola bilməz). Deməli, faktiki olaraq aktiv yuvaların sayı maksimum $n-1$-dir, göyərçinlər (insanlar) isə $n$ nəfərdir.