3. NODAĻA

VIENKĀRŠĀKĀS INDUKCIJAS SHĒMAS

Pēc šīs nodaļas apgūšanas Jūs pilnībā pārvaldīsiet matemātiskās indukcijas metodes pamatus. Matemātiskās indukcijas princips ir viens no matemātikas pamatiem. Daudzi iztirzātie piemēri ļaus detalizēti iepazīties ar matemātiskās indukcijas pielietošanas iespējām, risinot dažādus praktiskus uzdevumus. Atrisināto uzdevumu daudzveidība Jums pilnā mērā atsegs vispārīgu apgalvojumu pierādīšanas tehnoloģiju. Jūs būsiet spējīgi no atsevišķiem apgalvojumiem atrast vispārīgas likumsakarības. Uzdevumi paškontrolei ļaus padziļināti apgūt un nostiprināt matemātiskās indukcijas principu

Šajā un turpmākajās nodaļās vispārīgus apgalvojumus (un arī uzdevumus) apzīmēsim ar lielajiem latīņu burtiem (A, B, C utt.), aiz tiem iekavās norādīsim apgalvojuma (uzdevuma) parametrus. Piemēram, iepriekšējā paragrāfa 6. piemērā aplūkoto uzdevumu "atrast, cik veidos naturālu skaitli n var izteikt ar vieninieku un divnieku summu", varam apzīmēt ar B(n); tad konkrēto uzdevumu, ja n=12, apzīmēsim ar B(12).

Atcerēsimies apgalvojumu pierādīšanas interpretāciju ar rūtiņu aizkrāsošanu (sk. 1. §.). Tad 2. §. 6. piemēra uzdevums "atrast, cik veidos skaitli 12 var izteikt ar vieninieku un divnieku summu" nozīmē šādu uzdevumu: galīgā 12 rūtiņu lentē aizkrāsot pēdējo rūtiņu (16. zīm.).

Šī uzdevuma risinājumu grafiski var iztēloties šādi: vispirms atrisinājām uzdevumu B(1)- aizkrāsojām lentes pirmo rūtiņu, pēc tam atrisinājām uzdevumu B(2)- aizkrāsojām lentes otro rūtiņu, tad atradām iespēju no uzdevuma B(n) un B(n+1) atrisinājumiem iegūt uzdevuma B(n+2) atrisinājumu, resp., atradām iespēju aizkrāsot jebkuru tādu rūtiņu, kuras divas iepriekšējās rūtiņas ir aizkrāsotas. Grafiski to var attēlot ar 17. zīmējumā redzamo shēmu.

16. zīm.

17. zīm.

Tādejādi mēs pakāpeniski aizkrāsojam lentes trešo, ceturto, …., divpadsmito rūtiņu, t.i., atrisinājām uzdevumus B(3), B(4), …B(12).

Līdzīga ideja ir arī matemātiskās indukcijas metodes pamatā.

Aplūkosim vispārīgu apgalvojumu A(n), kura parametra n vērtības var būt 1, 2, 3,… .

Matemātiskās Indukcijas Princips (MIP)

Tātad, lai pierādītu, ka vispārīgs apgalvojums A(n) ir patiess,

1) jāpārbauda, vai ir patiess apgalvojums A(1);

2) pieņemot, ka A(k) ir patiess, un izmantojot to, jāpierāda, ka patiess ir arī apgalvojums A(k+1).

MIP ir viena no aritmētikas aksiomām, tāpēc tā pareizība nav jāpierāda. Tomēr

uzskatāmības labad "pasekosim" tā darbībai.

Pieņemsim, ka vispārīga apgalvojuma A(n) parametrs n var būt jebkurš naturāls skaitlis, un par šo apgalvojumu ir pierādīti MIP nosacījumi a) un b). Tad

1. apgalvojums A(1) ir patiess saskaņā ar a);
2. nosacījumā b) k var būt jebkurš naturāls skaitlis, tāpēc, izraugoties k=1, iegūstam: ja A(1) ir patiess, tad arī A(2) ir patiess; bet no nosacījuma a) zināms, ka apgalvojums A(1) ir patiess, tātad patiess ir arī A(2);
3. izvēloties k=2, saskaņā ar b) iegūstam: ja apgalvojums A(2) ir patiess, tad arī A(3) ir patiess. Bet pēc iepriekš pierādīta apgalvojuma A(2) ir patiess, tātad ir patiess arī A(3).

Līdzīgi turpinot, iegūstam, ka apgalvojums ir patiess, ja n=4, n=5, n=6 utt.

Nosacījumu a) sauc par indukcijas bāzi (jeb īsāk- par bāzi), bet nosacījumu b)- Pieņemsim, par induktīvo pāreju (īsāk- par pāreju). Induktīvajā pārejā izmantoto pieņēmumu par A(k) patiesumu sauc par induktīvo hipotēzi jeb induktīvo pieņēmumu.

Kā ģeometriski varētu ilustrēt MIP? Apgalvojumu A(n) kā vienmēr attēlosim ar rūtiņu rindu.

18. zīm.

Ja A(1) ir patiess, tad varam aizkrāsot pirmo rūtiņu;

19. zīm.

Bet nosacījums b) ģeometriski nozīmē šādu pāreju:

20. zīm.

Iegūstam lenti, kurā aizkrāsotas pirmās divas rūtiņas: . Atkārtojot vēlreiz šādu pāreju- aizstājot rūtiņu kombināciju ar , iegūstam lenti, kurā aizkrāsotas pirmās trīs rūtiņas: . Skaidrs, ka, līdzīgi turpinot, pakāpeniski aizkrāsosim visu bezgalīgo lenti, t.i., būsim pierādījuši vispārīgo apgalvojumu A(n).

12. piemērs. Pierādīt, ka katram naturālam n

1+3+5+7+…+(2n+1)=(n+1)2

(A(n))

Apzīmēsim summu 1+3+5+…+(2n+1) ar S_n.

Pierādīsim vienādību A(n), lietojot matemātiskās indukcijas principu:

1. vienādība A(1) ir patiesa, jo 1+3=2²;
2. jānoskaidro, vai katram naturālam k no A(k) patiesuma izriet, ka patiess ir A(k+1), jeb pierakstot to īsāk, vai A(k)A(k+1)?

Izvēlēsimies kaut kādu naturālu skaitli k un pieņemsim, ka vienādība A(k) ir pareiza, t.i., ka

S_k=1+3+5+…+(2k+1)=(k+1)²

Pierādīsim, ka tad pareiza ir arī vienādība A(k+1). Pierādāmo vienādību A(k+1) iegūstam, vienādībā A(n) ievietojot n vietā k+1:

S_k+1=1+3+5+…+(2(k+1)+1)=((k+1)+1)²=(k+2)².

Šī vienādība tiešām ir pareiza, jo

S_k+1=1+3+5+…+(2k+1)+(2k+3)=

=S_k+(2k+3)=(k+1)²+2k+3=

=k²+2k+1+2k+3=(k+2)².

Esam pierādījuši, ka A(k)A(k+1) katram naturālam k. Tā kā vienādībai A(n) esam pierādījuši MIP nosacījumus a) un b), tad apgalvojums "1+3+5+…+(2n+1)=(n+1)² visiem naturāliem n" ir pierādīts.

Ilustrēsim matemātiskās indukcijas metodi ar dažiem citiem raksturīgākajiem piemēriem. Dažreiz bāzi, ja tās pierādījums vienkāršs, īsuma labad nepierādīsim.

13. piemērs. Pierādīt, ka katram naturālam n

(A(n))

Apzīmēsim vienādības A(n) kreiso pusi ar S(n).

Bāze. Ja n=1, tad vienādība A(1) ir šāda:

Acīmredzot tā ir pareiza.

Induktīvā pāreja. Pieņemsim, ka k- kaut kāds fiksēts naturāls skaitlis, un pieņemsim, ka atsevišķais apgalvojums A(k) ir patiess, t.i., pieņemsim, ka

(A(k))

Izmantojot šo vienādību, pierādīsim atsevišķo apgalvojumu A(k+1):

Tiešām,

Tā kā pēc pieņēmuma A(k) ir pareiza vienādība, tad

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

Gan indukcijas bāze, gan pāreja ir pierādītas.

Tātad pēc matemātiskās indukcijas principa vispārīgais apgalvojums A(n) ir pierādīts.

14. piemērs. Pierādīt, ka katram naturālam n

(A(n))

Induktīvā pāreja. Pieņemsim, ka A(k)- patiess apgalvojums, t.i., ka

Pārbaudīsim, vai A(k+1) ir patiess. Izmantosim pieņēmumu par A(k) patiesumu:

t.i., A(k+1)- patiess apgalvojums. Pēc matemātiskās indukcijas principa ir pierādīts, ka vienādība A(n) pareiza katram naturālam n.

15. piemērs. Par Fibonači virkni sauc skaitļu virkni (a_n), ko definē šādi: a₁=1, a₂=1, a_n+2=a_n+1+a_n (n- naturāls skaitlis).

Pierādīt, ka

a) a1+a2+…+an=an+2-1;

(A(n))

b) a₂+a₄+a₆+…+a_2n=a_2n+2-1.

Pierādīsim vispirms apgalvojumu a). Apzīmēsim a₁+a₂+…+a_n ar S(n).

Bāze. Ja n=1, tad vienādība a₁=a₃-1 ir acīmredzama, jo a₃=a₁+a₂=2.

Induktīvā pāreja. Pieņemsim, ka vienādība A(k) pareiza, t.i., pieņemsim, ka a₁+a₂+a₃…+a_k=a_k+2-1. Tad a₁+a₂+a₃…+a_k+1=(a₁+a₂…+a_k)+a_k+1.

Izmantojot induktīvo pieņēmumu, iegūstam, ka S(k+1)=a_k+2-1+a_k+1=(a_k+1+a_k+2)-1=a_k+3-1=a_(k+1)+2-1.

Tātad vienādība A(k+1) arī ir pareiza.

Apgalvojums A(n) pierādīts.

P i e z ī m e: a_k+1+a_k+2=a_k+3 pēc Fibonači virknes definīcijas.

Apgalvojumu b) pierāda līdzīgi.

16. piemērs. Pierādīt, ka n3+5n dalās ar 6, ja n- naturāls skitlis.

(A(n))

Bāze. Ja n=1, tad 1³+51=6 dalās ar 6.

Induktīvā pāreja. Pieņemsim, ka apgalvojums A(k)- patiess, t.i., pieņemsim, ka k³+5k dalās ar 6. Pārbaudīsim, vai patiess A(k+1), t.i., pārbaudīsim vai (k+1)³+5(k+1) dalās ar 6.

(k+1)³+5(k+1)=k³+3k²+3k+1+5k+5=(k³+5k)+(3k²+3k)+6.

Skaidrs, ka 6 dalās ar 6; pēc induktīvā pieņēmuma par A(k) patiesumu arī k³+5k dalās ar 6. Tātad induktīvā pāreja būs pierādīta, ja pratīsim pierādīt, ka 3(k²+k) dalās ar 6 vai, kas ir tas pats, ka k²+k dalās ar 2.

To, ka k²+k dalās ar 2, var pierādīt, ievērojot, ka k²+k=k(k+1) un viens no diviem pēc kārtas ņemtiem naturāliem skaitļiem k un k+1 ir pāra skaitlis. Tomēr šo faktu varēja pierādīt arī ar matemātisko indukciju. Izdarīt to patstāvīgi!

Tādejādi šajā piemērā matemātiskās indukcijas metodi apgalvojuma pierādījumā nācās lietot divas reizes. Var gadīties, ka tā jālieto vēl vairākas reizes.

17. piemērs. Pierādīt, ka 7n+2+82n+1 dalās ar 57, ja n- naturāls skaitlis.

(A(n))

Induktīvā pāreja. Ja A(k)- patiess, tad 7^k+2+8^2k+1 dalās ar 57. Ievērojam, ka 7^(k+1)+2+8^2(k+1)+1=7^k+3+8^2k+3=77^k+2+648^2k+1=7(7^k+2+8^2k+1)+578^2k+1.

Pirmais saskaitāmais dalās ar 57 pēc induktīvās hipotēzes, otrajā saskaitāmajā viens reizinātājs ir 57. Tātad arī to summa dalās ar 57, un A(k+1) ir patiess.

18. piemērs. Pierādīt, ka 2ⁿ pēdējais cipars ir 6, ja n dalās ar 4.

Ja n dalās ar 4, tad n=4m (m- naturāls), un tātad jāpierāda, ka 2^4m pēdējais cipars ir 6.

Induktīvā pāreja. Ja 2^4k pēdējais cipars ir 6, tad 2^4(k+1)=2^4k (16 arī beidzas ar 6, jo abu reizinātāju pēdējie cipari ir 6, tātad arī to reizinājuma pēdējais cipars ir 6. Induktīvā pāreja A(k)A(k+1) ir pierādīta.

19. piemērs. Pierādīt, ka a^p-a dalās ar p, ja p- pirmskaitlis, bet a- naturāls skaitlis. (Fermā mazā teorēma).

Bāze. Ja a=1, tad 1^p-1=0 dalās ar p.

Induktīvā pāreja. Pieņemsim, ka apgalvojums ir patiess, ja a=k, t.i., pieņemsim, ka k^p-k dalās ar p. Pierādīsim, ka arī (k+1)^p-(k+1) dalās ar p.

Tiešām,

(k+1)^p-(k+1)=k^p+C_p¹k^p-1+C_p²k^p-2+…+C_p^p-1k+1-(k+1)=

=(k^p-k)+C_p¹k^p-1+C_p²k^p-2+...+C_p^p-1k.

Pirmais saskaitāmais dalās ar p pēc induktīvā pieņēmuma. Ja pierādīsim, ka C_p^m dalās ar p visiem tādiem naturāliem m, kuriem 1m(p-1), tad induktīvā pāreja būs pierādīta.

ir vesels skaitlis. Skaitītāja reizinātājs p nesaīsinās ne ar vienu no reizinātājiem saucējā, jo tie visi ir mazāki nekā p, bet p ir pirmskaitlis. Tātad arī ir vesels skaitlis. Esam pierādījuši, ka C_p^m dalās ar p.

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

(A(n))

Induktīvā pāreja. Pieņemsim, ka nevienādība A(k) ir pareiza, t.i., ka

(1)

Izmantojot (1), pierādīsim, ka pareiza nevienādība A(k+1):

(2)

Nevienādības (2) kreiso pusi var iegūt, nevienādības (1) kreiso pusi pareizinot ar nevienādības (2) labo pusi var iegūt, pareizinot (1) labo pusi ar Tāpēc, ja pratīsim pierādīt, ka

(3)

tad, sareizinot (1) un (3), iegūsim (2), un induktīvā pāreja būs pierādīta.

Nevienādību (3) ietecam lasītājiem pierādīt patstāvīgi. (Sakarā ar šo piemēru sk. arī 6. paragrāfa 121. uzdevumu.)

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

Induktīvā pāreja. Pieņemsim, ka

Tā kā

iegūtās summas pirmais saskaitāmais pēc induktīvās hipotēzes nav mazāks kā k², bet katra no k nākamajām iekavām nav mazāka nekā 2, tad visa izteiksme nav mazāka nekā k²+2k+1=(k+1)² , kas arī bija jāpierāda.

22. piemērs. Skaitļu virkni (a_n) definējam šādi: a₁ (n- naturāls skaitlis).

Pieņemsim, ka doti a_n+1 punkti un jebkuri no tiem savienoti ar taisnes nogriezni vienā no n krāsām. Pierādīt, ka katram naturālam n var atrast trijstūri ar virsotnēm dotajos punktos, kuram visas malas ir vienā un tajā un pašā krāsā.

Bāze. Ja a₁=1, tad punktu skaits ir a₁+1=3, bet krāsa tikai viena. Meklējamā trijstūra virsotnes ir trīs dotie punkti.

Induktīvā pāreja. Pieņemsim, ka apgalvojums pareizs, ja n=k. Aplūkosim a_k+1+1 punktus un nogriežņus, kas tos pa pāriem savieno; šie nogriežņi ir k+1 krāsās. Izvēlamies vienu no aplūkojamajiem punktiem A; tas savienots ar a_k+1=(k+1)a_k+1 citiem punktiem. Tā kā krāsu ir k+1, tad vismaz a_k+1 punktus ar punktu A savieno vienas un tās pašas krāsas nogriežņi.(Ja no A neizietu vairāk kā a_k vienas krāsas nogriežņu, tad kopējais no A izejošo nogriežņu skaits nepārsniegtu (k+1)a_k) Aplūkosim šos a_k+1 punktus. Ir divas iespējas:

1. kaut divi no šiem punktiem savienoti ar krāsas nogriezni. Tad tie kopā a punktu A noder par meklējamā trijstūta virsotnēm;
2. nekādi divi no aplūkojamajiem a_k+1 punktiem nav savienoti ar krāsas nogriezni. Tas nozīmē, ka šie a_k+1 punkti pa pāriem savienoti ar nogriežņiem, kas nokrāsoti pārējās k krāsās; tad no tiem var izvēlēties trīs punktus, kas pa pāriem savienoti ar vienas krāsas nogriežņiem, pēc induktīvā pieņēmuma.

Šī rezultāta vispārinājums un interesanta problēmu kopa, kas ar to saistās, aprakstīta 7. paragrāfā.

23. piemērs. Plaknē novilktas n dažādas taisnes sadala šo plakni apgabalos. Pierādīt, ka, krāsojot katru apgabalu vienā no divām dotajām krāsām, var tā nokrāsot visu plakni, ka nekādi divi apgabali ar kopēju malu nav vienā krāsā.

Bāze. Ja n=1, nokrāsojam vienu pusplakni baltu, otru melnu.

Induktīvā pāreja. Pieņemsim, ka k taisnēm apgalvojums jau pierādīts: apgabalus, kuros k taisnes sadala plakni, var nokrāsot uzdevumā prasītajā veidā. Novilksim vēl vienu taisni (tad plakni apgabalos sadalīs k+1 taisnes), un apgabaliem vienā pusē no tās krāsojumu neaiztiksim, bet otrā pusē mainīsim krāsas uz pretējo. Ja divu apgabalu kopējā mala atrodas uz šīs taisnes, tad apgabaliem ir dažādas krāsas saskaņā ar veikto pārkrāsošanu; ja apgabalu kopējā mala atrodas uz kādas no pārējām k taisnēm, tad apgabali ir dažādās krāsās saskaņā ar induktīvo hipotēzi.

24. piemērs. Pierādīt, ka katru naturālu skaitli, kas nepārsniedz n!, var sadalīt ne vairāk, kā n dažādos saskaitāmajos, kas visi ir skaitļa n! dalītāji.

Bāze. Ja n=1, tad 1!=1; ar vienīgo saskaitāmo dalās ar 1!.

Induktīvā pāreja. Pieņemsim, ka apgalvojums ir pareizs, ja n=k.

Aplūkosim skaitli m(k+1)! un dalīsim to ar k+1; tad m=(k+1)d+r, kur dalījums dk! un atlikums r apmierina nevienādības 0rk. Pēc induktīvās hipotēzes

pie tam sk; katrs no saskaitāmajiem a₁, a₂, …, a_s ir skaitļa k! dalītājs un tie visi ir dažādi. Tāpēc summā

saskaitāmo skaits nepārsniedz k+1, katrs no šiem saskaitāmajiem ir (k+1)! Dalītājs un tie visi ir dažādi: pirmie s saskaitāmie saskaņā ar induktīvo pieņēmumu, pēdējais tāpēc, ka tas ir mazāks nekā k+1, bet visi pārējie- ne mazāki kā k+1.

25. piemērs. Dots cirkulis ar konstantu atvērumu un lineāls bez iedaļām. Izmantojot šos instrumentus, konstruēt nogriezni, kura garums ir r/n (n- naturāls skaitlis, r- ar doto cirkuļa atvērumu novilktās riņķa līnijas rādiuss).

Konstruēsim riņķa līniju, kuras centrs ir O un rādiuss- r. Šajā riņķa līnijā ievilksim regulāru sešstūri; tā malas garums ir r. Apzīmēsim sešstūra virsotnes ar A₁, A₂, A₃, A₄, A₅, A₆, A₇. Bez tam katram naturālam k definēsim A_6k+1=A₁, A_6k+2=A₂,…, A_6k+5=A₅, A_6k+6=A₆, (t.i., iedomāsimies, ka sešstūra virsotņu numerācija secīgi turpinās vēl otro, trešo,…k-to,…. reizi).

Parādīsim, kā uz rādiusa [OA_n] konstruēt tādu punktu X_n, ka OX_n=r/k.

Bāze. Uz rādiusa [OA₁] varam ņemt X₁=A₁.

Induktīvā pāreja. Pieņemsim, ka uz [OA_k] atrasts tāds X_k, ka OX_n=r/k. (21. zīm.).

21. zīm.

Savienosim X_k un A_k+2 ar taisni. Tad [OA_k+1] un [X_kA_k+2] krustpunkts Z ir meklējamais punkts X_k+1. (Pierādīt!)

26. piemērs. Pierādīt: katram naturālam n eksistē tāda galīga plaknes punktu kopa S_n, ka katrs kopas S_n punkts A atrodas 1 cm attālumā tieši no n kopas S_n punktiem.

Bāze. Ja n=1, par kopu S₁ var ņemt divu tādu punktu kopu, kuri atrodas 1 cm attālumā viens no otra.

Induktīvā pāreja. Pieņemsim, ka naturālam skaitlim k eskistē uzdevumā prasītā punktu kopa S_k.

Apzīmēsim ar S`<sub>k</sub> kopas S<sub>k</sub> attēlu paralēlajā pārnesē par vektoru, kura garums ir 1 cm, bet virziens izraudzīts tā, lai kopām S<sub>k</sub> un S`_k nebūtu kopēju punktu un lai attālums starp kopas S_k punktu A un kopas S`<sub>k</sub> punktu B būtu 1 cm tikai tad, ja B ir A attēls. Tad par kopu S<sub>k+1</sub> var ņemt kopu S<sub>k</sub> un S`_k apvienojumu.

P i e z ī m e. Pierādījumu tam, ka šādu pārbīdes virzienu vienmēr var izvēlēties, sk. 50. uzdevuma atrisinājumā.

27. piemērs. Aplūkosim dzelzceļa mezglu, kurš parādīts 22. zīmējumā. No punkta A mezglam tuvojas 2ⁿ vagoni (pieņemsim, ka katram no tiem ir autonoms dzinējs, t.i., katrs vagons var pārvietoties patstāvīgi). Mezglā ir n "strupceļi" X¹, X²,…, Xⁿ. Katrs taisnais posms ir pietiekami garš, lai tajā varētu novietoties visi vagoni. Vagoniem aizliegts virzīties pa kreisi.

Pierādīt, ka šādā mezglā vagoni var pārkārtoties un aizbraukt uz punktu B jebkurā kārtībā.

22. zīm.

Bāze. Ja n=1, mezglā ir tikai 1 strupceļš X₁, un tam cauri brauc divi vagoni. Viegli pārbaudīt, ka tie var izbraukt cauri mezglam gan tādā pašā kārtībā, kādā tie brauca no A, gan pretējā kārtībā.

Induktīvā pāreja. Pieņemsim, ka mezglā ar k strupceļiem X₁, X₂,…X_k var pārkārtot jebkurā kārtībā 2^k vagonus. Aplūkosim mezglu ar k+1 strupceļiem X₁, X₂,…, X_k, X_k+1, kuram no kreisās puses tuvojas 2^k+1 vagoni.

Pieraksta ērtības labad turpmāk apzīmēsim m=2^k; tad 2^k+1=2m.

Pieņemsim, ka vagoniem pēc izbraukšanas caur mezglu jābūt sakārtotiem šādi: vispirms vagons v₁, aiz tā- vagons v₂, pēc tam- v₃,…, pašās beigās (kreisajā galā)- vagons v_2m.

Sastāvā, kas tuvojas mezglam no kreisās puses, aplūkosim pirmos m vagonus. Pēc induktīvā pieņēmuma šos vagonus, izmantojot strupceļus X₁, X₂, …,X_k, posmā Y_kY_k+1 var sakārtot jebkurā kārtībā. Sakārtosim tos šajā posmā otrādā kārtībā, nekā tiem jāparādās posmā Y_k+1B, un pēc tam visu šādi sakārtotu pirmo m vagonu virkni ievadīsim strupceļā X_k+1; tagad šajā strupceļā, skaitot no augšas uz leju, pirmie m vagoni būs sakārtoti tādā kārtībā, kādā tie nonāks posmā Y_k+1B. Pēc tam vēlreiz izmantojot induktīvo pieņēmumu, sakārtosim pēdējos m vagonus posmā Y_k+1Y tādā kārtībā, kādā tiem jānonāk posmā Y_k+1B. Izraugoties piemērotā secībā vagonus no strupceļa X_k+1 un posma Y_kY_k+1, iegūsim visu 2m vagonu vajadzīgo sakārtojumu.

(Šis piemērs ilustrē metodes, kuras elektronu skaitļojamās mašīnas lieto informācijas glabāšanai un sakārtošanai.)

Līdz šim mēs aplūkojām piemērus, kuros induktīvā pāreja no k uz k+1 tika izdarīta "vienveidīgi", neatkarīgi no hipotētiskā, parametra vērtībai k atbilstošā apgalvojuma īpašībām. Tomēr iespējams, ka induktīvajā pārejā jāšķiro vairāki gadījumi.

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

Bāze. Ja n=1, tad x₁=1, tātad arī x_11.

Induktīvā pāreja. Pieņemsim, ka apgalvojums pierādīts k saskaitāmajiem. Aplūkosim k+1 pozitīvus saskaitāmos x₁, x₂,…, x_k, x_k+1, kuru reizinājums ir 1. Iespējami divi gadījumi:

1. x₁=x₂=…=x_k=x_k+1=1. Tad protams, x₁+x₂+…+x_k+x_k+1=k+1k+1;
2. kāds no saskaitāmajiem x₁, 1i(k+1) atšķiras no 1. Tad starp šiem k+1 saskaitāmajiem ir tāds saskaitāmais, kurš lielāks nekā 1, un arī tāds saskaitāmais, kurš mazāks nekā 1. Pieņemsim, ka x₁>1 un x₂<1 (ja šiem saskaitāmajiem ir citi indeksi, pierādījums nemainās- apskatāmos k+1 skaitļus var tā pārnumurēt, lai būtu pareizas nevienādības x₁>1 un x₂<1). Tad (1-x₁)(1-x₂)<0 un tātad

1+x1x2<x1+x2.

(1)

Apskatām k pozitīvus skaitļus x₁x₂, x₃, x₄, …, x_k, x_k+1. Pēc uzdevuma nosacījumiem to reizinājums ir 1, tāpēc saskaņā ar induktīvo pieņēmumu

No šīs nevienādības un nevienādības (1) iegūstam, ka

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

P i e z ī m e. Sakarā ar šī uzdevuma risinājumu sk. arī 9. paragrāfu.

29. piemērs. Pieņemsim, ka plaknē atzīmēti v punkti; sauksim tos par virsotnēm. Daži šo punktu pāri savā starpā savienoti ar līnijām, kuras sauksim par robežām; katrai robežai pieder tikai divas virsotnes- šīs robežas galapunkti, un dažādām robežām kopēji punkti var būt tikai galapunkti. Apzīmēsim robežu skaitu ar r. Robežas sadala plakni apgabalos; apzīmēsim to skaitu ar a. (Piemēram, 23. zīmējumā v=8, r=9, a=3: apgabals kontūras ABCD iekšpusē, apgabals kontūras DFG iekšpusē un bezgalīgais ārējais apgabals.)

23. zīm.

Pieņemsim, ka no jebkuras virsotnes uz katru citu virsotni var aiziet, ejot pa robežām; tādu "karti" sauksim par sakarīgu. Pierādīt, ka katrai sakarīgai kartei

v+a=r+2

(1)

Šo apgalvojumu sauc par Eilera formulu plakaniem sakarīgiem grafiem. Pierādīsim to ar matemātisko indukciju pēc parametra r.

Bāze. Ja r=1, tad v=2, a=1, un vienādība (1) ir pareiza.

Pāreja. Pieņemsim, vienādība (1) ir pareiza sakarīgām kartēm, kas satur k robežas, un aplūkosim karti ar k+1 robežām, v virsotnēm un a apgabaliem. Pierādīsim vienādību

v+a= (k+1)+2.

(2)

Ir divas iespējas.

1. Apskatāmajā kartē var atrast virsotni, no kuras iziet tikai viena robeža. Nodzēsīsim šo virsotni un šo robežu. Jauniegūtā karte būs sakarīga, tai būs k robežas, v-1 virsotne un a apgabali; pēc induktīvās hipotēzes

1. teorēma.

Ievērosim, ka 1. teorēmas grafiskā ilustrācija ir tāda pati kā MIP gadījumā, tikai lentes kreisā rūtiņa tagad atbilst parametra vērtībai p, nākošā- parametra vērtībai p+1 utt. Iesakām par to pārliecināties lasītājam patstāvīgi.

32. piemērs. Dots, ka m2, n>9m+20, m un n- vai nu abi pāra, vai abi nepāra skaitļi. Pierādīt, ka skaitli n var izteikt ar m saliktu nepāra skaitļu summu.

Apgalvojumu pierādīsim ar indukciju pēc m.

Bāze. Ja m=2, jāapskata pāra skaitļi n, kas lielāki nekā 38. Katru šādu n var izteikt vienā no trim veidiem:

n=6t+40=25+3(2t+5),

n=6t+42=27+3(2t+5),

n=6t+44=35+3(2t+3),

kur t- vesels, t0. Tātad bāze pierādīta.

Pāreja. Pieņemsim, ka apgalvojums patiess, ja m=k, un pierādīsim, ka tas patiess, ja arī m=k+1. Aplūkosim skaitli

n>9(k+1)+20.

Tad n=9+N, kur N>9k+20. Ja skaitļi k+1 un n abi ir pāra skaitļi vai abi- nepāra skaitļi, tad arī N=n-9 un k ir vai nu abi pāra, vai abi nepāra skaitļi, tāpēc saskaņā ar induktīvo pieņēmumu N var izteikt ar k saliktu nepāra skaitļu summu. Tā kā n=9+N, tad n var izteikt ar k+1 saliktu nepāra skaitļu summu.

33. piemērs. Pierādīt, ka katram naturālam n, n3 var atrast tādus dažādus naturālus skaitļus, x₁, x₂, x₃, …x_n, ka

Bāze. Ja n=3, tad x₁=2, x₂=3, x₃=6, jo

Pāreja. Pieņemsim, ka x₁<x₂<…<x_k ir tādi k naturāli skaitļi, ka

Tā kā katram naturālam m ir pareiza vienādība tad skaitļi x₁, x₂, …, x_k-1, x_k+1, un x_k(x_k+1) ir tādi k+1 dažādi naturāli skaitļi, kuru apgriezto lielumu summa ir 1.

P i e z ī m e. Sk. arī 4. Paragrāfa 111. un 112. uzdevumu.

34. piemērs. Pilsētā dzīvo n pļāpas, n4. Katrai no viņām mājās ir telefons. Kādu dienu pļāpas visas vienlaikus uzzin katra savu jaunu ziņu. Pierādīt, ka var tā noorganizēt viņu telefona sarunas, ka pēc 2n-4 sarunām katra no viņām zinās visas jaunās ziņas.

Bāze. Ja n=4, apzīmēsim pļāpas ar A, B, C, D. Pieņemsim, ka katrā sarunā katra pļāpa izstāsta visas viņai zināmās jaunās ziņas. Tad mērķis būs sasniegts pēc četrām sarunām šādā secībā: AB, CD, AC, BD.

Pāreja. Pieņemsim, ka apgalvojums ir pareizs, ja n=k. Organizēsim k+1 pļāpu telefona sarunas šādi.

1. Vispirms sarunājas divas pļāpas A un B.
2. Tālālajās sarunās pļāpa A nepiedalās, bet pārējās k pļāpas apmainās savā starpā ar viņām zināmo informāciju. Pēc induktīvā pieņēmuma telefona sakarus var organizēt tā, ka pēc 2k-4 sarunām šīs k pļāpas zinās visas jaunās ziņas (k pļāpu sarunu sākumā pļāpa B zināja gan savu, gan pļāpas A jauno ziņu).
3. Pļāpa B piezvana pļāpai A un izstāsta viņai visus uzzinātos jaunumus. Tādejādi pavisam notikušas 1+(2k-4)+1=2(k+1)-4 telefona sarunas.

Piezīme. Sakarā ar šo uzdevumu sk. šī paragrāfa 60.- 70. uzdevumus.

35. piemērs. n laupītāji aplaupījuši Bagdādes kalīfu. Katram laupītājam ir savs ieskats par tās vai citas laupījuma daļas vērtību. Kā sadalīt laupījumu, lai katrs laupītājs būtu pārliecināts, ka pēc viņa vērtējuma saņemta vismaz 1/n daļa no laupījuma?

Bāze. Ja n=2, laupījumu var sadalīt šādi. Pirmais laupītājs sadala laupījumu divās, pēc viņa ieskata vienādi vērtīgās daļās, bet otrs laupītājs izvēlas to daļu, kas viņam liekas vērtīgāka.

Pāreja. Pieņemsim, ka k laupītāji prot sadalīt laupījumu. Tad k+1 laupītāji var rīkoties pēc šādas stratēģijas.

1. Laupījuma dalīšanā piedalās tikai k laupītāji. Viņi sadala visu laupījumu savā starpā tā, lai katrs (pēc paša domām) saņemtu vismaz k-to daļu no visa laupījuma; to var izdarīt saskaņā ar induktīvo pieņēmumu.
2. Katrs no k laupītājiem, kas piedalījās laupījuma dalīšanā, sadala savu daļu k+1 pēc viņa ieskata vienādi vērtīgās daļās.
3. Laupītājs, kas dalīšanā nepiedalījās, paņem pa vienai daļai no katra sava biedra (protams, to daļu, kas viņam liekas vērtīgāka).

Pārbaudiet paši, vai visi laupītāji būs apmierināti (to, protams, nevar pateikt par kalīfu)!

36. piemērs. Volejbola turnīrā piedalās n komandas. Katra komanda ar jebkuru no pārējām komandām spēlē vienu reizi; neizšķirtu rezultātu nav. Pierādīt, ka pēc turnīra nobeiguma komandas var tā sanumurēt, ka pirmā komanda uzvarējusi otro, otrā- trešo, …, (n-1)-ā komanda- n-to komandu.

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

Pāreja. Pieņemsim, ka apgalvojums pareizs k komandu turnīriem, un aplūkosim turnīru, kurā piedalās k+1 komandas.

"Aizmirsīsim" vienu komandu (apzīmēsim to ar A) un apskatīsim pārējo k komandu "apakšturnīru". Pēc uzdevuma nosacījumiem šīs k komandas var tā sanumurēt, ka pirmā komanda uzvarējusi otro, otrā- trešo, …,(k-1)-tā komanda- k-to. Apzīmēsim šādi sanumurētas kmandas ar B₁, B₂, …, B_k-1, B_k. Tagad noskaidrosim, kā komanda A nospēlējusi ar komandām B₁, …, B_k. Ir trīs iespējas.

1. Komanda A uzvarējusi komandu B₁. Piešķiram komandai A numuru 1, bet komandai B_i- numuru i+1 (i=1, 2, …, k).
2. Komanda A zaudējusi pirmajām m komandām B₁, B₂,…B_m, bet uzvarējusi (m+1)-o komandu B_m+1. Komandām B₁, B₂, …, B_m numurus nemainām, komandai A piešķiram numuru m+1, bet komandām B_m+1,…,B_k numurus palielinam par 1.
3. Komanda A zaudējusi visām k komandām B₁, ..., B_k. Tad tām numurus nemainām, bet komandai A piešķiram numuru k+1.

32.-36. piemērā parametra vērtības bija naturāli skaitļi, kas lielāki par kādu naturālu p vai vienādi ar p (p2) , tāpēc ka mazākām parametra vērtībām apgalvojums ir nepareizs (33. piemērs), vai arī tāpēc, ka mazākām parametra vērtībām uzdevumam nav jēgas (36. piemērs). Apskatīsim vēl divus piemērus, kuros šādai īpatnībai ir citi cēloņi.

37. piemērs. Uz taisnes doti n2 nogriežņi; ik diviem no tiem ir kopējs punkts. Pierādīt, ka visiem n nogriežņiem ir kopējs punkts.

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

Aplūkosim trīs nogriežņus a, b, un c. Pieņemsim, ka P₁ab, P₂ac, P₃bc. Aplūkosim P₁, P₂, un P₃ novietojumu uz taisnes. Vismaz viens no tiem pieder nogrieznim, kura galapunkti ir abi pārējie; pieņemsim, ka P_3[P1P₂]. Tā kā P₁ab un P₂ac,, tad arī P₁a un P₂a, tāpēc [P₁P₂]a. Tā kā P_3[P1P₂], tad arī P₃a. Tātad P₃ ir kopējs visiem trim nogriežņiem.

Pāreja. Pieņemsim, ka apgalvojums pareizs k nogriežņiem, un pierādīsim, ka tas patiess arī k+1 nogriežņiem a₁, a₂, …,a_k, a_k+1, ja ik diviem no tiem ir kopējs punkts. Aplūkosim k nogriežņus a₁, a₂, …,a_k-1, a_ka_k+1. (Tā kā nogriežņiem a_k un a_k+1 ir kopēji punkti, tad a_ka_k+1 arī ir nogrieznis (var būt 1 punkts))

Pierādīsim, ka arī katriem diviem no šiem k nogriežņiem ir kopējs punkts. Tiešām, ik diviem no nogriežņiem a₁, a₂, …,a_k-1 ir kopējs punkts saskaņā ar doto k+1 nogriežņu īpašībām; nogriežņiem a_ka_k+1 un a_i (1ik-1) ir kopējs punkts saskaņā ar jau pierādīto gadījumu, kad n=3.

Tātad pēc induktīvās hipotēzes k nogriežņiem a₁, a₂, …,a_k-1, a_ka_k+1 ir kopējs punkts; tas pats punkts ir kopējs arī dotajiem k+1 nogriežņiem.

Pierādīto teorēmu sauc par Helli teorēmu taisnes gadījumā. Šīs teorēmas vispārinājumi un pielietojumi aplūkoti 78.- 81. uzdevumā.

Induktīvajā pārejā izmantojām parametra vērtībai 3 atbilstošo jau pierādīto atsevišķo apgalvojumu. Par raksturīgākajām kļūdām līdzīgu uzdevumu risinājumos pastāstīts 9. paragrāfā.

! 38. piemērs. Dots, ka a un n- naturāli skaitļi. Pierādīt, ka aⁿ⁺³+(a+1)²ⁿ⁺³ dalās ar a²+a+1.

Protams, mēs varam pārbaudīt apgalvojuma patiesumu, ja n=1, un pielietot MIP. Bet indukcijas bāzes pārbaude būs diezgan darbietilpīga. Tāpēc rīkosimies citādi- pierādīsim šo apgalvojumu plašākai parametra n vērtību kopai.

Bāze. Ja n=-1, tad a²+(a+1).dalās ar a²+a+1.

Pāreja. Pieņemsim, ka a^k+3+(a+1)^2k+3 dalās ar a²+a+1, kur k-1. Tad

Otrais sakaitāmais acīmredzot dalās ar a²+a+1; arī pirmais saskaitāmais dalās ar a²+a+1 pēc induktīvās hipotēzes.

Līdz ar to pēc 1. teorēmas apgalvojums pierādīts visām parametra n vētrībām, kas nav mazākas kā -1, tātad arī visiem naturāliem n.

Nobeigumā atzīmēsim, ka, lai gan visos piemēros bāzes pārbaude bija vienkāršākā, gandrīz trivāla risinājuma daļa, to nekādā gadījumā nedrīkst aizmirst. Tiešām, induktīvais spriedums ir it kā daudzstāvu mājas celtniecība, kurā katrs nākošāis stāvs balstās uz iepriekšējo; ja nav pamata- indukcijas bāzes, sabrūk arī visa celtne.

Aplūkosim piemēru.

39. piemērs. "Visi naturālie skaitļi ir vienādi."

"Pierādīsim" to ar matemātisko indukciju.

Pieņemsim, ka jau pierādīta vienādība k=k+1. Pieskaitot šīs vienādības abām pusēm 1, iegūstam, ka k+1=(k+1)+1, jeb k+1=k+2 (induktīvā pāreja). Ievietojot šajā vienādībā n=1, n=2 utt., iegūstam, ka 1=2=3=…,t.i., ka visi naturālie skaitļi ir vienādi.

Kļūdas cēlonis: nav pierādīta indukcijas bāze "1=2"; tā arī nav jāpierāda, jo nav pareiza.

Uzdevumi paškontrolei III.

22. Uzgriežņa katrā galā pierakstīts skaitlis 1. Pirmajā solī nogriežņa vidū uzrakstām skaitli 2. Katrā nākošā solī starp ik diviem jau uzrakstītiem blakus skaitļiem uzrakstām to summu. Tā pēc otrā soļa būs uzrakstīta skaitļu virkne 1, 3, 2, 3, 1, pēc tršā soļa- virkne 1, 4, 3, 5, 2, 5, 3, 4, 1, utt.

Pierādīt, ka pēc n-tā soļa uzrakstīto skaitļu summa ir 3n+1.

23. Pierādīt vienādības

24. Caur vienu punktu novilktas n plaknes tā, ka nekādas trīs no tām neiet caur vienu taisni. Pierādīt, ka šīs plaknes telpu sadala n²-n+2 daļas.

25. Regulāra trijstūra katra mala sadalīta n kongruentās daļas. Caur dalījuma punktiem novilktas taisnes paralēli trijstūra malām. Pierādīt, ka tās sadala doto trijstūri n² trijstūros.

26. Skaitļu virkni (a_n) definē šādi: a₁=2; a_n+1=a_n²-a_n+1 , ja n1, n- naturāls skaitlis. Pierādīt, ka

27. Aplūkosim izteiksmes a₁x₁+a₂x₂+…+a_nx_n, kurās katrs no koeficentiem a_i ir vai nu 1, vai -1. Pierādīt, ka visu šo izteiksmju kvadrātu summa ir 2ⁿ, ja. x₁²+x₂²+…+x_n²=1.

28. Ja (x_i)- kaut kāda virkne, tad ar apzīmēsim summu x₁+x₂+…+x_n. Pieņemsim, ka (a_i) un (b_i)- kaut kādas virknes (i=1, 2, 3, …). Apzīmēsim b₁+b₂+…+b_k ar B_k. Pierādīt, ka katram n2 ir pareiza vienādība

Šo formulu sauc par Ābela formulu. To bieži lieto, aprēķinot dažādas summas (sk., piemēram, [20]). Lasītājs ar zināšanām augstākajā matemātikā saskatīs tās analoģiju ar parciālās integrēšanas formulu.

*29. Izmantojot Ābela formulu, aprēķināt summu

30. Katrs no skaitļiem a₁,…, a_n ir vai nu -1, vai 1. Pierādīt vienādību

*31. Ar d(n) apzīmēsim naturāla skaitļa n dalītāju skaitu. Pierādīt, ka

*32. Atrisināt 31. uzdevumu, neizmantojot matemātisko indukciju.

*33. Pierādīt, ka

34. Pierādīt, ka Fibonači skaitļu virknes locekļiem (sk. 21. lpp.) ir pareizas šādas vienādības

a) a₁+a₃+ a₅+…+a_2n-1= a_2n;

b) a₁²+a₂²+ a₃²+…+a_n²=a_na_n+1;

c) a₁a₂+a₂a₃+…+a_2na_2n+1=a_2n+1²-1;

d) a_n²= a_n-1a_n+1+(-1)ⁿ⁺¹, ja n2

e) a_n+m= a_n-1a_m+ a_na_m+1, ja n2

35. Pierādīt, ka Lukasa virknes locekļiem (sk. 17. lpp.) ir pareiza vienādība

36. Pierādīt, ka naturālam skaitlim n

a) 11¹⁰ⁿ-1 dalās ar 100;

b) 7ⁿ-18ⁿ-1 dalās ar 6;

c) n³+6n²+5n dalās ar 6;

d) 6²ⁿ+103ⁿ dalās ar 11;

e) 6²ⁿ+19ⁿ-2ⁿ⁺¹ dalās ar 17.

37. Pierādīt, ka triju pēc kārtas ņemtu naturālu skaitļu kubu summa dalās ar 9.

38. Pierādīt, ka skaitlis, kura decimālais pieraksts sastāv no 3ⁿ vieniniekiem, dalās ar 3ⁿ.

39. No skaitļiem 1, 2, 3,…,2n-1, 2n izraudzīti n+1 skaitļi. Pierādīt,ka viens no tiem dalās ar kādu citu no izraudzītajiem skaitļiem.

40. Zināms, ka k-tās pakāpes polinoma P(x) koeficenti ir veseli skaitļi un polinoma vērtība P(x) dalās ar m, ja x- vesels skaitlis. Koeficents pie xk. ir a. Pierādīt, ka k!a dalās ar m.

41. Pierādīt nevienādības:

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

43. Pierādīt, ka no n dažādiem skaitļiem var izveidot vismaz 1/2n(n+1), dažādas summas, kurās katrs skaitlis ieiet ne vairāk kā vienu reizi. (Summas ir dažādas, ja to vērtības atšķiras.)

44. Plaknē novilktas n riņķa līnijas; Tās sadala plakni apgabalos. Pierādīt, ka, nokrāsojot katru apgabalu vienā no divām dotajām krāsām, var tā nokrāsot visu plakni, ka jebkuri divi apgabali ar kopēju robežu- riņķa līnijas loku- ir dažādās krāsās.

45. Plaknē novilktas n riņķa līnijas un katrā no tām novilkta horda. Riņķa līnijas un hordas sadala plakni apgabalos. Pierādīt, ka, nokrāsojot katru apgabalu vienā no trim dotajām krāsām, var tā nokrāsot visu plakni, ka jebkuri divi apgabali ar kopēju robežu- riņķa līnijas loku vai nogriezni- ir dažādās krāsās.

46. Vispārināt 44. un 45. uzdevumu un 23. piemēru telpas gadījumam.

47. Dotas divas paralēlas taisnes. Uz vienas no tām atlikts nogrieznis. Izmantojot tikai lineālu bez iedaļām, sadalīt šo nogriezni n kongruentās daļās (n- naturāls skaitlis).

48. Doti n papīra kvadrāti. Pierādīt, ka šos kvadrātus iespējams sagriezt daļās tā, lai no iegūtajām daļām varētu salikt vienu kvadrātu. (Daļas saliekot nedrīkst pārklāties, un nedrīkst palikt arī tukši laukumi.)

49. Plaknē doti 2n+1 punkti. Izmantojot cirkuli un lineālu, konstruēt (2n+1)-stūri, kuram šie punkti ir malu viduspunkti.

50. Pierādīt, ka 26. piemēra risinājumā kopu S`_k ar vajadzīgajām īpašībām vienmēr var konstruēt.

51. Plaknē doti n punkti, kas visi neatrodas uz vienas taisnes. Pierādīt, ka tādu taišņu, kas katra iet vismaz caur diviem dotajiem punktiem, ir ne mazāka kā n.

52. Pierādīt, ka sakarīgā kartē (sk. 29. piemēru) ir vai nu virsotne, no kuras izriet tikai viena robeža, vai arī noslēgta kontūra.

53. Dotas vienāda izskata monētas un sviras svari bez atsvariem. Visām monētām, izņemot vienu, ir vienāda masa (tās ir īstas). Vienas monētas masa atšķiras no pārējo monētu masas, bet nav zināms, vai tā ir vieglāka vai smagāka kā pārējās (tā ir viltota). Izmantojot n svēršanas, atrast viltoto monētu un noskaidrot, vai tā ir vieglāka vai smagāka nekā pārējās.

Nākamie pieci uzdevumi noder pētījumam skolēnu zinātniskajā darbā.

*54. Pierādīt, ka 31. piemērā konstruētais atsvaru komplekts ir vienīgais ar vajadzīgo īpašību.

*55. Atrisināt 31. piemēru un 54. uzdevumu, izmantojot divnieku skaitīšanas sistēmu.

*56. Pierādīt, ka nav tāda atsvaru komplekta, kas apmierina 31. piemēra nosacījumus, ar kuru var jebkuru ķermeni, kura masa gramos ir naturāls skaitlis starp 1 un M, ja M2ⁿ.

*57. Ar doto atsvaru komplektu, kas sastāv no n atsvariem, liekot atsvarus uz abiem svaru kausiem, var nosvērt jebkuru ķermeni, kura masa gramos ir naturāls skaitlis starp 1 un M. Cik liels var būt M?

*58. Cik ir tādu n atsvaru komplektu, ar kuriem var sasniegt maksimālo iespējamo M 57. uzdevumā?

1. Ja k- naturāls skaitlis; k3, tad skaitli 9k+20 nevar izteikt ar k saliktu nepāra skaitļu summu. Pierādīt to.

Nākamie 11. uzdevumi arī var noderēt skolēnu zinātniskās biedrības darbā.

*60. Pierādīt, ka 34. piemērā 2n-4 ir mazākais sarunu skaits, ar kuru katra no pļāpām var uzzināt visas jaunākās ziņas.

*61. Pieņemsim, ka nevienai pļāpai nav telefona, un informāciju viņas izplata ar vēstulēm. Pierādīt, ka 2n-2 ir mazākais vēstuļu skaits, kurš jāuzraksts, lai katra no viņām uzzinātu visas jaunās ziņas (n- pļāpu skaits).

*62. Pieņemsim, ka katrai pļāpai ir telefons, un katra telefona saruna ilgst vienu stundu. Telefona sarunas, protams, var risināties paralēli, bet katra pļāpa vienlaikus var piedalīties tikai vienā telefona sarunā. Pierādīt, ka vismazākais stundu skaits, pēc kura katra pļāpa var uzzināt visas jaunās ziņas, ir

a) [log₂n], ja n- pāra skaitlis;

b) [log₂n]+1, ja n- nepāra skaitlis.

*63. Pieņemsim, ka pļāpām nav telefona, un ar informāciju viņas apmainās pie kafijas tases vakaros. Katra pļapa, katru dienu var piedalīties tikai vienā kafijas vakarā; katrā kafijas vakarā piedalās ne vairāk kā k pļāpas. Pierādīt, ka minimālais dienu skaits, kurās katra no pļāpām var uzzināt visas jaunās ziņas, ir

a) [log_kn], ja n dalās ar k;

b) ,

P i e z ī m e. Acīmredzot 62. uzdevums un 63. uzdevuma speciāls gadījums, kad k=2.

*64. Pieņemsim, ka pļāpām nav telefona, un informāciju viņas nodod cita citai ar vēstulēm. Katra pļāpa ik dienas var uzrakstīt ne vairāk kā k vēstules un izlasīt ne vairāk kā k vēstules (pieņemsim, ka vēstules nogādā adresātam tajā pašā dienā, kad tās uzrakstītas, un katra vēstule jāizlasa tajā pašā dienā, kad tā saņemta). Vēstules raksta priekšpusdienās un saņem pēcpusdienās. Pierādīt, ka minimālais dienu skaits, pēc kurām katra pļāpa var uzzināt visas jaunākās ziņas, ir [log_k+1n) (n- pļāpu skaits).

*65. Vai jaunumu uzzināšanai nepieciešamais dienu skaits 64. uzdevumā samazinās, ja saņemtās vēstules lasīšanu var atlikt uz nākošo dienu?

*66. Pieņemsim, ka informācija izplatās tā, kā norādīts 64. uzdevumā, bet neviena pļāpa nevar vienā un tajā pašā dienā gan lasīt, gan rakstīt vēstules. Pierādīt, ka pļāpas var tā organizēt sarakstīšanos, ka pēc 2[log_k+1n] dienām viņas visas zinās visas jaunās ziņas (n- pļāpu skaits).

*67. Pieņemsim, ka pļāpām nav telefonu, un katra no viņām var katru dienu vai nu uzrakstīt vienu vēstuli, vai izlasīt vienu vēstuli. Vēstules adresātam tiek nogādātas tajā pašā dienā, kad uzrakstītas, un katra vēstule jālasa tajā dienā, kad tā saņemta. Turklāt vēstules tiek rakstītas priekšpusdienā, bet lasītas pēcpusdienā. Pieņemsim, ka pļāpu skaits n apmierina nevienādības

,

kur (a_k)- Fibonači skaitļu virkne (sk. 21. lpp.). Pierādīt, ka pļāpas var tā organizēt sarakstīšanos, ka viņas visas uzzina visas jaunās ziņas

a) pēc k+1 dienām, ja n- pāra skaitlis;

b) pēc k+3 dienām, ja n- nepāra skaitlis.

*68. Pieņemsim, ka pļāpām nav telefonu, un katra pļāpa katru dienu var vai nu uzrakstīt divas vēstules, vai arī izlasīt divas vēstules. Vēstules adresātam tiek nogādātas tajā pašā dienā, kad uzrakstītas. Pieņemsim, ka pļāpu skaits n apmierina nevienādības

,

kur (b_k)- Pella skaitļu virkne: b₀=0, b₁=1, b_n=2b_n-1+b_{n-2 .} Pierādīt, ka pļāpas var tā organizēt sarakstīšanos, ka katra pļāpa uzzina visas jaunās ziņas

a) pēc k+1 dienām, ja n- pāra skaitlis;

b) pēc k+3 dienām, ja n- nepāra skaitlis.

*69. Vai jaunumu uzzināšanai pietiekamo dienu skaits 66, 67. un 68. uzdevumā samazinās, ja vēstuļu lasīšanu var atlikt uz citu dienu?

*70. Mēģiniet atrast jauno ziņu uzzināšanai nepieciešamo minimālo dienu skaitu 66.-69. Uzdevumā.

P i e z ī m e. "Pļāpu uzdevumu" vairums (izņemot 61. uzdevumu) ir ļoti grūti risināmi. Tāpēc ievērojams sasniegums būs arī kāda uzdevuma daļēja atrisināšana.

71. Vai 35. piemērā laupītāji var tā sadalīt laupījumu, lai katrs uzskatītu, ka ir

saņēmis vismaz daļu no laupījuma un neviens cits laupītājs nav saņēmis vairāk par viņu?

72. Tūristu grupā ir n cilvēki, kas cits citu nepazīst. Pierādīt, ka dažus no viņiem var iepazīstināt savā starpā tā, lai nekādiem trim grupas cilvēkiem nebūtu šajā grupā vienāds paziņu skaits.

73. Grupā ir n savstarpēji nepazīstami cilvēki. Katram grupas loceklim ir daži paziņas ārpus šīs grupas. Vai var iepazīstināt dažus šīs grupas locekļus savā starpā tā, lai nekādiem trim grupas locekļiem paziņu skaits (ieskaitot arī "ārējos"paziņas) nebūtu vienāds?

74. Uz apļveida šosejas, kuras garums ir 100 km, stāv n automašīnas. Kopējais benzīna daudzums tajās ir pietiekams, lai nobrauktu 101 km. Pierādīt, ka ir viena tāda automašīna, kas, uzsākot braukšanu ar savu benzīnu un pa ceļam savācot benzīnu no pārējām automašīnām, var veikt pilnu apli. (Benzīnu no vienas mašīnas drīkst pārliet otrā tikai tad, kad abas mašīnas atrodas blakus; mašīnu stumt nedrīkst.)

75. Pierādīt, ka izteiksmē x₁: x₂: x₃: …: x_n-1: x_n dažādos veidos saliekot iekavas, var iegūt 2^n-2 dažādas algebriskas daļas.

76. Doti n skaitļi a₁, a₂, …a_n, a_{i 1 visiem} i=1, 2, …, n.

Aplūkosim izteiksmi ₁a₁,+ ₂a₂+_…+_na_n, kurā katrs no koeficientiem _i ir vai nu 1, vai arī -1. Pierādīt, ka koeficientus _i var izraudzīties tā, lai būtu pareiza nevienādība

₁a₁,+ ₂a₂+_…+ _na_n1.

77. Plaknē doti n vektori , to garumi nepārsniedz 1. Aplūkosim izteiksmi , kurā katrs no koeficentiem _i ir vai nu 1, vai arī -1. Pierādīt, ka koeficientus _i var izraudzīties tā, lai būtu pareiza nevienādība

*78. Atrisināt 37. piemēra uzdevumu, neizmantojot matemātisko indukciju.

79. Figūru sauc par izliektu, ja līdz ar katriem diviem tās punktiem A un B arī nogriežņa [AB] katrs punkts pieder pie šīs figūras.

Pierādīt teorēmas:

a) ja plaknē dotas n, n 3 izliektas figūras un jebkurām trim no tām ir kopējs punkts, tad visām n figūrām ir kopējs punkts;

b) ja telpā dotas n, n 4 izliektas figūras un jebkurām četrām no tām ir kopējs punkts, tad visām n figūrām ir kopējs punkts.

Šo teorēmu sauc par Helli teorēmu plaknē (telpā).

*80. Aplūkojam n, n3 lineārās nevienādības ar mainīgajiem x un y:

a₁x+ b₁y+c₁>0,

a₂x+b₂y+c₂>0.

. . . . . . . .

a_nx+b_ny+c_n>0

Pierādīt, ka visām n nevienādībām ir kopējs atrisinājums, ja jebkurām trim no tām ir kopējs atrisinājums.

*81. Vispārināt 80. uzdevumu nevienādībām ar trim mainīgajiem.

82. Plaknē doti vairāki punkti un vairāki vektori; katrs no vektoriem sākas kādā no dotajiem punktiem un beidzas kādā no dotajiem punktiem. Turklāt katrā punktā sākas tikpat daudz vektoru, cik tajā beidzas. Pierādīt, ka visu vektoru summa ir nulles vektors.

83. Izliektā daudzskaldnī, kura tilpums ir 1 tilpuma vienība, izraudzīti kaut kādi 3(2ⁿ-1) punkti. Pierādīt, ka no šī daudzskaldņa var sagriezt daudzskaldni, kura iekšpusē neatrodas neviens no dotajiem punktiem un kura tilpums ir tilpuma vienības.

*84. Vai 83. uzdevumā mazāko daudzskaldni var sagriezt tā, lai arī uz tā robežas neatrastos neviens no dotajiem punktiem?

85. Koordinātu ass punktos x₁, x₂, …,x_n atrodas punktveida masas m₁, m₂, …,m_n. Pierādīt, ka to smaguma centrs atrodas punktā

.

86. Uz rūtiņu papīra uzzīmēts daudzstūris, kura malas iet pa rūtiņu līnijām. Pierādīt, ka tā smaguma centru var konstruēt, izmantojot tikai lineālu.

87. Alfabētā ir n, n2 burti. Uz riņķa līnijas uzrakstīti vairāki burti tā, ka

a) divi vienādi burti nav uzrakstīti blakus;

b) katriem diviem alfabēta burtiem a un b var tā novilkt taisni, ka visi uz riņķa

līnijas uzrakstītie burti a atrodas vienā pusē no šīs taisnes, bet visi burti b- otrā pusē.

Pierādīt, ka ir uzrakstīti ne vairāk kā 2n-2 burti.

88. Skaitļu virkni (a_n) definē šādi: a₁=5, a_n+1=a_n². Pierādīt, ka locekļu a_n+1 un a_n pēdējie n cipari sakrīt.

ĪSS LITERATŪRAS APSKATS

Matemātiskās indukcijas principa izklāstu var atrast, piemēram, darbā [7]; turpat ir arī aprakstīti daudzi 1. teorēmas pielietojumi. Daudzus uzdevumus var atrast grāmatā [8], darbos [4] un [9], Kā arī uzdevumu krājumā [10].

Dažādus matemātiskās indukcijas metodes pielietojumus sarakstu sastādīšanā, kārtošanā un pārveidošanā (līdzīgi kā 27. piemērā) var atrast darbā [11]. Uzdevumos, kas saistīti ar grafiem (29. piemērs), matemātisko indukciju lieto ļoti plaši: sk., piemēram, [12], [7]. Indukcijas pielietojumus karšu krāsošanas problēmās var atrast darbos [2], [7], [13]; sarežģīta ir grāmata [14]. Uzdevumiem par svēršanu literatūra norādīta pēc 11. paragrāfa.

32. piemērs un 59. uzdevums sasaucas ar slaveno Goldbaha problēmu: pierādīt, ka katru pāra skaitli, sākot ar 4, var izteikt ar divu pirmskaitļu summu. Šī problēma nav atrisināta vēl šodien; par tās vēsturi sk., piemēram, [15].

Uzdevumu sērija par pļāpām (60.-70. uzdevumi, 34. piemērs) veltīta problēmai, kas cieši saistās ar jautājumu par informācijas optimālu izplatīšanu. Šajā nozarē notiek aktīvs zinātnisks darbs (sk., piemēram, [16]). Helli teorēma (37. piemērs, 79.-81. uzdevums) ir viena no teorēmām, kas rod pielietojumu dažādās matemātiskās nozarēs visnegaidītākajā veidā; acīmredzot tās būtība vēl nav pilnīgi izprasta. Šīs teorēmas pielietojumiem veltīta plaša literatūra (piemēram, [17], [18]).

Ābela formulas (28. uzdevums) ģeometrisks pierādījums atrodams darbā [19]. Citus summu aprēķināšanas paņēmienus var atrast rakstos [20], [21]. Literatūra par Fibonači skaitļiem norādīta pēc nākamā paragrāfa.

Ļoti interesantus uzdevumus par smaguma centru un tā pielietojumiem matemātikā var atrast grāmatā [22].