7. NODAĻA

DIVDIMENSIONĀLĀ INDUKCIJA

Aplūkosim vispirms uzdevumu, kuram attiecībā uz šīs nodaļas saturu būs tāda pati loma kā 2. nodaļai (atsevišķo apgalvojumu pakāpeniska pierādīšana) attiecībā uz 3.-6. nodaļu saturu (vispārīgu apgalvojumu pierādīšana ar matemātisko indukciju).

63. piemērs. Telpā novilktas n plaknes. Nekādas divas no šīm nav plaknēm nav paralēlas, nekādas trīs neiet caur vienu taisni un nekādas četras neiet caur vienu punktu. Pierādīt, ka tās sadala telpu daļās.

Šis uzdevums ir grūts. Risināsim vispirms šim uzdevumam analogus uzdevumus taisnes un plaknes gadījumā (t.i., viendimensijas un divdimensiju telpā).

63.1. piemērs. Uz taisnes atzīmēti n punkti. Pierādīt, ka tie sadala taisni n+1 daļās.

Pierādījums ir acīmredzams.

63.2. piemērs. Plaknē novilktas n taisnes; nekādas divas no šīm taisnēm nav paralēlas un nekādas trīs neiet caur vienu punktu. Pierādīt, ka tās sadala plakni daļās.

Izdarīsim to ar indukciju.

Bāze. Ja n=1, apgalvojuma pareizība ir acīmredzama.

Pāreja k k+1. Pieņemsim, ka apgalvojums ir patiess k taišņu gadījumā. Aplūkosim k+1 taisnes. Izraudzīsimies kaut kādas k taisnes no tām. Tad pēc induktīvā pieņēmuma izraudzītās k taisnes sadala plakni daļās.

Pievienosim atlikušo taisni a. Pēc uzdevuma nosacījumiem taisnes akrustpunkti ar izraudzītajām k taisnēm ir dažādi, tāpēc šie krustpunkti taisni asadala k+1 daļās. Pēc induktīvā pieņēmuma izraudzītās k taisnes sadala plakni daļās. Dažas no šīm plaknes daļām divos apgabalos sadala kāda no taisnes a daļām (to skaits ir k+1). Tāpēc, novelkot (k+1)-o taisni, plaknes apgabalu skaits palielinās par k+1. Līdz ar to k+1 taisnes sadala plakni daļās, kas arī bija jāpierāda.

Tagad atrisināsim 63. piemēra uzdevumu.

Bāze. Ja n=1, apgalvojums acīmredzot ir patiess.

Pāreja k k+1. Pieņemsim, ka apgalvojums patiess k plakņu gadījumā. Apskatīsim k+1 plaknes un izraudzīsimies kaut kādas k no tām. Pēc induktīvā pieņēmuma izraudzītās k plaknes sadala telpu apgabalos.

Pievienosim atlikušo plakni . Pēc uzdevuma nosacījumiem starp plaknes šķēluma taisnēm ar izraudzītajām k plaknēm nav paralēlu taišņu un nekādas trīs no šīm taisnēm neiet caur vienu punktu. Tāpēc šķēluma taisnes (to skaits ir k) plakni sadala daļās. Izraudzītās k plaknes sadala telpu daļās. Dažas no šīm telpas daļām plaknes kāda no daļām sadala 2 apgabalos, tāpēc, novelkot (k+1)-o plakni, telpas apgabalu skaits palielinās par . Tārad k+1 plaknes sadala telpu

daļās., kas arī bija jāpierāda.

Uzskatot punktu par 0-dimensiju telpu un ņemot vērā, ka taisne ir 1-dimensiju telpa, plakne- 2-dimensiju telpa, varam teikt, ka ir atrisināts šāds vispārīgs uzdevums: cik daļās n dažādas (k-1)-dimensiju telpas sadala k-dimensiju telpu, ja nekādas divas no (k-1)-dimensiju telpām nav paralēlas, nekādas trīs nešķeļas pa vienu (k-2)-dimensiju telpu un nekādas četras nešķeļas pa vienu (k-3)-dimensionālu telpu (k=1, 2, 3).

Grafiski šo uzdevumu var attēlot ar divdimensiju telpas lenti, kurā ir 3 joslas (41. zīm.).

41. zīm.

Līdz šim aplūkotos vispārīgos apgalvojumus mēs apzīmējām ar A(n), B(n) utt., tādejādi norādot, ka parametrs ir tikai viens- tas ir n. Šim parametram piešķirot konkrētas vērtības 1, 2, 3, …, ieguvām atsevišķus apgalvojumus A(1), A(2), A(3),… .

Tomēr dažkārt šāda pieeja izrādās pārāk vienkāršota.

64. piemērs Pierādīt, ka

visiem naturāliem n un k. Vienādības keisajā pusē ir k saskaitāmo summa, kurā katrs saskaitāmais ir n pēc kārtas ņemtu naturālu skaitļu reizinājums: pirmajā summas loceklī pirmais reizinātājs ir 1, otrajā- 2, trešajā- 3, …, k-jā loceklī- k.

Protams, šo apgalvojumu var uzskatīt par vispārīgu apgalvojumu A(n) ar parametru n. Tad apgalvojums A(1) ir šāds: , bet A(2)- šāds: . Kā redzams, apgalvojumi A(1), A(2),…kļūst arvien sarežģītāki, ja palielina parametra n vērtību. Patiesībā šie apgalvojumi nemaz nav atsevišķi apgalvojumi, jo tie ir atkarīgi no summas locekļu skaita k, t.i., apgalvojumi A(1), A(2), … ir vispārīgi apgalvojumi ar parametru k. Tāpēc diez vai izdosies pierādīt apgalvojumu A(n) ar indukciju pēc n.

Pamēģināsim tomēr to izdarīt.

Bāze. Pārbaudīsim, vai apgalvojums A(1) "" ir patiess. Šo apgalvojumu var pierādīt vai nu ar matemātisko indukciju, vai arī, izmantojot aritmētiskās progresijas locekļu summas formulu. (Izdarīt to patstāvīgi.)

Pāreja. Pieņemsim, ka A(m)- patiess apgalvojums, un pierādīsim, ka arī A(m+1) ir patiess apgalvojums; ģeometriski tas nozīmē rūtiņu aizkrāsošanas shēmu . (Induktīvās pārejas formulējumā izraudzījāmies burtu m, nevis k, jo k ir saskaitāmo skaits aplūkojamā summā.)

Pieņemsim tātad, ka

(1)

Jāpierāda, ka

(2)

Šo induktīvo pāreju pierādīt ir ļoti grūti. Tiešām, kā pierādīt vienādību (2), izmantojot ienādību (1)? Vienādības (1) kreisā puse neietilpst vienādības (2) kreisajā pusē ne kā reizinātājs, ne kā saskaitāmais; arī citu iespēju izmantot vienādību (1) pat pēc diezgan ilgām pārdomām atrast neizdodas.

Varbūt kāds no lasītājiem būs veiksmīgāks, bet mēs pamēģināsim rīkoties citādi. Jau atzīmējām, ka apgalvojumi A(1), A(2), A(3), …, kurus iegūst no vispārīgā apgalvojuma A(n), piešķirot parametram n konkrētas vērtības, ir sarežģīti vispārīgi apgalvojumi ar parametru k, un tātad katrs no tiem ir atsevišķu apgalvojumu apvienojums. Tas nozīmē, ka pierādāmo vispārīgo apgalvojumu var "sadalīt" vēl vienkāršākos apgalvojumos nekā A(1), A(2), … . Kā to izdarīt?

Pierādāmās vienādības abas puses ir atkarīgas gan no saskaitāmo skaita k tās puses summā, gan arī no reizinātāju skaita n katrā šīs summas loceklī, tātad aplūkojamais vispārīgais apgalvojums ir apgalvojums ar diviem parametriem; apzīmēsim to ar A(k; y). Ievietojot parametru vietā konkrētas vērtības, iegūstam atsevišķus apgalvojumus. Tā piemēram, ja n=3, k=2, iegūstam apgalvojumu

"".

Kā šādu apgalvojumu attēlot grafiski? Ja vispārīgais apgalvojums bija ar vienu parametru, mēs to attēlojām ar bezgalīgu lenti . Vispārīgu apgalvojumu ar diviem parametriem var attēlot ar plaknes kvadrantu (divdimensiju "lenti") (42. zīm.). Katra rūtiņa atbilst atsevišķam apgalvojumam, ko iegūst no vispārīgā apgalvojuma, piešķirot parametriem n un k noteiktas vērtības. Piemēram, rūtiņa, kas atrodas trešajā rindiņā un ceturtajā kolonā, atbilst parametru vērtībām k=3, n=4, t.i., atsevišķajam apgalvojumam A(3; 4).

Mūsu uzdevums- pierādīt visus atsevišķos apgalvojumus, resp., aizkrāsot visas rūtiņas. Padomāsim, kā grafiski attēlojas uzsāktais neveiksmīgais uzdevuma risinājums ar indukciju pēc n.

Vispirms mēs pierādījām apgalvojumu A(n), ja n=1. A(1) ir vispārīgs apgalvojums ar parametru k. Tā kā esam šo apgalvojumu pierādījuši, tad bezgalīgajā divdimensiju "lentē" drīkstam aizkrāsot visas tās rūtiņas, kas atbilst parametru vērtībām n=1, k- jebkurš naturāls skaitlis, t.i., drīkstam aizkrāsot pirmo kolonu (43. zīm.)

42. zīm.

43. zīm.

Pierādīt induktīvo pāreju : "no tā, ka apgalvojums pareizs parametra n vērtībai m, secinām, ka tas pareizs arī parametra vērtībai m+1" neizdevās- tas bija pārāk grūti.

Ja pāreja (t.i., A(m)A(m+1)) būtu pierādīta, mēs drīkstētu aizkrāsot visu otro kolonu (katra tās rūtiņa ir pa labi no pirmās kolonas, bet pirmās kolonas visas rūtiņas jau ir aizkrāsotas), pēc tam visu trešo kolonu utt., līdz kamēr aizkrāsots būtu viss kvadrants. Bet vai visu kvadrantu nevarētu nokrāsot, aizkrāsojot rūtiņas citā secībā?

44. zīm.

Protams, varētu! Tā, piemēram, vispirms varētu aizkrāsot visu pirmo rindiņu. Ja mums būtu tiesības aizkrāsot katru rūtiņu, kas atrodas zem aizkrāsotās rūtiņas , tad varētu aizkrāsot visu otro rindiņu, pēc tam visu trešo rindiņu utt. Lai šādā secībā drīkstētu aizkrāsot kavdranta rūtiņas, jāpierāda atbilstošā indukcijas bāze un pāreja.

Pamēģināsim to izdarīt.

Lai aizkrāsotu 1. rindiņu, jāpierāda apgalvojums A(1,n), t.i., jāpierāda, ka

visiem nN .

Acīmredzams, ka šī vienādība ir pareiza. Tātad drīkstam aizkrāsot kvadranta pirmo rindiņu (44. zīm.).

Tagad pierādīsim šādu induktīvo pāreju: ja apgalvojums A(k; y) ir patiess ar parametra k vērtību m, tad tas ir patiess arī ar parametra k vērtību m+1. Ģeometriski šo pāreju var attēlot ar shēmu .

Pieņemsim, ka A(m,n) ir patiess apgalvojums, t.i., ka

Tad

t.i., apgalvojums A(m+1, n) ir patiess. Induktīvā pāreja pierādīta, līdz ar to pierādīts arī vispārīgais apgalvojums A(k, n).

Kā redzams, ja vispārīgais apgalvojums satur vairākus parametrus, tad nebūt nav vienalga, pēc kura mainīgā cenšamies izdarīt induktīvo pāreju: pēc viena mainīgā pierādīt pāreju var būt ļoti grūti, pēc otra- pavisam viegli.

Aplūkosim vēl vienu vispārīga apgalvojuma A(k, n) pierādīšanas iespēju. Pieņemsim, ka apgalvojums A(k, n) ir patiess, ja k=1 vai n=1, t.i., patiesi ir apgalvojumi A(1, n) un A(k, 1), un ka esam pierādījuši induktīvo pāreju, kas attēlojama ar shēmu

Tādā gadījumā vispārīgais apgalvojums A(k, n) ir patiess. Tiešām, tā kā A(1, n) un A(k, 1) ir patiesi apgalvojumi, tad drīkstam aizkrāsot 45. zīmējumā attēlotā kvadranta pirmo rindiņu un pirmo kolonu.

Izmantojot induktīvo pāreju, pārējās rūtiņas tiks aizkrāsotas šādā secībā: A(2, 2), A(3, 2), A(2, 3), A(4, 2), A(3, 3), A(2, 4), A(5, 2), A(4, 3), A(3, 4), A(2, 5), A(6, 2), … .

Skaidrs, ka tā tiks aizkrāsots viss kvadrants, tātad vispārīgais apgalvojums A(k,n) ir pierādīts.

No teiktā iegūstam šādu secinājumu: ja indukcijas bāze un induktīvā pāreja ģeometriski attēlojas ar shēmu, kas dod iespēju aizkrāsot visas kvadranta rūtiņas, tad dotā uzdevuma risināšanai šī shēma ir derīga.

45.zīm.

65. piemērs. Pierādīt, ka n(n+1)(n+2)…(n+k-1) dalās ar k! (kN, nN, k!=123…k).

Izmantojot tikko aplūkoto indukcijas shēmu, izdarīt to patstāvīgi.

Nakamajā piemērā divdimensionālā indukcija tiek lietota sarežģītākā situācijā: bāze jāpierāda nevis vienai, bet vairākām parametra vērtībām, turklāt bāzes pierādījumā arī jālieto (viendimensionālā) indukcija.

66. piemērs. m dažāda nosaukuma grāmatas, katra n eksemplāros saliktas uz m galdiņiem tā, lai uz katra galdiņa būtu n grāmatas. Pierādīt, ka lasītājs var paņemt no katra galdiņa pa vienai grāmatai tā, lai viņam būtu dažāda nosaukuma grāmatu pilns komplekts.

Ja n=1, apgalvojums acīmredzot ir patiess: katra no m dažādo nosaukumu grāmatām ir vienā eksemplārā, un tās novietotas uz m galdiņiem, uz katra galdiņa pa vienai grāmatai.

Pierādīsim, ka apgalvojums ir patiess, ja n=2.

m dažāda nosaukuma grāmatas, katra 2 eksemplāros, saliktas uz m galdiņiem tā, ka uz katra galdiņa ir divas grāmatas. Pierādīt, ka laītājs var paņemt no katra galdiņa pa vienai grāmatai tā, lai viņam būtu dažāda nosaukuma grāmatu pilns komplekts.

Pierādīsim šo apgalvojumu ar indukciju pēc m.

Bāze. Ja m=1, apgalvojuma pareizība ir acīmredzama.

Pāreja"<kk". Pieņemsim, ka apgalvojums ir patiess visām m vērtībām, kas mazākas nekā k. Aplūkosim k grāmatu gadījumu. Paņemsim no kāda galdiņa g₁ vienu grāmatu, piemēram, grāmatu a₁. Pieņemsim, ka otra grāmata, kas atrodas uz galdiņa g₁, ir a_2, Otrs grāmatas a₂ eksemplārs atrodas uz kāda galdiņa g₂. Paņemsim grāmatu a₂ no galdiņa g₂. Uz g₂ atrodas vēl kāda grāmata a_3. Otrs grāmatas a₃ eksemplārs atrodas uz galdiņa g₃. Paņemsim grāmatu a₃ no galdiņa g₃ utt. Šādi turpinot, nonāksim pie galdiņa g_s, uz kura paliek tāda pati grāmata kā tā, kas palika uz pirmā galdiņa g₁ (pierādīt to patstāvīgi). No pirmajiem s galdiņiem ir paņemts pa vienai grāmatai, turklāt tās visas ir dažādas; paņemto grāmatu otrie eksemplāri atrodas uz šiem pašiem s galdiņiem. Ja s=k, apgalvojums k grāmatu gadījumā ir pierādīts; ja s<k, tad vēl nepaņemtās k-s grāmatas, katra divos eksemplāros, saliktas uz atlikušajiem k-s galdiņiem, pa 2 grāmatām uz katra galdiņa. Tā kā k-s<k, tad pēc induktīvā pieņēmuma no šiem galdiņiem, paņemot pa vienai grāmatai no katra galdiņa, var savākt atlikušo s-k grāmatu pilnu komplektu. Līdz ar to induktīvā pāreja pierādīta, un tātad apgalvojums patiess, ja n=2.

Uzdevumā dotais vispārīgais apgalvojums un jau pierādītie divi gadījumi (kad n=1, n=2) attēloti 46. zīmējumā.

Tagad pierādīsim induktīvo pāreju, kuras ģeometriskais attēlojums ir šāds: .

Pieņemsim, ka apgalvojums ir patiess, ja n=k un ja n=k+1. Aplūkosim gadījumu, kad n=k+2. Pamatojoties uz indukcijas bāzi, pierādīsim vispirms šādu l e m m u.

Ja m grāmatas, katra k+2 eksemplāros, novietotas uz m galdiņiem, k+2 grāmatas uz katra galdiņa, un ja no katra galdiņa var paņemt pa vienai grāmatai tā, kā prasīts uzdevumā, tad to pašu var izdarīt arī pēc tam, kad kaut kādas (vienalga, kuras) divas grāmatas apmainītas vietām.

46. zīm.

Tiešām, izvēlēsimies pirms divu grāmatu apmaiņas pa vienai grāmatai no katra galdiņa tā, lai būtu atlasīts dažāda nosaukuma grāmatu pilns komplekts. Pēc šīs izvēles visu m grāmatu atlikušie k+1 eksemplāri paliek uz m galdiņiem- k+1 grāmatas uz katra galdiņa. Pēc induktīvās hipotēzes atkal varam izvēlēties pa vienam sējumam no katra galdiņa tā, kā prasīts uzdevumā; pēc šīs izvēles visu m grāmatu atlikušie k eksemplāri paliek uz m galdiņiem- k grāmatas uz katra galdiņa. Pēc induktīvās hipotēzes tādu pašu grāmatu atlasi varam atkārtot vēlreiz.

Tātad pirms divu grāmatu apmaiņas vietām mēs no galdiņiem varam atlasīt trīs grāmatu komplektus saskaņā ar uzdevuma prasībām. Vismaz vienā no atlasītajiem komplektiem nebūs neviena no abām apmainītajām grāmatām, tāpēc šo grāmatu komplektu varēs atlasīt arī pēc divu grāmatu apmaiņas vietām- lemma pierādīta.

No lemmas viegli secināt pierādāmā apgalvojuma patiesumu, ja n=k+2. Tiešām, ja katras grāmatas visi k+2 eksemplāri novietoti uz viena galdiņa, tad acīmredzot grāmatas var izvēlēties tā, kā uzdevumā prasīts. Mainot grāmatas vietām pa pāriem, varam iegūt grāmatu jebkuru sadalījumu uz galdiņiem pa k+2 sējumiem uz katra galdiņa; saskaņā ar lemmu arī šiem sadalījumiem prasītā grāmatu izvēle ir iespējama.

Uzdevums atrisināts.

Nākamais piemērs vispārina 3.§. 22. piemēru; sk. Arī 140.- 142. uzdevumu un 7.§. literatūras apskatu.

! 67. piemērs. Pierādīt, ka jebkuriem diviem naturāliem skaitļiem v un k eksistē tāds naturāls skaitlis N(v, k), ka ir spēkā īpašība:

ja telpā doti N(v, k) punkti, ik divi dažādi punkti savienoti ar līniju vienā no dotajām k krāsām, katra līnija satur tikai divus no dotajiem punktiem- savus galapunktus, un dažādām līnijām kopēji var būt tikai galapunkti, tad eksistē v tādi punkti, kurus savieno līnijas vienā un tajā pašā krāsā.

(Izmantojiet grafu teorijas terminoloģiju, apgalvojumu var formulēt šādi.

Katriem v un k eksistē tāds N(v, k), ka pilnā grafā ar N(v, k) virsotnēm, kurā katra šķautne ir vienā no dotajām k krāsām, atradīsies pilns apakšgrafs ar v virsotnēm, kura visas šķautnes ir vienā un tajā pašā krāsā.)

Bāze. 3. § 22. piemērā pierādīta skaitļa N(v, k) eksistence, ja v=3. Viegli saprast, ka N(2, k)=2; var uzskatīt, ka N(1, k)=1- visas līnijas (tādu nemaz nav) ir vienā un tajā pašā krāsā. Skaidrs arī, ka skaitlis N(v, 1)=v ir ar vajadzīgajām īpašībām.

Pierādāmais vispārīgais apgalvojums un jau pierādītie apgalvojumi, kad v=3, v=2, v=1, k=1, attēloti 47. zīmējumā. Iedomāsimies uz brīdi, ka esam pierādījuši arī skaitļa N(v,2) eksistenci, t.i., pierādījuši apgalvojumu ar k=2, jeb ģeometriski, aizkrāsojuši arī otro rindiņu (48. zīm.).

47. zīm.

48. zīm.

Pāreja Pieņemsim, ka k-1 krāsām apgalvojums ir patiess, un pierādīsim, ka tas ir patiess arī k krāsām; ģeometriski induktīvā pāreja attēlojama šādi: .

Pierādīsim, ka skaitlis N(v, k)=N(max(v, N(v, k-1)), 2) ir ar uzdevumā minētajām īpašībām. (Ar max(x, y) saprotam lielāko no skaitļiem x un y.)

Tiešām, pieņemsim, ka doti N(max(v,N(v,k-1)),2) punkti un ik divus punktus savieno līnija kādā no dotajām k krāsām. Vienu no šīm krāsām apzīmēsim ar ; visu citu krāsu līnijas uz laiku aizstāsim ar jaunas krāsas līnijām. Tad N(max(v, N(v, k-1)),2) punktus pa pāriem savieno divu krāsu ( un ) līnijas, tāpēc saskaņā ar pieņēmumu par N(v, 2) eksistenci atradīsies max(v, N(v, k-1)) punktu, kas visi savā starpā savienoti ar vienas krāsas ( un ) līnijām. Ja visi šie punkti savienoti ar krāsas līnijām, tad meklējamos v punktus esam atraduši, jo punktu skaits nav mazāks kā v. Ja visi šie punkti, kuru skaits nav mazāks par kā N(v, k-1), savienoti ar krāsas līnijām, atjaunojam līnijām iepriekšējās krāsas; tā kā šo krāsu skaits ir k-1, tad saskaņā ar indukcijas hipotēzi starp N(v, k-1) punktiem varēs atrast v punktus, kas savienoti ar vienas krāsas līnijām. Induktīvā pāreja ir pierādīta.

Atliek pierādīt skaitļu N(v, 2) eksistenci.

Pierādīsim šādu vispārīgu apgalvojumu:

katriem diviem naturāliem skaitļiem m un n eksistē tāds naturāls skaitlis M(m,n), ka pastāv īpašība: ja ik divi dažādi no dotajiem M(m,n) punktiem savienoti ar līniju vienā no divām dotajām krāsām un tā, kā norādīts 67. piemēra nosacījumos, tad var atrast vai nu m punktus, kuru savstarpējai savienošanai nav izmantotas krāsas līnijas, vai arī n punktus, kuru savstarpējai savienošanai nav izmantotas krāsu līnijas.

Pierādīsim šo apgalvojumu ar matemātisko indukciju.

Acīmredzot var ņemt M(1,n)=M(m,1)=1: tā kā vienīgais punkts pats par sevi vispār nav savienots ar līniju, tad nav izmantotas ne , ne krāsas līnijas. Ģeometriskā ilustrācija redzama 49. zīmējumā.

Pierādīsim tagad induktīvo pāreju, kas ģeometriski attēlojama šādi , t.i., pierādīsim, ka no skaitļu M(m-1,n) un M(m,n-1) eksistences izriet skaitļa M(m,n) eksistence.

Tiešām, M(m,n)=2max(M(m-1,n), M(m,n-1)) (pierādīt to patstāvīgi)

Induktīvā pāreja pierādīta. Viegli saprast, ka tā dod tiesības aizkrāsot visu kvadrantu 49. zīmējumā.

49. zīm.

Lai pabeigtu 67. piemēra pierādījumu, atliek ievērot, ka varam ņemt N(v,2)=M(v,v).

Uzdevumi paškontrolei VII

134. (Špernera lemma.) Tetraedra virsotnes apzīmētas ar cipariem 1, 2, 3 un 4. Tetraedrs sadalīts trijstūra piramīdās tā, ka katrām divām piramīdām vai nu nav kopēju punktu, vai arī ir kopēja virsotne, vai kopēja šķautne (bet ne šķautnes daļa), vai kopēja skaldne (bet ne skaldnes daļa). Piramīdu virsotnes arī apzīmētas ar cipariem 1, 2, 3 un 4, pie tam virsotneskas atrodas uz dotā tetraedra šķautnes, apzīmētas ar kādu no cipariem, kas uzrakstīti šīs šķautnes galos, bet virsotnes, kas atrodas uz dotā tetraedra skaldnes,- ar kādu no cipariem, kas uzrakstīti šīs skaldnes virsotnēs.

Pierādīt, ka eksistē vismaz viena darījuma piramīda, kuras visas virsotnes apzīmētas ar dažādiem cipariem.

*135. (Tēma skolēnu zinātniskajai biedrībai.) Pamēģiniet vispārināt 63. piemēra beigās minēto piezīmi lielākam dimensiju skaitam k.

136. Pierādīt, ka

1. Doti 2ⁿ naturāli skaitļi x₁, x₂ ,…x₂ⁿ. Izveidojam no tiem 2ⁿ jaunus skaitļis x₁-x_2, x₂-x_{3, …,}x₂ⁿ_-1-x₂^{n ,} x₂^n-x1, no šiem skaitļiem pēc tāda paša likuma- vēl 2ⁿ jaunus skaitļus, utt. Pierādīt, ka kādā solī iegūsim 2ⁿ nulles.

138. Vai 137. uzdevumā pierādītais rezultāts ir spēkā, ja

1. x₁, x₂ ,…x₂^n- racionāli skaitļi;
2. x_1, x₂ ,…x₂^n- iracionāli skaitļi;
3. šo skaitļu skaits nav divnieka naturāla pakāpe, bet kaut kāds naturāls skaitlis?

139. (G. Eņģeļa uzdevums.) Funkcijas f(k,l) argumenti ir veseli nenegatīvi skaitļi, f(0,0)=1 un visām pieļaujamām k un l vērtībām ir pareizas vienādības

Pierādīt, ka

1. f(k,k)=(-1)^kk!;
2. ;
3. f(k,l)=0, ja neeksistē tāds vesels nenegatīvs m, ka l=k-3m ( uzskata, ka 0!=1).

*140. Pierādīt 67. piemēra rezultātu, neizmantojot matemātiskās indukcijas metodi.

141. (L. Kliesmete.) Pierādīt šādu teorēmu, kas vispārina 67. piemēra rezultātu: ja telpā doti bezgalīgi daudzi punkti, ik divi no tiem savienoti ar līniju vienā no dotajām k krāsām, tad var atrast bezgalīgi daudzus punktus, kas visi savienoti ar vienas un tās pašas krāsas līnijām.

*142. Pierādīt 67. piemēra rezultāta šādu vingrinājumu (Ramseja vispārīgā teorēma):

katriem natrurāliem skaitļiem r, v₁, v₂, …, v_k eksistē naturāls skaitlis N(r, v₁, v₂, …, v_k), kuram piemīt īpašība: ja aplūko kopu S, kas sastāv no n elementiem, un visas tās apakškopas, kuras sastāv no r elementiem (sauksim tās par r-apakškopām) sadala k grupās, tad vai nu eksistē tāda S apakškopa, kas sastāv no v₁ elementiem un kuras visas r-apakškopas pieder pirmajai grupai, vai arī eksistē tāda S apakškopa, kas sastāv no v₂ elementiem un kuras visas r-apakškopas pieder otrai grupai, …, vai arī eksistē tāda S apakškopa, kas sastāv no v_k elementiem un kuras visas r-apakškopas pieder k-tajai grupai.

Viegli saprast, ka 67. piemēra rezultāts ir šīs teorēmas speciāls gadījums, ja r=2 (visas r-apakškopas ir punktu pāri), k- krāsu skaits, bet v₁=v₂=…=v_k=v.

143. (Erdeša un Sekereša teorēma.) Pierādīt, ka katram naturālam skaitlim n var atrast naturālu skaitli N(n) ar īpašību: starp plaknes jebkuriem N(n) punktiem, no kuriem nekādi 3 neatrodas uz vienas taisnes, var atrast n punktus, kas ir izteikta n-stūra virsotnes.

*144. Pierādīt, ka, izmantojot 143. uzdevuma apzīmējumus, N(n)>2^n-2.

*145. (Neatrisināta matemātiska problēma.) Katram naturālam n atrast minimālo N(n) (N(n)- 143. uzdevumā minētais skaitlis).

Ir zināms, ka min N(4)=5, min N(5)=9, min N(6)=17.

*146. (Tēma skolēnu zinātniskajai biedrībai.) Plaknē novilktas n taisnes. Cik daļās šīs taisnes var sadalīt plakni atkarībā no to savstarpējā novietojuma?

Atrisināt līdzīgu uzdevumu arī par telpu, kuru sadala n plaknes.

*147. Plakni daļās sadala n taisnes. Nekādas divas no šīm taisnēm nav paralēlas, un nekādas trīs taisnes neiet caur vienu punktu. Pierādīt, ka pie katras taisnes pieguļ vismaz viens trijstūris.

Kāds ir mazākais šo trijstūru skaits? (Skaitām tikai tos trijstūrus, kas nepastāv no vairākiem dalījuma apgabaliem.)

*148. Pierādīt 65. piemēra apgalvojumu, neizmantojot matemātisko indukciju.

ĪSS LITERATŪRAS APSKATS.

66. piemēra uzdevums saistīts ar Kēninga-Holla teorēmu par dažādiem pārstāvjiem, kurai ir ļoti liela nozīme kombinatorikā; sk. [45], 5. N

67. piemērā un 140.- 142. uzdevumā .apskatītās problēmas ietilpst t.s. Ramseja teorijā. Šai teorijā ietilpst rezultāti, kas garantē, ka, pietiekami bagātu struktūru (piemēram, pietiekami liela grafa šķautņu kopa) sadalot dotā skaitā daļu (katru šķautni krāsojot kādā no dotajām k krāsām), vismaz vienā no šīm daļām ietilpst apakšstruktūra ar vajadzīgajām īpašībām (atradīsies cik patīk liels pilns grafs, kam visas šķautnes ir vienā krāsā). Piemēram, viens no Ramseja teorijas rezultātiem ģeometrijā skan šādi: ja plaknes punkti nokrāsoti 3 krāsās, tad atradīsies divi vienas krāsas punkti, kas atrodas 1 cm attālumā viens no otra.

67. piemēra risinājumā izmantojām skaitļu M(m,n) eksistenci. Jebkuriem naturāliem m un n eksistē mazākais no skaitļiem M(m,n); to apzīmē ar R(m,n) un sauc par Ramseja skaitli.

Pašreiz ir zināmas tikai šādu Ramseja skaitļu vērtības:

R(3,3)=6; R(3,4)=9; R(3,5)=14; R(4,4)=18; R(3,6)=18; R(3,7)=23.

Bez tam ir zināms, ka, 41R(5,5)+<67 un 25R(4,5)29, kā arī dažas līdzīgas nevienādības.

Lai pierādītu, ka, piemēram, R(3,3)=6, jāpierāda divi apgalvojumi:

1. ja ik divus no 6 punktiem savieno ar līniju vienā no divām dotajām krāsām, tad atradīsies 3 punkti, kas savienoti ar vienas un tās pašas krāsas līnijām;
2. ja ik divus no 5 punktiem var savienot ar līniju vienā no divām dotajām krāsām tā, ka nekādi 3 punkti nav savienoti ar vienas un tās pašas krāsas līnijām.

Ramseja skaitļu meklēšana ir laikam gan pats populārākais uzdevums mūsdienu kombinatorikā; par tā dažādiem variantiem un vispārinājumiem sk., piemēram, [46]. Daži Ramsleja skaitļu vispārinājumi izraisa nepieciešamību lietot trīsdimensionālu (un pat vēl ielāka dimensiju skaita) matemātisko indukciju.