8. NODAĻA

SAREŽĢĪTA INDUKCIJAS PARAMERTA IZVĒLE

Aplūkosim sarežģītākus indukcijas piemērus.

68. piemērs. Doti n kauliņi. Katrs no tiem nokrāsots vienā krāsā, turklāt nevienā krāsā nav nokrāsoti vairāk kā n/2 kauliņi. Pierādīt, ka šos kauliņus var novietot uz riņķa līnijas tā, lai nekādi divi vienas krāsas kauliņi neatrastos blakus.

Līdzšenējā pieredze vedina izdarīt indukciju pēc kauliņu skaita. Varbūt kāds no lasītājiem to spēs izdarīt; mēs aplūkosim indukciju pēc dažādo krāsu skaita k.

Bāze. Ja k=1, tad uzdevuma nosacījumi nav izpildāmi, jo n>n/2, ja n>0.

Ja k=3, apzīmēsim krāsas ar A, B un C; ar atbilstošajiem mazajiem burtiem apzīmēsim attiecīgajā krāsā nokrāsoto kauliņu skaitu. Pieņemsim, ka abc. Izvietosim A krāsas kauliņus regulāra n-stūra virsotnēs, pa vienai virsotnei izlaižot. Tā kā an/2, tad nekādi divi no šiem kauliņiem neatrodas balakus virsotnēs.

Aiz pēdējā A krāsas kauliņa sāksim izvietot B krāsas kauliņus, joprojām izlaižot pa vienai virsotnei. Kad tas vairs nav iespējams, B krāsas kauliņus izvietojam secīgi starp jau izvietotajiem A krāsas kauliņiem. Tā kā ba, tad nekādi divi no tiem neatrodas blakus virsotnēs.

Atlikušās tukšās virsotnes neatrodas cita citai blakus; tajās izvietojam C krāsas kauliņus.

Pāreja kk+1, ja k3. Pieņemsim, ka k krāsu gadījumā uzdevuma apgalvojums ir patiess, un aplūkosim k+1 krāsās nokrāsotus vienkrāsainus kauliņus; ja k3, tad k+14. Izvēlešimies tās divas krāsas un no šīm k+1 krāsām, kurās nokrāsots vismazāk kauliņu; tā kā k+14, tad abās šajās krāsās kopā nokrāsots ne vairāk kā n/2 kauliņu. Aizstāsim krāsas un ar vienu krāsu, kas atšķiras no atlikušajām k-1 krāsām; tad kopējais krāsu skaits ir k. Pēc induktīvā pieņēmuma, k krāsās nokrāsotos kauliņus var izvietot saskaņā ar uzdevuma prasībām; šis pats izvietojums apmierina uzdevuma prasības arī tad, ja atgriežamies pie sākotnējā krāsojuma.

69. piemērs. Pierādīt, ka katrs naturāls skaitlis, kas nav Fibonači skaitlis (sk. 21. lpp.), ir izsakāms ar dažādu Fibonači skaitļu summu.

Ja naturāls skaitlis n nav Fibonači skaitlis, tad tas atrodas starp diviem Fibonači blakus skaitļiem, t.i., eksistē tāds naturāls k, ka

f_k<n<f_k+1 (k4, jo f₁=f₂=1, f₃=2_, f₃=3).

Pierādīsim uzdevuma apgalvojumu ar indukciju pēc k.

Bāze. Ja k=4, uzdevuma apgalvojums ir patiess, jo vienīgais naturālais skaitlis n no intervāla ]f₄; f₅[=]3;5[ ir 4 un 4=3+1=f₄+f₁.

Pāreja "mm+1". Pieņemsim, ka apgalvojums ir patiess visiem naturāliem k, ja km. Tas nozīmē, ka katrs naturāls skaitlis, kas mazāks nekā f_m+1 un nav Fibonači skaitlis, izsakāms ar dažādu Fibonači skaitļu summu; skaidrs, ka starp šiem saskaitāmajiem nav skaitļa f_m+1.

Aplūkosim naturālu skaitli n no intervāla ]f_m+1 ; f_m+2[; f_m+1<n<f_m+2 . Tā kā f_m+1+f_m =f_m+2 , tad n=f_m+1+x, kur 0<x<f_m<f_m+1. Pēc induktīvā pieņēmuma, x var izsacīt arī dažādu Fibonači skaitļu summu, starp kuriem nav skaitļa f_m+1; tāpēc arī n=f_m+1+x varizsacīt kā dažādu Fibonači skaitļu summu.

70. piemērs. Pierādīt, ka f_n dalās ar f_m, ja n dalās ar m. (f₁, f₂,…- Fibonači skaitļi; sk.21. lpp.) Uzdevumu var formulēt arī šādi: ja m un k- naturāli skaitļi, tad f_mk dalās ar f_m.

Pierādīt to ar indukciju pēc k (t.i., pēc skaitļu n un m dalījuma) patstāvīgi, izmantojot vienādību

f_u+v=f_u-1f_v+f_uf_v+1.

71. piemērs. Dots, ka x₁, x₂, …,x_m, y₁, y₂, …, y_n- naturāli skaitļi, turklāt

x1+x2+…+xm=y1+y2+…+yn<mn.

(1)

Pierādīt, ka vienādībā

x₁+x₂+…+x_m=y₁+y₂+…+y_n

var izsvītrot dažus saskaitāmos (bet ne visus) tā, lai iegūtu precīzu vienādību

Izdarīsim indukciju pēc kopējā doto skaitļu skaita s=m+n. Tā kā x₁,…, x_m,…, y₁,…, y_{n -} naturāli skaitļi, tad x₁+…+x_mm, y₁+…y _n n ; ņemot vērā nosacījumu (1), iegūstam, ka m n >m, m n > n , un tātad n >1, m>1, jeb n 2, m2 un s=m+ n 4.

Bāze. Ja s=4, tad m=2, n=2, x₁+x₂=y₁+y₂<4 un vismaz viens no skaitļiem x₁,x₂, tāpat arī vismaz viens no skaitļiem y₁, y₂ ir 1. Izsvītrojot vienādībā x₁+x₂=y₁+y₂ šos saskaitāmos, iegūstam pareizu vienādību.

Pāreja. Pieņemsim, ka apgalvojums patiess, ja doto skaitļu kopējais skaits ir s. Pierādīsim, ka apgalvojums patiess arī tad, ja šis skaits ir s+1, tad

x1+x2+…+xm=y1+y2+…+yn< mn,m+n=s+1

(2)

Pieņemsim, ka skaitļi x₁+x₂+…+x_m sakārtoti neaugošā secībā un skaitļi y₁+y₂+…+y_n- arī neaugošā secībā.

Aplūkosim x₁ un y₁. Ja x₁=y₁, vienādībā (2) varam izsvītrot x₁ un y₁ un iegūt pareizu vienādību. Ja x₁y₁, pieņemsim, ka x₁>y₁ (gadījumu, kad x₁<y_1, apskata analoģiski). Pārveidosim vienādību (2):

(x1 y1)+x2+…+xm=y2+…+yn;

(3)

saskaitāmo skaits šajā vienādībā ir s=m+n-1.

Ja nevienādība y₂+…+y_n<m(n-1) ir pareiza, tad saskaņā ar induktīvo pieņēmumu vienādībā (3) var izsvītrot dažus (ne visus) saskaitāmos un iegūt pareizu vienādību. Ja starp palikušajiem saskaitāmajiem vienādībā (3) nav (x₁-y₁), uzdevums it atrisināts; ja starp tiem ir (x₁-y₁), y₁ jāpārnes uz vienādības otru pusi.

Atliek pierādīt nevienādību y₂+…+y_n<m(n-1).

Apzīmēsim M=y₁+…y_n. Tā kā y₁- vislielākais (vai viens no vislielākajiem) šīs summas saskaitāmajiem, tad y₁M/n, tāpēc

.

Tā kā pēc uzdevuma nosacījumiem m<mn, tad

,

ko arī vajadzēja pārbaudīt.

72.. piemērs. Traukā atrodas n baktērijas un viens vīruss. Pirmajā sekundē vīruss apēd vienu baktēriju un pēc tam sadalās divos vīrusos; reizē ar vīrusu arī katra palikusī baktērija sadalās divās baktērijās. Nākošajā sekundē katrs vīruss atkal apēd vienu baktēriju, un pēc tam katrs vīruss dalās divos vīrusos un katra baktērija- divās baktērijās. Ja kādam vīrusam pietrūkst baktērijas, ko apēst, viņš tajā pašā sekundē nomirst.

Vai šāds process turpināsies bezgalīgi ilgi, vai arī pienāks brīdis, kad būs apēstas visas baktērijas?

Pierādīt patstāvīgi ar indukciju pēc t, ka pēc t sekundēm traukā atradīsies 2^t vīrusi un 2^t(n-t) baktērijas (t=1, 2, …, n). Tas nozīmē, ka pēc n sekundēm visas baktērijas būs apēstas (un tāpēc nākošajā sekundē nomirs arī visi vīrusi).

73. piemērs. Doti n atsvari, kuru masa gramos izteikta ar naturālu skaitli. Zināms, ka šos atsvarus var sadalīt k vienādas masas kaudzēs. Pierādīt, ka vismaz k dažādos veidos var no atsvaru komplekta izņemt vienu atsvaru tā, lai atlikušos atsvarus vairs nevarētu sadalīt k vienādas masas kaudzēs (k>1).

Šī uzdevuma risinājumā netiks izmantota ne indukcija pēc n, ne indukcija pēc k.

Nosauksim par ievērojamu katru tādu atsvaru, kuru izņemot no komplekta, atlikušos atsvarus vairs nevar sadalīt k vienādas masas kaudzēs; citus atsvarus nosauksim par neievērojamiem. Pieņemsim pretējo, ka ievērojamu atsvaru ir mazāk nekā k, un ar matemātisko indukciju pēc m pierādīsim šādu apgalvojumu:

ja m ir naturāls skaitlis, m1, tad katra neievērojama atsvara masa dalās ar k^m.

Bāze. Ja m=1, visu atsvaru kopējā masa dalās ar k (jo tos var sadalīt k vienādas masas kaudzēs). Izņemot no komplekta kādu neievērojamu atsvaru, tā paša iemesla dēļ atlikušo atsvaru kopējā masa un tātad arī izņemtā atsvara masa dalās ar k. Tātad katra neievērojamā atsvara masa dalās ar k.

Pāreja mm+1. Pieņemsim, ka katra neievērojama atsvara masa dalās ar k^m. Sadalām visus atsvarus k vienādas masas kaudzēs. Tā kā ievērojamo atsvaru ir mazāk nekā k, tad starp šīm kaudzēm var atrast tādu, kas nesatur nevienu ievērojamu atsvaru. Katra tajā ietilpstošā neievērojamā atsvara masa dalās ar k^m, tāpēc arī šīs kaudzes kopējā masa dalās ar k^m. Tāpēc visu atsvaru kopējā masa dalās ar kk^m=k^m+1 (jo visām k kaudzēm ir viena masa).

Izņemsim no viena komplekta jebkuru neievērojamu atsvaru. Spriežot līdzīgi kā iepriekš, iegūstam, ka visu palikušo atsvaru kopējā masa un tāpēc arī izņemtā neievērojamā atsvara masa dalās ar k^m+1. Induktīvā pāreja izdarīta.

Tā kā k2, tad skaitļu virkne k, k², k³, …, k^m, … ir neierobežota. Tāpēc nav tāda naturāla skaitļa, kas dalītos ar visiem tās locekļiem. Tātad neievērojamu atsvaru nemaz nav. Tā kā vispār atsvaru ir vismaz k (jo var izveidot k vienādas masas kaudzes), tad ir vismaz k ievērojamu atsvaru, kas ir pretrunā ar mūsu pieņēmumu.

Uzdevumi paškontrolei VIII

149. Pierādīt 69. piemēra pastiprinājumu: katru naturālu skaitli, kas nav Fibonači skaitlis, var izteikt ar dažādu Fibonači virknes locekļu summu, starp kuriem nav divu Fibonači virknes blakus skaitļu.

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

f_u+v=f_u-₁f_v+f_uf_v+1 (f_k- Fibonači skaitļi).

151. Pierādīt 956. uzdevuma rezultātu ar indukciju pēc k, kur k- mazākais no tiem naturālajiem i, kuriem na₁ +a₂+ …+a_i.

152. Taisnstūrveida tabulā ar m rindiņām un n kolonām katrā rūtiņā ierakstīts reāls skaitlis; visi skaitļi ir dažādi. Katrā kolonā pasvītroti k lielākie šīs kolonas sakitļi (km), bet katrā rindiņā pasvītroti s lielākie šīs rindiņas skaitļi (sn). Pierādīt, ka vismaz ks rūtiņās ierakstītie skaitļi pasvītroti divas reizes (kā rindiņas un kā kolonas lielākie skaitļi).

153. Taisnstūris sadalīts mazākos taisnstūros; katram mazākajam taisnstūrim vismaz vienas malas garums ir 1. Pierādīt, ka sākotnējam taisnstūtrim vismaz vienas malas garums izteikts ar veselu skaitli.

154. Pieņemsim, ka a₁, a₂, …, a_n- dažādi naturālie skaitļi, kas lielāki nekā 1; neviens no tiem nedalās ar naturāla skaitļa kvadrātu (izņemot 1). Skaitļi b₁, b₂, …, b_n ir racionāli skaitļi. Dots, ka

.

Pierādīt, ka b₁=b₂= …=b_n=0.

155. Atzīmēsim uz skaitļu ass punktus, kuru koordinātes ir veseli skaitļi. Punktā 0 atrodas daļiņa. Pēc vienas sekundes tā sadalās divās daļiņās, un viena daļiņa pārvietojas par 1 vienību pa labi, bet otra- par 1 vienību pa kreisi. Pēc nākošās sekundes ar katru no šīm daļiņām notiek tas pats, turklāt divas daļiņas, kas nonāk vienā un tajā pašā punktā, savstarpēji iznīcinās, utt. Pierādīt, ka pēc 2^k sekundēm būs tikai divas daļiņas: viena- punktā 2^k, otra- punktā- 2^k.