10. NODAĻA

INDUKCIJA ATSEVIŠĶU APGALVOJUMU PIERĀDĪŠANĀ

(INDUKCIJAS METODES PIELIETOJUMI)

Iepriekšējās nodaļās aplūkotās matemātiskās indukcijas shēmas lietojām, lai pierādītu vispārīgus apgalvojumus. Tomēr dažreiz matemātikā indukciju veiksmīgi pielieto arī citos gadījumos, pierādot atsevišķus apgalvojumus.

78. piemērs. Pierādīt nevienādību .

Pirmajā acumirklī nav saprotams, kā sākt risināšanu- neiesim taču aprēķināt reizinājumu nevienādības kreisajā pusē! Bet kā būtu, ja mēģinātu atrast vispārīgu apgalvojumu, kura speciāls gadījums ir pierādāmā nevienādība?

Samērā viegli nonākam pie šādas hipotēzes:

.

(A(n))

(Pierādāmo nevienādību iegūst no šīs nevienādības, ja n=50.) Pierādīt patstāvīgi ar matemātisko indukciju, ka nevienādība A(n) ir pareiza, ja n2 (ja n=1, iegūst vienādību (0,5=0,5), izmantojot 1. teorēmu.

Vispārīgu apgalvojumu dažreiz vieglāk pierādīot nekā atsevišķu apgalvojumu. Acīmredzot tas saistīts ar to, ka vispārīgs apgalvojums informē par būtiskām īpašībām, kas piemīt visiem vispārīgajā apgalvojumā ietilpstošajiem atsevišķajiem apgalvojumiem. Atsevišķā apgalvojumā uzmanība var pievērsties kādai konkrētai, nebūtiskai īpašībai, līdz ar to novirzot risinātāju no racionālākā risināšnas ceļa.

Protams, vajag veiksmīgi izvēlēties pierādāmo vispārīgo apgalvojumu. Piemēram, ja mēs būtu mēģinājuši pierādīt vispārīgu apgalvojumu

(A(n))

tad būtu piedzīvijuši neveiksmi (šis vispārīgais apgalvojums nav patiess, kaut arī tā speciāls gadījums- atsevišķais apgalvojums A(50)- ir patiess).

Aplūkosim dažus līdzīgus piemērus.

79. piemērs. Pierādīt, ka eksistē tāds naturāls skaitlis n, ka n²+1 dalās ar 5¹⁹⁸².

Ar matemātisko indukciju pierādīsim, ka katram naturālam k eksistē tāds n_k, ka n_k²+1 dalās ar 5^k.

Bāze. Ja k=1, tad tāds n₁ ir, piemēram, 7.

Pāreja "kk+1". Pieņemsim, ka esam atraduši tādus naturālus n₁, n₂, …, n_k, ka n_i²+1 dalās ar 5ⁱ visiem i=1, 2, …, k.

Lemma. Ja n²+1 dalās ar 5, tad, dalot n ar 5, atlikumā iegūst 2 vai 3.

Tiešām, ja n=5t, tad n²+1=25t²+1 ar 5 nedalās;

ja n=5t+1, tad n²+1=25t²+10t+2 ar 5 nedalās;

ja n=5t+2, tad n²+1=25t²+20t+5 ar 5 nedalās, bet, dalot n ar 5, atlikums ir 2;

ja n=5t+3, tad n²+1=25t²+30t+10 ar 5 dalās, bet, dalot n ar 5, atlikums ir 3

ja n=5t+4, tad n²+1=25t²+40t+17 ar 5 nedalās.

Lemma ir pierādīta.

Ja n_k=5t+2, tad (n_k+1)²+1=25t²+10 dalās ar 5, un saskaņā ar induktīvo pieņēmumu ar 5^k+1 dalās (n_k²+1)((n_k+1)²+1)=(n_k²+n_k+1)²+1, tātad par n_k+1 var izraudzīties skaitli n_k²+n_k+1

Ja n_k=5t+3, tad (n_k-1)²+1==25t²+20t+5 dalās ar 5, un saskaņā ar induktīvo pieņēmumu 5^k+1 dalās ar (n_k²+1)((n_k--1)²+1)=(n_k²-n_k+1)²+1, tātad par n_k+1 var ņemt skaitli n_k²-n_k+1.

80. piemērs. Pierādīt, ka 1¹⁹⁷⁶+2¹⁹⁷⁶+…+1978¹⁹⁷⁶ dalās ar 1979.

Apzīmēsim 1ⁿ+2ⁿ+…+1978ⁿ=S_n. Pierādīsim, ka S_n dalās ar 1979, ja n1977, n- naturāls.

Bāze. Ja n=1, jāpierāda, ka dalās ar 1979. Tas ir acīmredzams.

Pāreja "<kk". ja k1977. Pieņemsim, ka apgalvojums patiess, ja n=1, 2, …, k-1. Pierādīsim, ka tas patiess, ja n=k. No 50. piemēra risinājuma iegūstam, ka

1979^k+1=C¹_k+1S_k+C²_k+1s_k1+…+C^k_k+1S₁+1979.

Atceroties, ka C¹_k+1=k+1, no šīs vienādības iegūstam

(k+1)Sk=1979k+1-1979)-C2k+1Sk-1-…- Ckk+1

(1)

Tā kā k1977, tad k+11978. No vienādības (1), izmantojot induktīvo pieņēmumu, secinām, ka (k+1). S_k dalās ar 1979. Tā kā 1979 ir pirmskaitlis un k+11978<1979, tad skaitļu (k+1) un 1979 vienīgais kopējais dalītājs ir 1. Tāpēc no tā, ka (k+1)S_k dalās ar 1979, izriet, ka S_k dalās ar 1979, kas arī bija jāpierāda.

81. piemērs. Par rezultātu basketbola spēlē kādā brīdī sauc veselu nenegatīvu skaitļu pāri (m; y), kur mn, m- vadošās komandas iegūtais punktu skaits dotajā brīdī, n- otras komandas iegūtais punktu skaits dotajā brīdī. Pieņemsim, ka soda metieni netiek mesti, bet visi punkti tiek gūti no spēles (katrs precīzs metiens dod divus punktus). Spēli sauc par saistošu, ja nevienā brīdī starpība m-n nepārsniedz 4 punktus. Divas spēles sauc par vienādām, ja to laikā veidojušos rezultātu virknes ir vienādas (neatkarīgi no tā, kura komanda katrā brīdī bijusi vadība), un par dažādām- pretējā gadījumā.

Cik dažādu saistošu spēļu ar gala rezultātu 62:60 iespējams?

Apzīmēsim ar A_n dažādu saistošu spēļu skaitu, kuru gala rezultāts ir 2n:2n, ar B_n- dažādu saistošu spēļu skaitu, kuru gala rezultāts ir 2n:(2n-2), ar C_n- dažādu saistošu spēļu skaitu, kuru gala rezultāts ir 2n:(2n-4). Citu gala rezultātu saistošām spēlēm nevar būt. Viegli sastādīt tabulu, uzskaitot visas iespējamās spēles ar prasītajiem rezultātiem, ja n=1, 2, 3.

n	1	2	3
An	1	2	4
Bn	1	2	4
Cn	0	1	2

Izmantojot sakarības A_n=B_n,B_n=A_n-1+C_n, C_n=B_n-1, pierādīt ar matemātisko indukciju, ka

A_n=2^n-1, B_n=2^n-1, C_n=2^n-2, ja n2.

Tātad saistošu spēļu ar rezultātu 62:60 ir B₃₁=2³⁰.

82. piemērs. Uz papīra lapas uzrakstīti skaitļi 0 un 1. Ja uz lapas uzrakstīti dažādi skaitļi un , tad atļauts uz tās uzrakstīt arī skaitli . Pierādīt, ka uz lapas drīkst uzrakstīt arī skaitli .

Pierādīsim ar indukciju pēc n, ka drīkst uzrakstīt visus racionālos skaitļus , kur 0<m<2², m- naturāls.

Bāze. Ja n=1, jāpierāda, ka uz lapas drīkst uzrakstīt 1/2. Tas ir acīmredzams.

Pāreja "kk+1". Pieņemsim, ka drīkst uzrakstīt visus skaitļus , ja 0<m<2^k, m, kN. Apskatīsim kaut kādu skaitli , kur 0<m<2^k+1, m, kN. Ja m- pāra skaitlis, t.i., m=2m₁, tad , tātad pēc induktīvās hipotēzes to uz lapas drīkst uzrakstīt (jo 0<m₁<2^k). Ja m- nepāra skaitlis, t.i., m=2m₁+1, tad

Tā kā 0<2m₁+1<2^k+1, tad 0<m₁<2^k. Tātad drīkst uzrakstīt pēc induktīvā pieņēmuma. Tā kā 0<m₁+1<2^k+1, tad vai nu drīkst uzrakstīt pēc induktīvā pieņēmuma, vai arī šīs daļas vērtība ir 1, bet skaitlis 1 uz lapas uzrakstīts pēc uzdevuma nosacījumiem. Tātad saskaņā ar uzdevuma nosacījumiem drīkst uzrakstīt arī skaitli .

83. piemērs. Pierādīt, ka naturālos skaitļus no 1 līdz 1982 var uzrakstīt virknē tādā secībā, ka starp jebkuriem diviem naturāliem skaitļiem nav uzrakstīts to vidējais aritmētiskais.

Pierādīsim ar indukciju pēc n, ka šādā veidā var uzrakstīt naturālos skaitļus no 1 līdz 2ⁿ. Tā kā eksistē tāds naturāks k, ka 2^k>1982, tad no šo 2^k skaitļu izvietojuma, izsvītrojot liekos skaitļus, iegūsim skaitļu no 1 līdz 1982 vajadzīgo sakārtojumu virknē.

Bāze. Ja n=1, der, piemēram, sakārtojums 1; 2.

Pāreja kk+1. Pieņemsim, ka pirmos 2^k naturālos skaitļus esam sakārtojuši prasītajā veidā un ieguvuši virkni

Pierādīt, ka pirmo 2^k+1 naturālo skaitļu sakārtojums virknē

.

ir vajadzīgais.

84. piemērs. Burtu galīgu virkni sauc par līdzsvarotu, ja kāds tās sākuma fragments sakrīt ar kādu šīs virknes beigu fragmentu. Piemēram, līdzsvarotas ir virknes abca, ab ab utt.

Pierādīt, ka eksistē burtu galīga virkne, kas kļūst līdzsvarota, pierakstot tai galā jebkuru latviešu alfabēta burtu.

Ar matemātisko indukciju pierādīsim šādu apgalvojumu: jebkurai galīgai burtu kopai A_n=a₁; a₂; a₃;…a₂^{k var konstruēt burtu galīgu virkni, kas kļūst līdzsvarota, pierakstot tai galā jebkuru kopas} A burtu.

Bāze. Ja n=1, kopa A₁ sastāv no viena burta a₁, iegūstam līdzsvarotu virkni a₁a₁.

Pāreja kk+1. Pieņemsim, ka protam konstruēt šādas virknes k burtu kopām. Aplūkosim kopu A_k+1=a₁; a₂; …; y_{n. Pēc induktīvā pieņēmuma, eksistē galīga burtu virkne 12} …_m , kas kļust līdzsvarota, pierakstot tai galā jebkuru no burtiem a₁, a₂, …, a_k.

Aplūkosim burtu virkni

12 … m ak+112 …m

(1)

Pierakstot virknei (1) galā burtu a_k+1, šī virkne kļūst līdzsvarota, jo sakrīt tā pirmā un otrā puse. Pierakstot virknei (1) galā jebkuru no burtiem a₁, a₂, …, a_k, šī virkne kļūst līdzsvarota pēc induktīvā pieņēmuma, jo sakrīt kāds no virknes ₁₂ …_ma_i (i=1, 2, …, k) sākuma faragmentiem ar kādu no tās beigu fragmentiem; tā kā šis sākuma fragments nav visa virkne ₁₂ …_ma_i, tad sakrītošie virknes ₁₂ …_ma_i sākuma un beigu fragmenti ir virknes (1) sākuma un beigu fragmenti.

Uzdevumi paškontrolei X

160. Dots, ka a₁, a₂, …, a_n, …- naturāli skaitļi, pie tam a₂>a₁ un a_n+2=3a_n+1-2a_n visiem naturāliem n. Pierādīt, ka a₁₀₀>2₉₈.

161. lielāks

162. Pierādīt nevienādību

.

163. Dots, ka ir vesels skaitlis. Pierādīt, ka arī x¹⁰²⁴ ir vesels skaitlis.

164. Pierādīt, ka 5^{25sin 25 ir vesels skaitlis, kas nedalās ar 5, ja sin =3/5.}

165. Doti 100 dažādu diametru diski ar caurumiņu vidū. Tie kaut kā uzmaukti uz vertikālas ass. Atļauts noņemt no ass jebkuru daudzumu augšējo disku (varbūt visus), nemainot to kārtību, apgriezt noņemto kaudzīti otrādi un uzmaukt atpakaļ uz ass. Pierādīt, ka, vairākas reizes atkārtojot šo operāciju, diskus uz ass var sakārtot diametru dilšanas secībā, skaitot no apakšas.

166. Svešvalodu fakultātē mācās daudzi studenti. Tieši 50 no viņiem pārvalda angļu valodu, tieši 50- vācu valodu un tieši 50- franču valodu. (Nav teikts, ka tie ir dažādi cilvēki.) Pierādīt, ka no fakultātes studentiem var izveidot piecas tulkotāju grupas tā, lai katrā grupā tieši 10 cilvēki pārvaldītu angļu valodu, tieši 10- vācu valodu un tieši 10- farnču valodu (tiem nav noteikti jābūt dažādiem cilvēkiem).

167. Pierādīt, ka eksistē naturāls skaitlis, kas dalās ar 2¹⁹⁸² un nesatur savā pierakstā nevienu nulli.

168. Skaitli x, 0x1, atļauts aizstāt vai nu ar 1-x vai arī ar x/2. Pierādīt, ka no skaitļa 1/2 var iegūt skaitli 1983/2¹⁹⁸², izmantojot tikai minētos pārveidojumus.

169. Pierādīt, ka naturālos skaitļus no 1 līdz 1024 ieskaitot var sadalīt divās grupās tā, ka vienas grupas skaitļu k-to pakāpju summa vienāda ar otras grupas skaitļu k-to pakāpju summu katram k=1 2, …, 9.

*170. (Tēma skolēnu zinātniskajai biedrībai.) Noskaidrot, kāds ir minimālais operāciju skaits, ar kuru n diskus var sakārtot tā, kā prasīts 165. uzdevumā.