6. NODAĻA

PASTIPRINĀTU APGALVOJUMU PIERĀDĪŠANA.

PARALĒLĀ INDUKCIJA

Pieņemsim, ka mums jāpaceļ uz 1 m augsta paaugstinājuma kravas saiņi, kuru masas 50 kg, 100 kg, 150 kg, 200 kg un 300 kg. Mūsu rīcībā ir svira ar plecu attiecību 1:1, pie tam mūsu pašu masa ir 75 kg. Turklāt saini, kas pacelts kādā noteiktā augstumā, tūlīt pēc tam drīkst piestiprināt tam sviras galam, uz kuru mēs spiežam, lai ar tā palīdzību paceltu nākošo saini (skaidrs, ka iepriekš pacelais sainis tad nolaidīsies atpakaļ).

Pirmo saini 1 m augstumā mēs apceltu bez grūtībām. Piestiprinot to sviras galam, uz kuru spiežam, izdotos pacelt vajadzīgajā augstumā otro saini; ar tā palīdzību varētu pacelt trešo saini, ar trešā palīdzību- ceturto. Tomēr piekto saini pacelt neizdotos, jo 200 kg+75 kg=275 kg<300 kg.

Ja tā pati krava būtu sadalīta saiņos, kuru masa ir 70 kg, 110 kg, 160 kg, 210 kg un 250 kg, tad ar iepriekš aplūkoto paņēmienu bez grūtībām varētu pacelt uz paaugstinājuma smagāko saini; šajā brīdī visi citi saiņi atkal atrastos apakšā. Tad mēs līdzīgi paceltu 210 kg smago saini, pēc tam- 160 kg smago saini utt. Ievērosim, ka, ceļot šādi sadalītas kravas saiņus, katru reizi jāceļ lielāks smagums nekā pirmā sadalījuma gadījumā, bet var izmantot arī smagāku atsvaru.

Pierādījumus, kuros izmantota matemātiskās indukcijas metode, var salīdzināt ar aprakstīto procesu: katrs jau pierādītais atsevišķais apgalvojums tiek izmantots par induktīvo hipotēzi (jau pacelto smagumu izmanto kā atsvaru), lai pierādītu nākošo atsevišķo apgalvojumu (paceltu nākošo smagumu).

Izrādās, ka arī šajā gadījumā iespējama līdzīga situācija, kā smagumu pacelšanas uzdevumā: doto vispārīgo apgalvojumu ar matemātiskās indukcijas metiodi pierādīt nav iespējams, bet apgalvojumu, no kura izriet dotais apgalvojums ("spēcīgāku" apgalvojumu), - ir iespējams pierādīt. Acīmredzot tā var notikt tad, ja "spēcīgākajā" apgalvojumā pierādījuma grūtības ir vienmērīgāk sadalītas starp atsevišķiem apgalvojumiem, kurus tas satur.

Aplūkosim piemērus.

59. piemērs. Pierādīt, ka katram naturālam n ir pareiza nevienādība

(1)

Mēģināsim pierādīt šo apgalvojumu ar matemātisko indukciju.

Bāze. Ja n=1, tad nevienādība ir pareiza, jo 1<2.

Pāreja. Pieņemsim, ka .

Jāpierāda, ka arī . Diemžēl nav saskatāms, kā to varētu izdarīt; saskaņā ar induktīvo hipotēzi zināms, ka summa mazāka nekā 2, bet nav zināms, par cik šī summa atšķiras no 2- vairāk vai mazāk kā par .

Līdzīgas grūtības rodas, mēģinot izmantot citas indukcijas shēmas.

Šīs grūtības arī norāda, kā vajadzētu izmainīt mūsu apgalvojumu, lai izmainīto apgalvojumu varētu pierādīt ar matemātisko indukciju: apgalvojums jāpārveido tādā formā, lai tas saturētu arī informāciju par to, cik liela ir nevienādības kreisās puses atšķirība no labās puses.

Pierādīsim, ka visiem naturāliem n ir pareiza nevienādība

(2)

Pāreja. Pieņemsim, ka nevienādība

(3)

ir pareiza. Lai pierādītu nevienādību

(4)

pietiek pierādīt, ka

(5)

jo, saskaitot nevienādības (3) un (5), iegūst nevienādību (4). Viegli pārbaudīt, ka nevienādība (5) ir pareiza; tātad vispārīgais apgalvojums (2) pierādīts. Tā kā visiem n, tad pierādīts, ka patiess arī apgalvojums (1).

60. piemērs. Apzīmēsim

Pierādīt, ka a_k+1>b_n, ja n1.

Pierādīsim spēcīgāku nevienādību a_n+1>2b_n.

Pāreja. Pieņemsim, ka a_k+2=3^a_k+1>3^2b_k=9^b_k=2,25^b_k4^b_k>24^b_k=2b_k+1;

to arī vajadzēja pierādīt.

61. piemērs. Bezgalīgā rūtiņu papīra lapā n rūtiņas nokrāsotas melnā krāsā, visas

pārējās rūtiņas ir baltas. Ik pēc minūtes visas rūtiņas vienlaikus tiek pārkrāsotas pēc šāda likuma: katru rūtiņu nokrāso tādā krāsā, kādā tieši pirms šīs pārkrāsošanas bija vairākums no trim rūtiņām - pati apskatāmā rūtiņa un tās augšējais un labējais kaimiņš. (Ja divas vai trīs no šīm rūtiņām bija baltas, tad apskatāmā rūtiņa kļūst balta, pretējā gadījumā- melna.)

Pierādīt, ka, pietiekami ilgi turpinot šādu pārkrāsošanu, melno rūtiņu vairs nebūs.

Pierādīsim precīzāku apgalvojumu - ka melno rūtiņu vairs nebūs pēc n pārkrāsošanām.

Bāze. Ja n=1, tad pirmajā pārkrāsošanā vienīgā melnā rūtiņa tiek nokrāsota baltā krāsā.

Pāreja. Pieņemsim, ka šis apgalvojums patiess, ja n<k, un pierādīsim, ka tas patiess, ja n=k.

Apskatīsim papīra loksni, kurā k melnas rūtiņas. Apzīmēsim ar T taisnstūri, kura malas iet pa rūtiņu līnijām, kurš satur visas melnās rūtiņas un kuram gan pie kreisās malas, gan pie apakšējās malas ir vismaz pa vienai melnai rūtiņai. Skaidrs, ka nevienā pārkrāsošanā ārpus taisnstūra T melnā krāsā nebūs jānokrāso neviena rūtiņa.

Ar T₁ apzīmēsim taisnstūri, kuru iegūst no T, atmetot visas kreisā malējā stabiņa rūtiņas. Tad T₁ satur mazāk nekā k melnas rūtiņas. Tā kā melnas rūtiņas, kas atrodas taisnstūra T kreisajā malējā stabiņā, neietekmē melno rūtiņu parādīšanos pēc pārkrāsošanas taisnstūrī T₁, tad no induktīvā pieņēmuma izriet, ka jau agrāk nekā pēc k pārkrāsošanām taisnstūra T₁ iekšpusē melnā krāsā nebūs neviena rūtiņa.

Līdzīgi pierāda, ka taisnstūrī, ko iegūst no T, atmetot visas apakšējās rindiņas rūtiņas, jau agrāk nekā pēc k pārkrāsošanām nepaliks neviena melna rūtiņa.

Tātad jau agrāk nekā pēc k pārkrāsošanām vienīgā rūtiņa, kas varbūt būs palikusi melnā krāsā, atradīsies taisnstūra T kreisajā apakšējā stūrī. Jau nākamajā pārkrāsošanā tā tiks nokrāsota baltā krāsā, tātad ne vēlāk kā pēc k pārkrāsošanām visas rūtiņas būs baltā krāsā.

Atcerēsimies pirmos pierādījumus ar matemātisko indukciju trešajā paragrāfā. Grafiski tos varēja attēlot šādi (34. zīm.):

34. zīm.

Novietosim kolonas vertikāli (35. zīm.):

35. zīm.

Iedomāsimies, ka katra iesvītrotā rūtiņa ir daudzstāvu nama būvei paredzēts vienstāva bloks. Tādā gadījumā, izmantojot šo indukcijas shēmu, mēs ceļam namu ar bezgalīgi daudziem stāviem šādā veidā: Vispirms uzbūvējam pirmo stāvu (iesvītrojam pirmo kvadrātiņu) un pēc tam, pamatojoties uz to, ka k-tais stāvs jau uzbūvēts, būvējam (k+1)-o stāvu. Turklāt (k+1)-ā stāva būvē mēs varam izmantot tikai jau uzbūvēto k-to stāvu (dažos aplūkotajos variantos- k-to un (k-1)-o stāvus vai visus jau uzbūvētos stāvus), bet neko vairāk.

Tomēr reālā būvē tā nenotiek. Ceļot daudzstāvu namu, rīkojas tā: vispirms uzstāda celtni - ne sevišķi augstu. Pēc tam ar šī celtņa palīdzību uzbūvē mājai pirmos stāvus. Tad celtni piestiprina pie jau uzbūvētajiem stāviem un paaugstina; ar paaugstināto celtni uzbūvē mājai atkal jaunus stāvus. Pēc tam celtni piestiprina šiem uzbūvētajiem stāviem un atkal paaugstina, bet pēc tam savukārt uzbūvē jaunus stāvus mājai utt.

Kā redzams, šādā procesā tiek būvēta gan ēka, gan celtnis, kaut arī gala rezultātā mūs interesē vienīgi daudzstāvu nams; celtnis ir tikai palīgs. Daudzstāvu namu bez celtņa uzbūvēt būtu ļoti grūti; "uzbūvēt" uzreiz pašu celtni tā maksimālajā garumā, lai pēc tam ar šī celtņa palīdzību celtu māju, arī būtu gandrīz neiespējami - tam nebūtu kur atbalstīties. Tāpēc māju un celtni būvē pakāpeniski, katrā posmā izmantojot gan jau uzbūvētos mājas stāvus, gan arī jau izveidoto celtņa daļu.

Līdzīga situācija bieži sastopama arī matemātikas uzdevumos.

62. piemērs. Divas skaitļu virknes a₁, a₂, …, b₁, b₂ … veido šādi: a₁=3, b₁=4;

.

Pierādīt, ka visiem naturāliem n ir pareiza vienādība

Pamēģināsim risināt šo uzdevumu ar parasto indukcijas shēmu nn+1. Ja pierādāmo vienādību apzīmē ar A(n), tad A(1) ir apgalvojums

""

Viegli pārliecināties, ka tas ir patiess.

Pieņemsim, ka vienādība A(k) ir pareiza, t.i., ka

;

jāpierāda, ka pareiza ir arī vienādība A(k+1):

.

Pēc dotā

.

Te spriedums apraujas, jo nav zināms, kā izsakāms b_k. Ja b_k izteiksme būtu zināma, spriedumu varētu pabeigt.

Ja visām n vērtībām

(to mēs gribam pierādīt), tad jābūt

Tātad, ja būtu pierādīta vienādība

(apzīmēsim to ar B(n)), tad tālāku šķēršļu nebūtu.

Pamēģināsim šo vienādību pierādīt tāpat, kā mēģinājām pierādīt vienādību A(n)

Ja n=1, tad apgalvojums B(1), t.i., "" ir patiess.

Pieņemsim, ka vienādība B(k) ir pareiza, t.i., ka

.

Pierādīsim, ka tādā gadījumā pareiza ir arī vienādība B(k+1). No b_n definīcijas formulas iegūstam, ka , un atkal esam strupceļā. Mēs taču nezinām, kā izsakāms a_k+1! Tiesa, ir hipotēze, ka

,

bet tā taču nav pierādīta!

Lai pierādītu šo hipotēzi, bija jāatrod b_n, un nu izrādās, ka, lai aprēķinātu b_n, jau iepriekš jāzina, kā izsakāms a_n. Izveidojies "apburtais loks": lai pierādītu vienādību A(n), jābūt pierādītai vienādībai B(n), bet, lai pierādītu B(n), jābūt pierādītai vienādībai A(n).

Izeju no "apburtā loka" dod jauns līdz šim neapskatīts paņēmiens - paralēlā indukcija. Tās būtība ir tāda, ka abus apgalvojumus A(n) un B(n) pierāda ar indukciju virnlaikus.

Ilustrēsim šo paņēmienu, risinot 62. piemēra uzdevumu. Pierādāmā vienādība A(n) ir šāda

Tā būtu pierādīta, ja mēs zinātu, ka pareiza ir vienādība B(n):

.

Bāze. A(1) un B(1) ir pareizas vienādības, jo

.

Pārejas.

1. Ja A(k) un B(k) ir pareizas vienādības, tad pareiza ir arī vienādība a(k+1).

Tiešām, pieņemsim, ka

1. Ja A(k+1) un B(k) ir pareizas vienādības, tad arī B(k+1) ir pareiza vienādība.

Tiešām,

ja

,

tad

Līdz ar to ir pierādīts gan vispārīgais apgalvojums A(n), gan vispārīgais apgalvojums B(n), nN. Visvieglāk to redzēt grafiskajā interpretācijā ar divām bezgalīgām lentēm; viena no tām attēlo vispārīgo apgalvojumu A(n), otra - vispārīgo apgalvojumu B(n), nN (36. zīm.).

36. zīm.

Indukcijas bāze nozīmē, ka abām lentēm drīkst aizkrāsot pirmās rūtiņas (37. zīm.)

37. zīm.

Pirmo induktīvo pāreju grafiski attēlo 38. Zīmējums:

38. zīm.

Otro induktīvo pāreju grafiski attēlo 39. Zīmējums:

39. zīm.

Vai aizkrāsojot rūtiāņas tādā secībā, kā parādīts 38. un 39. zīmējumā, var aizkrāsot visas rūtiņas abās lentēs? Protams, jā. Tā kā aizkrāsotas abas lenšu pirmās rūtiņas, drīkst aizkrāsot 2. rūtiņu augšējā rindā (38. zīm.), bet pēc tam- 2. rūtiņu apakšējā rindā ( 39. zīm.). Tādejādi ir nokrāsota otrā kolonna. Bet tas nozīmē, ka drīkst aizkrāsot trešās kolonnas augšējo rūtiņu un pēc tam- apakšējo rūtiņu. Līdzīgi aizkrāso 4. kolonnu, 5. kolonnu utt. Katra rūtiņa agri vai vēlu tiks nokrāsota.

Atzīmēsim, ka ne vienmēr uzdevuma risinājuma induktīvās pārejas ilustrējamas ar 38. un 39. zīmējumu. Tikpat labi citā uzdevumā pēc indukcijas bāzes pierādīšanas (t.i., pēc 1. kolonnas nokrāsošanas) var būt izdevīgi pierādīt induktīvās pārejas, kas ilustrētas 40. zīmējumā, vai vēl cita veida induktīvās pārejas. Svarīgi ir tikai tas, lai rūtiņu aizkrāsošanas shēma garantētu iespēju aizkrāsot abu lenšu visas rūtiņas (protams, atbilstšās induktīvās pārejas jāpierāda).

40. zīm.

Paralēlā indukcija ir paragrāfa sākumā apskatītās metodes (pierādāmā apgalvojuma aizstāšana ar citu apgalvojumu) variants. Tiešām, viena apgalvojuma A(n) vietā mēs aplūkojam divus apgalvojumus A(n) un B(n) un paralēli pierādām, ka tie ir patiesi, t.i., pierādām, ka viens apgalvojums "A(n) un B(n)" ir patiess. Tas nozīmē, ka patiess ir apgalvojums A(n).

Uzdevumi paškontrolei VI

121. Pierādīt, ka nevienādība , ir pareiza visiem naturāliem n.

122. Dotas bezgalīgi daudzas kartiņas; uz katras no tām uzrakstīts kāds naturāls skaitlis.Ir zināms, ka katram naturālam skaitlim n tieši uz n kartiņām uzrakstīti šī skaitļa dalītāji. Pierādīt, ka skaitlis 2^m ir uzrakstīts uz kādas no kartiņām, ja m- naturāls skaitlis.

123. Visi naturālie skaitļi kaut kā sadalīti n klasēs; katrs skaitlis ietilpst tieši vienā klasē. Pierādīt, ka katru bezgalīgu virkni, kuras elementi ir cipari, var tā sadalīt galīgos posmos, ka visi naturālie skaitļi, kuru decimālais pieraksts ir virknes posms (izņemot varbūt vienu), pieder pie vienas klases.

124. Pierādīt, ka katram naturālam n eksistē tikai galīgs skaits vienādojuma

atrisinājumu naturālos skaitļos.

125. Skaitļu virknes (a_n) un (b_n) definē šādi:

a₁= -10, b₁= -13, a_n+1= -2a_n+4b_n, b_n+1= -5a_n+7b_n.

Pierādīt, ka a_n=2ⁿ-43ⁿ visiem naturāliem n.

126. Pierādīt, ka nevienādība ir pareiza visiem naturāliem n.

127. Pierādīt, ka

1. f_2n=f²_n+1-f²_n-1,
2. f₁f₂+f₂f₃+…+f_2n-1f_2n=f²_2n,

ja f_n - Fibonači skaitļi (sk. 21. lpp.).

128. (Van der Vardena teorēma.) Sadalīsim naturālo skaitļu kopu kaut kādās divās daļās. Pierādīt, ka vismaz vienā no šīm daļām var atrast cik patīk garas aritmētiskas progresijas.

*129. Vai patiess šāds apgalvojums (Van dre Vardena teorēmas pastiprinājums): ja naturālo skaitļu kopa kaut kā sadalīta divās daļās, tad vismaz viena no tām satur bezgalīgu aritmētisku progresiju?

*130. (Neatrisināta matemātiska problēma.) Vai eksistē naturālu skaitļu augoša virkne n₁<n₂<n₃ …, kas apmierina šādus divus nosacījumus:

a) eksistē tāda konstante C, ka katra aritmētiska progresija, kas sastāv tikai no šīs virknes locekļiem, satur ne vairāk kā C locekļus;

b)

(citiem vārdiem, rinda diverģē)?

Profesors Pauls Erdešs par šīs problēmas atrisinājumu izsolījis 2000 dolāru lielu prēmiju.

*131. Pierādīt, ka no skaitļiem var izvēlēties 2ⁿ skaitļus tā, ka nekādi no izraudzītajiem skaitļiem neveido aritmētisku progresiju.

*132. (Neatrisināta matemātiska problēma, tēma Skolēnu zinātniskajai biedrībai.) Dažas no n-stūra virsotnēm jāatzīmē ar melnu krāsu, bet pārējās - ar kādu citu krāsu tā, lai neviena melnā virsotne nebūtu vienādā attālumā no divām citām melnajām virsotnēm un lai melnās virsotnes nebūtu diametrāli pretējas. Noteikt melno virsotņu maksimālo skaitu M(n).

Ja nav iespējams atrast precīzu M(n) izteiksmi, pamēģiniet atrast M(n) vērtības ar n30, kā arī iespējami labākus M(n) ierobežojumus no augšas un no apakšas.

133. Pierādīt, ka cos(nx)=P_n(cos x) un sin (nx)=sin xQ_n-1(cos x), kur Q_k un P_k- k-tās pakāpes polinomi ar veseliem koeficentiem. Piemēram, P₂(t)=2t²-1, jo cos 2x=2cos² x-1; Q₁(t)=2t, jo sin 2x=sin x*2cos x.

ĪSS LITERATŪRAS APSKATS

Matemātikā ļoti bieži vispārīgāku apgalvojumu vieglāk pierādīt nekā atsevišķu apgalvojumu (sk., piemēram rakstu [38]).

Par ļoti lielu skaitļu salīdzināšanu, ja tie pierakstīti ar atkārtotas kāpināšanas palīdzību, sk. [39].

Daudzi interesanti uzdevumi, kas līdzīgi 61. piemērā apskatītajam uzdevumam, atrodami grāmatas [40] 38. nodaļā. Nelielu priekšstatu par nopietnākām problēmām, kas saistītas ar šiem uzdevumiem, var iegūt, izlasot rakstu [41].

123. uzdevuma risinājums atšķiras no citiem ar to, ka tas ir "tīrs eksistences pierādījums": mēs nenorādām nekādu paņēmienu, kā sadalīt ciparu virkni saskaņā ar uzdevuma prasībām, bet tikai pierādām, ka tāda iespēja ir (pareizāk sakot, pierādā, ka nevar būt, ka tādas iespējas nav). Jautājums par šādu pierādījumu vērtību ir klasiskās matemātikas pārstāvju, no vienas puses, un konstruktīvistu un intuicionistu, no otras puses, patstāvīgu diskusiju objekts; sk., piemēram, darbus [42] un [43].

128. uzdevuma risinājumā pierāda, ka jebkuriem naturāliem skaitļiem n₁, n₂, …, n_k eksistē tāds mazākais naturālais skaitlis W(n₁, n₂, …, n_k), ka , sadalot k grupās naturālos skaitļus no 1 līdz W, vai nu pirmā grupa satur aritmētisku progresiju, kuras locekļu skaits ir n₁+1, vai otrā grupa satur aritmētisku progresiju, kurā ir n₂+1 locekļi,…, vai k-tā grupa satur aritmētisku progresiju, kurā ir n_k+1 locekļi. Sos skaitļus W(n₁, n₂, …, n_k) sauc par Van der Vardena skaitļiem; to precīzo vērtību noteikšana ir viens no populārākajiem (un grūtākajiem) mūsdienu kombinatorikas uzdevumiem, kam veltīts milzīgs daudzums rakstu. Lūk, dažas no Van der Vardena skaitļu W(x, y) vērtības (xy):

y \ x	2	3	4	5	6	7	8	9
2	9	18	22	32	46	58	77	97
3		35	55	73
4			178

Bez tam W(2, 2, 2)=27, W(2, 2, 3)=51, W(2, 2, 2, 2)=76.