4. NODAĻA

SAREŽĢĪTĀKAS VIENDIMENSIONĀLAS VIENVIRZIENA INDUKCIJAS SHĒMAS

Iepriekšējā 3.nodaļā iepazināmies ar tradicionālo matemātiskās indukcijas metodi. Gandrīz visi uzdevumu krājumos atrodamie uzdevumi ir atrisināmi, izmantojot MIP un 1. teorēmu. Bet dažreiz ir izdevīgi izmantot to vispārinājumus.

Atcerēsimies vēlreiz, ka, lai pierādītu vispārīgu apgalvojumu, jāpierāda visi atsevišķie apgalvojumi, kurus tas satur. Kā to izdara, tas ir uzdevuma risinātāja ziņā. Ģeometriskajā interpretācijā jāizkrāso visa figūra, kas attēlo vispārīgo apgalvojumu, vienalga, ar kādu krāsošanas paņēmienu; neviena rūtiņa, kas atbilst kādam atsevišķam apgalvojumam, nedrīkst palikt balta - neaizkrāsota.

2. teorēma.

24. zīm.

Attēlosim vispārīgo apgalvojumu A(n), np grafiski (24. zīm.).

Pirmā rūtiņa atbilst parametra vērtībai p, otrā- parametra vērtībai p+1 utt. Izmantojot grafisko interpretāciju, 2. teorēma ir šāda: ja ir aizkrāsotas divas pirmās rūtiņas un iegūtas tiesības aizkrāsot rūtiņu, kura atrodas tieši uz divām blakus esošām aizkrāsotām rūtiņām, tad var aizkrāsot visas bezgalīgi daudzās rūtiņas. Rūtiņu aizkrāsošanas shēma ir šāda: .

40. piemērs. Skaitļu virkni a₁, a₂, a₃, …a_n, … definē šādi:

a1=0, a2=1, an+2=3an+12an

(A(n))

Pierādīt, ka a_n=2^n-1-1.

Pārbaudīsim 2. teorēmas nosacījumus.

Apgalvojums A(1) "a₁=2⁰-1", ko iegūst no vispārīgā apgalvojuma A(n) "a_n= 2^n-1-1", ja n=1, ir patiess, tātad pirmo rūtiņu drīkst aizkrāsot. Apgalvojums A(2) "a₂=2^2-1-1=1" arī ir patiess, tātad aizkrāsot drīkst arī otro rūtiņu.

Pamatosim tagad tiesības aizkrāsot rūtiņu, kat atrodas tieši aiz divām jau aizkrāsotām blakus rūtiņām: , t.i., pārbaudīsim 2. teorēmas nosacījumu b). Pieņemsim, ka apgalvojumi A(k) un A(k+1) ir patiesi, t.i., ka a_k=2^k-1-1 un a_k+1 =2^k-1. Saskaņā ar virknes definīciju un induktīvo pieņēmumu a_k+2=3a_k+1-2a_k=3(2^k-1)-2(2^k-1-1)= 32^k-3-2^k+2=22^k-1=

=2^k+1-1=2^(k+2)-1-1, t.i., arī apgalvojums A(k+2) ir patiess. Līdz ar to, pamatojoties uz 2. teorēmu, esam pierādījuši, ka vispārīgais apgalvojums A(n) ir patiess.

41. piemērs.

Izmantosim 2. teorēmu:

b) pieņemsim, ka ir veseli skaitļi.

Viegli pārbaudīt vienādību

,

(1)

no kurienes izriet vienādība

.

(saskaņā ar induktīvo pieņēmumu) ir veseli skaitļi, tad arī ir vesels skaitlis. 2. teorēmas nosacījumi apmierināti, tātad varam apgalvot, ka katram naturālam n.

Dažiem lasītājiem varbūt nav saprotams, kapēc mēs aplūkojam vienādību (1), nevis kādu citu vienādību. Kā varēja iedomāties, ka jāaplūko tieši šī vienādība? Tomēr skaidrs, ka, risinot uzdevumu ar indukcijas metodi, jāizmanto tas, ka ir veseli skaitļi; pierādīt, ka ir vesels skaitlis, būs visērtāk, ja izteiksmi izdosies izteikt ar , izmantojot reizināšanas, saskaitīšanas un atņemšanas operācijas.

Turpmākajos uzdevumos izmantosim Fibonači un Lukasa skaitļus.

Par Fibonači skaitļu virkni sauc virkni f₁=1, f₂=1, f₃=2, f₄=3, f₅=5,…., kurā katrs loceklis, sākot ar trešo, ir divu iepriekšējo locekļu summa.

Par Lukasa skaitļu virkni sauc virkni l₁=2, l₂=1, l₃=2, l₄=4, l₅=7,…, kurā katrs loceklis, sākot ar trešo, ir divu iepriekšējo locekļu summa.

Turpmākajos piemēros nepārbaudīsim 2. teorēmas nosacījumu a), ja pārbaude triviāla.

42. piemērs. Pierādīt, ka f_n +f_n+2=l_n+2.

Bāze. Ja n=1, tad f₁+f₃=1+2+3=l₃;

ja n=2, tad f₂ +f₄=1+3+=4=l₄.

Pāreja. Pieņemsim, ka apgalvojumi ir patiesi, ja n=k un n=k+1, t.i.,

fk+fk+2=lk+2 un	(1)
fk+1+fk+3= lk+3	(2)

Saskaitot vienādības (1) un (2), saskaņā ar Fibonači un Lukasa skaitļu definīcijām iegūstam

f_k+F_k+2+f_k+1+f_k+3=l_k+2+l_k+3, jeb

(f_k+f_k+1)+(f_k+2+f_k+3)=l_k+2+l_k+3, tātad

f_k+2+f_k+4=l_k+4,

t.i., pierādāmais apgalvojums ir patiess arī tad, ja n=k+2, un tātad f_n +f_n+2=l_n+2 visiem naturāliem n.

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

Izdarīsim indukciju pēc m.

Pāreja. Pieņemsim, ka pierādāmā vienādība pareiza, ja m=k un k+1, t.i., pareizas vienādības

Saskaitot šīs vienādības, iegūstam, ka

t.i., pierādāmā vienādība ir pareiza, ja m=k+2, un līdz ar to tā pareiza katram mN, nN un n>1.

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

Pāreja. Pieņemsim, ka formula pareiza, ja n=k un n=k+1. Tad

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

Bieži nākas izmantot arī citas indukcijas shēmas.Vienu no tām apraksta 3. teorēma.

3. teorēma.

Tātad, pārbaudot 3. teorēmas 2. nosacījumu, mēs pieņemam, ka A(k) ir patiess visām parametra k vērtībām, kas mazākas nekā m, un pierādām, ka tādā gadījumā ir patiess arī apgalvojums A(m).

Ģeometriski ilustrējot 3. teorēmu, lai nokrāsotu visu bezgalīgo lenti, vispirms aizkrāsojam tās pirmo rūtiņu (bāze) un pēc tam iegūstam tiesības izmantot šādu likumu: ja no lentes sākuma līdz pat kādai rūtiņai n visas iepriekšējās rūtiņas ir aizkrāsotas, tad drīkst aizkrāsot arī rūtiņu n (25. zīm.)

25. zīm.

Viegli pārliecināties, ka, tā rīkojoties, pakāpeniski var aizkrāsot visas rūtiņas.

45. piemērs. Skaitļu virkni a₁, a₂, a₃ …a_n, definē šādi: a₁=1, a₂=1, a_n+2=a₁+a₂ +…+a_n-1+ +a_n+ a_n+1. Pierādīt, ka a_n+2=2ⁿ.

Pierādīsim apgalvojuma A(n) "a_n+2= 2ⁿ" patiesumu, ja n=1.

Tiešām

Pieņemsim, ka patiesi ir apgalvojumi A(1), A(2),…,A(m-1), un pierādīsim, ka patiess ir arī apgalvojums A(m). Tiešām, ja a₃=2¹, a₄=2², a₅=2³, …, a_m=2^m-2, a_m+1=2^m-1, tad a_m+2=a₁+a₂+…+a_m+a_m+1=1+(1+2¹+2²+2³+…+2^m-2+2^m-1=1+2^m-1=2^m (izteiksme iekavās ir ģeometriskās progresijas summa; tās aprēķināšanas formula pierādīta skolas kursā), t.i., apgalvojums A(m) ir patiess, tātad patiess arī vispārīgais apgalvojums A(n).

46. piemērs. Pierādīt, ka katram n-stūrim (ne noteikti izliektam!) var novilkt vismaz n-3 diagonāles, kas atrodas tā iekšpusē.

Pēreja. Pieņemsim, ka apgalvojums ir patiess trijstūriem, četrstūriem, piecstūriem, …, (m-1)-stūriem, un aplūkosim kaut kādu m-stūri. Ja tas ir izliekts, tad no katras šī daudzstūra virsotnes izriet m-diogonāles, kas atrodas tā iekšpusē. Ja daudzstūris ir ieliekts, apskatām virsotni, pie kuras m-stūra iekšējais leņķis lielāks nekā 180^o. No šīs virsotnes izriet vismaz viena diogonāle, kas atrodas m-stūra iekšpusē (pierādīt to patstāvīgi !); šī diogonāle sadala m-stūri k₁-stūrī un k₂-stūrī, pie kam k₁<m, k₂<m un k₁+k₂=m+2. Pēc induktīvā pieņēmuma k₁-stūra iekšpusē atrodas vismaz k₂-3 diogonāles (kas arī ir dotā m-stūra diogonāles), tāpēc dotā m-stūra iekšpusē atrodas vismaz (k₁-3)+(k₂-3)+1=k₁+k₂-5= (m+2)-5=m-3 diogonāles, ko arī vajadzēja pierādīt.

47. piemērs. Atrisināsim 3. § 82. uzdevumu, izmantojot 3. teorēmu. Izdarīsim indukciju pēc to vektoru skaita s, kas nav nulles vektori.

Bāze. Acīmredzot s2 vai s=0, apgalvojums acīmredzot ir patiess; ja s=2, tad abi nenullvektori ir viens otram pretēji vērsti, un tātad to summa ir .

Pāreja. Pieņemsim, ka apgalvojums patiess, ja s<m, un aplūkosim gadīijumu, kad s=m. Izvēlēsimies vienu no dotajiem punktiem A un sāksim iet no tā pa kādu no nenullvektoriem, kuru sākumpunkts ir A. Ceļu turpinām tik ilgi, cik iespējams, neejot divas reizes pa vienu un to pašu vektoru. Tā kā visu aplūkojamo vektoru skaits ir galīgs, tad agri vai vēlu mums būs jāapstājas. Apstāšanās varēs notikt tikai punktā A, jo katrā punktā ieiet tikpat daudz nenullvektoru, cik no tā iziet.

Līdz apstāšanās brīdim punktā A visu to vektoru summa, pa kuriem esam gājuši, ir , jo maršruta sākuma punkts sakrīt ar beigu punktu. Katrā punktā ieiet tikpat daudz izstaigāto vektoru, cik no tā iziet. Tāpēc katrā punktā ieiet arī tikpat daudz neizstaigāto nenullvektoru, cik no tā iziet; bet neizstaigāto nenulvektoru skaits ir mazāks nekā m. Tāpēc saskaņā ar induktīvo pieņēmumu to summa ir , un tātad arī visu sākumā doto nenullvektoru summa ir .

48. piemērs. Apzīmēsim ar p₁, p₂,…,p_n,…visu pirmskaitļu augošu virkni. Pierādīt, ka

Pāreja. Pieņemsim, ka pierādāmā nevienādība ir pareiza ar pirmskaitļiem p₁, p₂,…,p_m-1. Aplūkosim skaitli k=p₁, p₂,…p_m-2p_m-1+1. Tas nedalās ne ar vienu no pirmskaitļiem p₁, p₂,…,p_m-2, p_m-1, jo, dalot šo skaitli ar kādu no minētajiem pirmskaitļiem, atlikums ir 1; tātad skaitlis k vai nu pats ir kāds no pirmskaitļiem p_m, p_m+1,…, vai arī dalās ar kādu no šiem pirmskaitļiem. Viegli redzēt, ka

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

49. piemērs. Kādā pilsētā ir vairāki laukumi un ielas, kas tos savieno; katra iela savieno divus laukumus un neiet caur citiem laukumiem. Dažās ielās ir divvirzienu kustība, citās- vienvirziena kustība; no katra laukuma uz jebkuru citu laukumu var aizbraukt. Remonta dēļ tajās ielās, kurās bija divvirzienu kustība, pārgāja uz vienvirziena kustību, bet tajās ielās, kurās bija vienvirziena kustība,- uz divvirzienu kustību. Izrādījās, ka arī tagad no katra laukuma uz katru var aizbraukt. Pierādīt, ka visās šīs pilsētas ielās var noteikt vienvirziena kustību tā, lai no katra laukuma varētu aizbraukt uz jebkuru citu laukumu.

Bāze. Ja pilsētā ir tikai 2 laukumi A un B, tad saskaņā ar uzdevuma nosacījumiem jābūt divām dažādām ielām, kas savieno A un B. Uz vienas no šīm ielām nosakām braukšanas virzienu AB, uz otras- virzienu BA.

Pāreja. Pieņemsim, ka mēs protam izvēlēties braukšanas virzienu saskaņā ar uzdevuma nosacījumiem pilsētās, kurās ir mazāk nekā m laukumi. Aplūkosim pilsētu ar m laukumiem (m>2).

Izvēlēsimies divus laukumus A un B, kurus savieno iela. Tad eksistē tādi laukumi L₁, L₂,…,L_k, ka A savienots ar L₁, L₁ savienots ar L₂,…, L_k-1 savienots ar L_k, L_k savienots ar B; ja tāda "cikla" nebūtu, tad brīdī, kad uz ielas starp A un B noteikta vienvirziena kustība, nebūtu iespējams aizbraukt no B uz A (vai arī no A uz B).

Izveidosim jaunu pilsētu; no dotās tā atšķiras ar to, ka laukumi A, B, L₁,…, L_k apvienoti vienā laukumā . Laukumu un visus tos laukumus, ar kuriem dotajā pilsētā bija savienots kaut viens no laukumiem A, B, L₁, …, L_k, savieno ielas. Jaunajā pilsētā laukumu skaits mazāks nekā m, tāpēc tajā pēc induktīvā pieņēmuma var izvēlēties braukšanas virzienus uz ielām saskaņā ar uzdevuma nosacījumiem. Dotajā pilsētā saglabāsim visus jaunās pilsētas braukšanas virzienus, bet starp laukumiem A, B, L₁, …L_k braukšanas virzienus noteiksim šādi:

AL₁, L₁L₂ …, L_k-1L_k, L_kB, BA.

50. piemērs. Izmantojot MIP, nav grūti pierādīt, ka

Parādīt, ka katram naturālam k izteiksme 1^k+2^k+…+n^k=P_k+1n (n) ir (k+1)-ās pakāpes polinoms ar mainīgo n, kurā koeficents pie .

Pierādīsim šo apgalvojumu, izmantojot 3. teorēmu:

1. ja n=1, apgalvojuma patiesums izriet no aritmētiskās progresijas pirmo n locekļu summas formulas:

1. pieņemsim, ka apgalvojums ir patiess, ja k=1, 2, …, m-1, t.i., ka

1+2+3+…+n=P₂(n);

1²+2²+3²+…+n²=P₃ (n)

1³+2³+3³+…+n³= P₄(n);

. . . . . . . . . . . .

1^m-1+2^m-1+3^m-1+…+n^m-1=P_m(n),

kur P_i(n) ir i-tās pakāpes polinoms ar argumentu n, un koeficents pie nⁱ ir . Mēģināsim atrast 1^m+2^m+…+n^m.

Ņūtona binoma formula

ir identitāte. Ievietosim šajā identitātē x vietā vērtības x=0, x=1, …, x=n. Iegūsim vienādības

Saskaitīsim šīs vienādības:

Atmetīsim iegūtās vienādības abās pusēs saskaitāmo 1^m+1+2^m+1+…+n^m+1 un izmantojot induktīvo pieņēmumu, aizstāsim iekavas vienādības labajā pusē attiecīgi ar P₂(n), P₃(n),…,P_m(n).

Iegūsim vienādību

un, atceroties, ka

Šīs vienādības labajā pusē kvadrātiekavās ir argumenta n tādu polinomu summa, kuru pakāpes nepārsniedz m, bet, izvirzot pēc Ņūtona binoma formulas (n+1)^m+1, iegūst polinomu ar argumentu n, , kura locekļu augstākā pakāpe ir m+1, tāpēc iegūtās vienādības labās puses polinomā koeficents pie n^m+1 ir 1. Dalot vienādības abas puses ar (m+1), iegūst vajadzīgo.

Visās līdz šim apskatītajās indukcijas shēmās var saskatīt šādu kopēju iezīmi: izdarot induktīvo pāreju, atsevišķā apgalvojuma A(k+1) patiesums izriet no dažu iepriekšējo atsevišķo apgalvojumu patiesuma (starp tiem ir arī apgalvojums A(k)). Ģeometriskajā ilustrācijā, aizkrāsojot kādu jaunu rūtiņu, iepriekšējā rūtiņa noteikti bija jau aizkrāsota.

Ja mēs iedomātos, ka pa rūtiņu lenti soļo bruņinieks, pakāpeniski atbrīvojot lenti no ienaidnieka un atbrīvotās rūtiņas aizkrāsojot, tad iegūtu, ka, rīkojoties saskaņā ar jau apskatītajām shēmām, bruņinieks vienmēr izdzen ienaidnieku no rūtiņas, kas atrodas blakus tai, kurā viņš stāv.

Bet vēsture pazīst arī citus uzbrukuma veidus. Piemēram, romiešu leģionā karavīri nostājās divās rindās viens aiz otra, izstiepjot pīķus uz priekšu; pie tam otrās rindas karavīru pīķi atradās pirmās rindas karavīru priekšā, aizsargājot tos. Leģionam ejot uzbrukumā, pirmās rindas pīķi apdraudēja nevis to telpu, kas atradās tieši šīs rindas priekšā, bet tālāko; telpu tieši pirmās rindas priekšā apdraudēja otrās rindas pīķi. (26. zīm.).

26. zīm.

Bieži vien matemātiskos pierādījumus izdevīgi izmantot indukcijas shēmu, kas atgādina minēto leģiona kaujas ierindu.

4. teorēma.

Ģeometriski nosacījums a) nozīmē tiesības aizkrāsot lentes pirmās k rūtiņas, bet nosacījums b)- tiesības aizkrāsot rūtiņu, kas atrodas par k rūtiņām pa labi no kādas jau aizkrāsotas rūtiņas. Šādas induktīvās pārejas shēma attēlota 27. zīmējumā

Viegli saprast, ka 1. teorēma ir 4. teorēmas speciālgadījums, ja k=1.

Ieteicams lasītājam pašam pārliecināties, ka var iekrāsot tās lentes visas rūtiņas, kas attēlo vispārīgo apgalvojumu A(n), np, ja apmierināti 4. teorēmas nosacījumi.

51. piemērs. Kādā valstī ir n pilsētas (n5). Jebkuras divas pilsētas savienotas ar ceļu. Ceļu krustojumu ārpus pilsētām nav (izmantoti viadukti). Pierādīt, ka uz ceļiem var noteikt vienvirziena kustību tā, ka no katras pilsētas uz jebkuru citu pilsētu var aizbraukt, braucot vai nu pa ceļu, kas savieno šīs divas pilsētas, vai caur kādu trešo pilsētu.

Izmantosim 4. teorēmu, ja p=5, k=2.

Bāze. 28. zīmējumā parādīts, ka noteikt kustības virzienus uz ceļiem, ja n=5 un n=6.

Pāreja. Pierādīsim, ka izvēlēties kustības virzienus, ja pilsētu skaits ir m+2 un kustības virzienus protam izvēlēties m pilsētu gadījumā.

28. zīm.

No aplūkojamām m+2 pilsētām izvēlamies kaut kādas m pilsētas. Pēc induktīvā pieņēmuma tās var savienot ar vienvirziena ceļiem tā, lai būtu apmierināti uzdevuma nosacījumu. Atliek izvēlēties kustības virzienus uz ceļiem, kas savieno šīs m pilsētas ar atlikušajām divām pilsētām A un B. Izdarām to šādi:

a) uz ceļiem, kas savieno A ar izraudzītajām m pilsētām, izvēlamies virzienu no A;

b) uz ceļiem, kas savieno B ar izraudzītajām m pilsētām, izvēlamies virzienu uz B;

c) uz ceļa AB izvēlamies virzienu BA.

52. piemērs. Uz rūtiņu papīra uzzīmēts kvadrāts, kura izmēri ir nn rūtiņas un malas iet pa rūtiņu līnijām. Kāds ir maksimālais rūtiņu skaits šajā kvadrātā, kuras var aizkrāsot tā, lai neviena figūra, kas kongruenta figūrai , nebūtu pilnīgi aizkrāsota?

Katru otro rindiņu atstājot neaizkrāsotu, bet citas rindiņas aizkrāsojot (29. zīm.), iegūstam, ka saskaņā ar uzdevuma nosacījumiem var aizkrāsot rūtiņas, ja n ir pāra skaitlis, bet rūtiņas, ja n ir nepāra skaitlis

29. zīm.

Pierādīsim, ka nevar aizkrāsot vairāk rūtiņu tā, lai būtu apmierināti uzdevuma nosacījumi.

1. Ja n- pāras skaitlis (n=2k), sadalām lielo kvadrātu k² tādos kvadrātos, kuru izmēri ir 22 rūtiņas. Katrā no šiem kvadrātiem nedrīkst aizkrāsot vairāk kā 2 rūtiņas, tātad kopējais aizkrāsoto rūtiņu skaits nepārsniedz .
2. Ja n- nepāra skaitlis, uzdevumu risināsim ar matemātisko indukciju. Skaidrs, ka nevar aizkrāsot vairāk kā rūtiņu, ja n=1. Pieņemsim, ka kvadrātā, kura izmēri ir (2k+1)x(2k+1) rūtiņas, nevar aizkrāsot vairāk kā rūtiņas. Aplūkosim kvadrātu, kura izmēri ir (2k+3)(2k+3) rūtiņas; jāpierāda, ka šādā kvadrātā nevar aizkrsot vairāk kā rūtiņas.

Tā kā kvadrātu ar izmēriem (2k+3)(2k+3) rūtiņas var iegūt, kavadrātam ar izmēriem (2k+1)(2k+1) rūtiņas pievienojot 30. zīmējumā attēloto figūru, tad pietiek pierādīt, ka 30. zīmējumā attēlotajā figūrā nevar aizkrāsot vairāk kā (2k²+7k+6)-(2k²+3k+1)=4k+5 rūtiņas tā, lai būtu apmierināti uzdevuma nosacījumi.

Sadalām katru no figūtām A₁A₂A₃A₄ un B₁B₂B₃B₄ (to izmēri ir 22k rūtiņas) k kvadrātos, kuru izmēri ir 22 rūtiņas; katrā no iegūtajiem 2k kvadrātiem drīkst aizkrāsot ne vairāk kā 2 rūtiņas, tātad abos taisnstūros A₁A₂A₃A₄ un B₁B₂B₃B₄ kopā drīkst iekrāsot ne vairāk kā 2k2=4k rūtiņas. Tieši pārbaudot, noskaidro, ka figūrā A₂CB₂B₁DA₃ drīkst aizkrāsot ne vairāk kā 5 rūtiņas.

30. zīm.

53. piemērs. n dažādi akmeņi (n5) sver 1 kg, 2 kg, …, n kg; skaitlis n vai nu dalās ar 3, vai arī atlikums, dalot ar 3, ir 2. Pierādīt, ka akmeņus var sadalīt 3 kaudzēs, kuru svari vienādi, nesaskaldot nevienu akmeni daļās.

Izmantosim 4. teorēmu, ja p=5, k=6.

Bāze. Ja n=5, 6, 8, 9, akmeņu sadalījums kaudzēs redzams tabulā.

Pāreja. Pierādīsim, ka kaudzēs ar vienādu masu var sadalīt akmeņus, kuri sver 1 kg, 2 kg, …, n kg, n+1 kg,…, n+6 kg, ja zināms, ka šāda veida kaudzēs var sadalīt akmeņus, kuri sver 1 kg, 2 kg, …, n kg.

Sakārtosim trīs vienādas masas kaudzēs akmeņus, kuri sver 1 kg, 2 kg, …, n kg. Pēc tam pievienosim vienai kaudzei n+1 kg un n+6 kg smagos akmeņus, otrai kaudzei- n+2 kg un n+5 kg smagos akmeņus, trešajai kaudzei- n+3 kg un n+4 kg smagos akmeņus.

54. piemērs. Pierādīt, ka katram naturālam skaitlim n var atrast tādu naturālu skaitli m un tādus skaitļus a_i, a_i=1 vai arī a_i=-1, i=1, 2, …, m, ka

n=a₁₁²+a₂₂²+…+a_mm².

Izmantosim 4. teorēmu, ja p=1, k=4.

Bāze. Viegli pārbaudīt, ka

1=1¹;

2=-1²-2² -3²+4²;

3=-1²+2²;

4=-1²-2²+3²,

Pāreja. Pieņemsim, ka

s=a₁₁²+a₂₂²+…+a_m m²,

kur visiem a_i=1 vai a_i=-1, visiem i=1, 2, …, m.

Tā kā (m+1)²-(m-2)²-(m+3)²+(m+4)²=4,

tad s+4=a₁₁²+a₂₂²+…+a_mm²+(m+1)²-(m-2)²-(m+3)²+(m+4)² .

55. piemērs. Pierādīt, ka jebkuru kvadrātu var sagriezt n kvadrātos, ja n6.

Izmantosim 4. teorēmu, ja p=6 un k=3.

Bāze. 31. Zīmējumā parādīts, kā kvadrātu var sagriezt 6, 7, un 8 kvadrātos.

Pāreja. Ja kvadrātu var sagriezt m kvadrātos, tad to var sagriezt arī m+3 kvadrātos: pietiek vienu no m kvadrātiem sagriezt 4 kongruentos kvadrātos.

31. zīm

56. piemērs. Pierādīt, ka katram nepāra skaitlim n, ja n25, eksistē tādi dažādi nepāra naturāli skaitļi x₁, x₂,…, x_n, ka

Uzdevumā minētie dažādie naturālie nepāra skaitļi eksistē, ja n=9 un ja n=11. Ar elektronu skaitļojamās mašīnas palīdzību atrasts, ka

Ja jums ir pacietība, varat to pārbaudīt.

Turpmākajā risinājumā izmantosim lemmu.

Lemma. Ja 56. piemēram eksistē atrisinājums ar n=m un n=s, tad tam eksistē arī atrisinājums ar n=m+(s-1).

Tiešām, pieņemsim, ka eksistē tādi naturāli nepāra skaitļi x₁<x₂<…<x_m, kuriem pareiza vienādība

un y₁< y₂< …<y_s ( arī naturāli nepāra skaitļi), kuriem

Tad

un tātad naturālie nepāra skaitļi x₁, x₂, …, x_m-1, x_my₁, …,x_my_s (to skaits ir m+s-1) apmierina 56. piemēra nosacījumus.

No lemmas un jau zināmajiem atrisinājumiem izriet, ka uzdevumam eksistē atrisinājums, ja n=9+8z+10l vai n=11+8z+10l, kur z un l- negatīvi veseli skaitļi. Ja n - naturāls nepāra skaitlis, n25, tad n=2t+1, t12, un tāpēc vienādības n=9+8z+10l un n=11+8z+10l var uzrakstīt formā

t=4+4z+5l	(1)
un
t= 5+4z+5l.	(2)

Uzdevums būs atrisināts, ja pierādīsim, ka katru naturālu t, t12 var izmantot formā (1) vai (2), kur z un l- veseli nenegatīvi.

Izmantosim 4. teorēmu, ja p=12 un k=4.

Bāze. Viegli redzēt, ka

12=4+42+50;

13=4+41+51;

14=4+40+52;

15=5+40+52.

Pāreja. Ja skaitli t₁ var izteikt formā (1) vai (2), tad arī t₁+4 var izteikt attiecīgi formā (1) vai (2); tiešām,

ja t₁= 4+4z₁+5l₁, tad t₁+4=4+4(z₁+1)+5l₁;

ja t₁= 5+4z₁+5l₁, tad t₁+4=5+4(z₁+1)+5l₁.

Par neatrisinātām problēmām, kas sastītas ar šo piemēru, sk. 57. lpp.

Uzdevumi paškontrolei IV

89. Pierādīt, ka

1. a_n=52²-3ⁿ⁺¹ , ja a₁=1, a₂=-7 un a_n+2=5a_n+1-6a_n visiem n1;
2. a_n=3ⁿ+7, ja a₁=10, a₂=16 un a_n+2=4a_n+1-3a_n visiem n1;
3. a_n=cos n, ja a₁= cos a₂=cos 2 un a_n+2=2 cos a_n+1-a_n visiem n1;
4. a_n= 2ⁿ+3ⁿ, ja a₁=1, a₂=-3, a₃=-29 un a_n+3-26a_n+1+24a_n visiem n1.

90. Pierādīt, ka Fibonači skaitļu virknē (sk. 21. lpp.)

91. Pierādīt, ka vienīgie naturālie skaitļi, kas ietilpst gan Fibonači, gan Lūkasa virknēs (sk. 17. lpp.) ir 1, 2, 3.

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

ir vesels skaitlis.

*93. Vai eksistē tāds naturāls m, ka var pierādīt teorēmu: katra m-stūra iekšpusē atrodas vismaz m-2 tā diogonāles?

94. Izliektā n-stūrī novilktas dažas diogonāles, kas sadala šo n-stūri trijstūros. Zināms, ka no katras virsotnes iziet pāra skaits novilkto diogonālu un ka jebkuras divas novilktās diogonāles ir bez kopējiem iekšējiem punktiem. Pierādīt, ka n dalās ar 3.

95. Pierādīt, ka katru naturālu skaitli var sadalīt pirmskaitļu reizinājumā.

96. Skaitļu virknei a₁, a₂,… ir šādas īpašības:

1. a₁=1;

1. visiem naturāliem k, k>1 ir pareiza nevienādība:

a_k1+a₁+a₂+…+a_k-1;

1. visi virknes locekļi ir naturāli skaitļi.

Pierādīt, ka katru naturālu skaitli var izteikt ar dažu (varbūt viena paša) šīs virknes locekļu summu

97. Skaitļi, x₁, x₂,…, x_n lielāki nekā 0 un mazāki nekā 1. Pierādīt, ka

98. Dažas no n pilsētām savienotas ar ceļiem tā, ka no katras pilsētas var aiziet uz jebkuru citu pilsētu. Zināms, ka katrā pilsētā ieiet pāra skaits ceļu. Pierādīt, ka ir iespējams, iziet no jebkuras pilsētas un, ejot pa katru ceļu tieši vienu reizi, atgriezties izejas punktā.

99. Doti naturāli skaitļi n un m, n2, m<n. Apskatīsim visus tos naturālos skaitļus, kuru decimālajā pierakstā ir ne vairāk kā n cipari. Sadalīsim tos divās grupās: vienā grupā tos skaitļus, kuru ciparu summa ir pāra skaitlis, otrā grupā- pārējos. Pierādīt, ka pirmās grupas skaitļu m-to pakāpju summa vienāda ar otrās grupas skaitļu m-to pakāpju summu.

100. Pierādīt, ka skaitli 30 var izteikt ar n piecinieku palīdzību, izmantojot iekavas un četru aritmētisko darbību zīmes, ja n3.

101. Pierādīt, ka katram naturālam n un katram pozitīvam x ir pareiza nevienādība

102. Skaitļu tabulā

katras rindiņas malējie skaitļi ir vieninieki, bet jebkuru citu tabulas skaitli a iegūst, saskaitot sakitli virs a ar tā blakus skaitļiem. Pierādīt, ka tabulā katrā rindiņā, sākot ar trešo, ir vismaz viens pāra skaitlis.

103. Atrisināt 53. piemēra uzdevumu, izmantojot nevis induktīvo pāreju nn+6, bet pāreju nn+3.

104. Pierādīt, ka katru naturālu skaitli var bezgalīgi daudzos veidos izteikt tā, kā prasīts 54. piemērā.

105. Pierādīt, ka kavdrātveida tabulā, kuras izmēri ir nn rūtiņas, ir iespējams ierakstīt skaitļus no 1 līdz n² (katrā rūtiņā citu skaitli) tā, lai visās kolonnās, visās rindiņās un abās diogonālēs ierakstīto skaitļu summas būtu vienādas (n- naturāls skaitlis, n3).

106. No sērkociņiem izveidota kvadrātveida tabula, kurā ir nn rūtiņas; katras rūtiņas malas garums ir viena sērkociņa garums. Pierādīt, ka jānoņem vismaz

lai nepaliktu neviena kvadrāta, kura malas izveidotas no sērkociņiem.

107. No punkta O iziet n vienības vektori (n- nepāra skaitlis), kas visi atrodas vienā pusplaknē. Pierādīt, ka to summas garums nav mazāks kā 1.

108. Pierādīt, ka kubu var sagriezt n kubos, ja n48.

*109. Pierādīt, ka kvadrātu nevar sagriezt 3 kvadrātos; 5 kvadrātos.

110. (Z. Ozolas teorēma.) Jebkuru trijstūri var sadalīt n vienādsānu trijstūros, ja n4, un n līdzīgos trijstūros, ja n6 vai arī n=4.

111. Pierādīt, ka 56. piemēra problēmai eksistē atrisinājums, ja n=17; 19; 21.

112. Pierādīt, ka 56. piemēra problēmai neeksistē atrisinājums, ja n- pāra skaitlis vai n<9.

! 113. Naturālu skaitli n sauc par labu, ja eksistē tādi (ne obligāti dažādi) naturāli skaitļi a₁, a₂,…, a_k, ka

Pierādīt, ka naturāls skaitlis n ir labs, ja n33.

ĪSS LITERATŪRAS APSKATS

Labākā grāmata par Fibonači skaitļiem krievu valodā ir [23]; izsmeļošus rezultātus var atrast žurnālā [24]. Par 50. piemērā minēto polinomu koeficentiem- Bernulli skaitļiem- arī ir plaša literatūra, kas aplūkota žurnālā [24]; sk. Arī rakstu [25].

Daudzi interesanti uzdevumi un neatrisinātas problēmas saistītas ar 56. piemēru; sk., piemēram, rakstu [26]. Nav zināms, vai 56. piemēra uzdevumam eksistē atrisinājums, ja n=13, 15 vai 23.

98. uzdevums saistīts ar t.s. Eilera cikla eksistences problēmu: kādiem grafiem eksistē noslēgts cikls, kas iet pa katru grafa šķautni tieši vienu reizi? Līdzīga problēma par Hamiltona cikla eksistenci- kādiem grafiem eksistē noslēgts ceļš, kas iet caur katru grafa virsotni tieši vienu reizi- ir viena no interesantākajām visā teorētiskajā kibernētikā; šodien nav zināms neviens algoritms, lai par katru grafu varētu pateikt, vai tam eksistē Hamiltona cikls vai ne, pie tam agrāk nekā visu variantu pārbaude pēc kārtas. Ja izdotos atrast šādu "ātru" algoritmu, mūsu rīcībā būtu ātras un efektīvas metodes praktiski visu svarīgāko kombinatorikas uzdevumu risināšanai. Par Hamiltona cikla eksistences nosacījumiem sk., piemēram, [27], bet par efektīviem un neefektīviem algoritmiem- grāmatas [28] un [29].

105. uzdevums veltīts t.s. maģiskajiem kvadrātiem; elementāro īpašību labs, bet nepilnīgs izklāsts atrodams darbos [30] un [31]. Šiem kvadrātiem un to vispārinājumiem veltīto darbu skaits aug eksponenciāli. Viena no pēdējām populārākajām, līdz šim neatrisinātām problēmām, ir šāda: kādi grafi ir maģiski? (Grafu ar n šķautnēm sauc par maģisku, ja tā šķutnes var tā sanumurēt, ka virsotnē ieejošo šķautņu numuru summa visām virsotnēm ir viena un tā pati.)

Interesanta problēmu grupa saistīta ar 108.-110. uzdevumu un 55. piemēru. Ir pierādīts, ka kubu var sadalīt n kubos, ja n=1; 8; 15; 20; 22; 27; 29; 34; 36; 38; 39; 41; 43; 45; 46 vai n48; varbūt lasītājiem izdosies atrast, kā? Citām n vērtībām uzdevums nav atrisināms. Kubu nevar sadalīt galīgā skaitā dažādu kubu; sk. rakstu [32]. Kvadrātu var sadalīt n dažādos kvadrātos, ja n=21 (sk.[3], bet to nevar izdarīt, ja n<21; līdz šim laikam nav zināmas visas tās n vērtības, kurām kvadrātu var sadalīt n dažādos kvadrātos. Par problēmām, kas saistītas ar šo jautājumu, sk.[34] un [35]; daudzas līdzīgas problēmas aplūkotas rakstā [36].

110. uzdevumā formulēto teorēmu, ko 1977. gadā pierādīja Rīgas L. Paegles 1. vidusskolas 11. klases skolniece Zaiga Ozola, var precizēt mazākām n vērtībām.

Divos vienādsānu trijstūros var sadalīt tikai taisnleņķa trijstūrus, trijstūrus, kuru leņķu lielumiem ir pareiza vienādība =2 vai =3, un nekādus citus trijstūrus.

Trīs vienādsānu trijstūros var sadalīt jebkuru šaurleņķa trijstūri un taisnleņķa trijstūri, kā arī jebkuru platleņķa trijstūri, kura leķu lielumiem ir pareiza kāda no vienādībām =2, =3, =4, =5, =6, =7, 2=3, 3=5, =+2, =+3, =+5, =2-2, =3-3, =3-4, =5-2,=/4, un nekādus citus trijstūrus.

Divos līdzīgos trijstūros var sadalīt tikai taisnleņķa un vienādsānu trijstūrus.

Trīs līdzīgos trijstūros var sadalīt tikai taisnleņķa un vienādsānu trijstūrus, kā arī trijstūrus, kuriem viens leņķis ir /3.

Piecos līdzīgos trijstūros var sadalīt tikai taisnleņķa un vienādsānu trijstūrus, kā arī trijstūrus, kuru leņķu lielumiem ir pareiza kāda no vienādībām = /3 vai =2 vai =2-2. Te , un - trijstūru iekšējo leņķu lielumi.