5. NODAĻA

DIVVIRZIENU INDUKCIJAS SHĒMAS

Šīs nodaļas apguve Jums ļaus elastīgi pielietot dažādas matemātiskās indukcijas shēmas. Salīdzinājumā ar iepriekšējām nodaļām, kur apguvām induktīvo pāreju "uz priekšu", tagad pratīsim to izdarīt arī pretējā virzienā - "uz atpakaļu". Tas ļaus Jums citus uzdevumus atrisināt racionālāk. Jūsu iespējas pieaugs ar katru atrisinātu problēmu.

Visu iepriekšējo nodaļu uzdevumos un piemēros induktīvā pāreja tika realizēta vienā virzienā- "uz priekšu". Ģeometriski: ar induktīvo pāreju ieguvām tiesības aizkrāsot lentes rūtiņu, kas atrodas pa labi no visām jau aizkrāsotajām rūtiņām. Citiem vārdiem: parametra vērtība, kurai vispārīgā apgalvojuma patiesumu pierādījām ar induktīvo pāreju, bija lielāka par parametra vērtībām, kurām vispārīgais apgalvojums patiess pēc indukcijas hipotēzes.

Aplūkotos uzdevumus ar šāda veida spriedumiem varēja samērā viegli atrisināt. Tomēr jāsaprot, ka visus lentes kvadrātiņus var aizkrāsot arī, nekrāsojot tos pēc kārtas. Piemēram, visi lentes kvadrātiņi tiktu aizkrāsoti arī tad, ja tos krāsotu šādā secībā: 2, 1, 4, 3, 6, 5, 8, 7,… Tātad, ja izdotos kāda uzdevuma risināšanai atrast indukcijas shēmu, kura atbilst minētajai krāsošanas secībai, un šī shēma izrādītos ērtāka nekā citas, to varētu bez šaubīšanās lietot- no indukcijas shēmas taču vajadzīga tikai iespēja pierādīt visu to atsevišķo apgalvojumu patiesumu, no kuriem sastāv vispārīgais apgalvojums.

Nākamajā teorēmā aplūkota minētā veida indukcijas shēma.

5. teorēma.

Ilustrēsim šo teorēmu grafiski. Nosacījuma b) grafiskais attēlojums ir šāds:

t.i., ja aizkrāsota k-tā rūtiņa, tad drīkst aizkrāsot arī 2k-to rūtiņu.

Nosacījums c) grafiski attēlojams šādi : ,

t.i., ja aizkrāsota k-tā rūtiņa, tad drīkst aizkrāsot arī tās blakus rūtiņu pa kreisi- (k-1)-mo rūtiņu.

Viegli redzēt, ka 5. teorēmas nosacījumi garantē tiesības aizkrāsot visu bezgalīgo lenti. Tiešām, nosacījums a) nozīmē, ka drīkst aizkrāsot lentes 1. rūtiņu: ; saskaņā ar nosacījumu b) drīkst aizkrāsot 2., 4., 8.,… rūtiņu: .

Vēl neaizkrāsotās rūtiņas starp aizkrāsotajām drīkst aizkrāsot saskaņā ar nosacījumu c).

57. piemērs. Pierādīt, ka apgalvojums " n pozitīvu skaitļu vidējais ģeometriskais nav lielāks kā šo skaitļu vidējais aritmētiskais" ir patiess, t.i.,

(A(n))

Bāze. Apgalvojums A(1) ir patiess, jo . Izdevīgi ir pierādīt atsevišķi arī apgalvojumu A(2): . To viegli pierādīt, izmantojot nevienādību .

Pāreja. Pieņemsim, ka jebkuram k pozitīviem skaitļiem apgalvojums A(k) ir patiess. Tad

.

Pierādīsim, ka apgalvojums A(2k) arī ir patiess. Tiešām, zinot, ka A(2) un A(k) ir patiesi apgalvojumi, iegūstam

Esam pierādījuši, ka no A(k) izriet A(2k). Atceroties ģeometrisko ilustrāciju, redzam, ka rūtiņu rindā paliek daudz neaizkrāsotu rūtiņu:

Tādēļ pierādīsim, ka no A(k) izriet A(k-1).

Pieņemsim, ka jebkuram k pozitīviem skaitļiem ir pareiza nevienādība

,

(1)

un pierādīsim, ka katriem k-1 pozitīviem skaitļiem ir pareiza nevienādība

.

(2)

Nevienādībā (1) ir par vienu skaitli- a_k- vairāk nekā pierādāmajā nevienādībā (2). Tā kā a_k var būt jebkurš pozitīvs skaitlis, tad a_k izvēlamies tā, lai nevienādības (1) labā puse būtu vienāda ar nevienādības (2) labo pusi, t.i.,

.

Izsakot no šīs vienādības a_k, iegūstam

Pārrakstām nevienādību (1), ievietojot a_k vietā iegūto izteiksmi:

.

Esam ieguvuši, ka

.

Kāpinot šīs nevienādības abas puses k-tajā pakāpē, pēc tam saīsinot ar (a₁+a₂+…+a_k-1 ) un (k-1) un velkot (k-1)-tās pakāpes sakni no nevienādības abām pusēm, iegūstam, ka , t.i., apgalvojums A(k-1) ir patiess. (Visus nevienādību pārveidojumus drīkstēja izdarīt, jo to abas puses ir pozitīvi skaitļi.)

Pārbaudīsim, vai tagad drīkst aizkrāsot visu rūtiņu rindu. Shematiski aizkrāsošanu varētu attēlot šādi: A(1)A(2)A(4)A(3)A(6)A(5)A(10)A(9)A(8)A(7)A(14)A(13)… (iespējami arī citi varianti). Kā redzams, katra rūtiņa tiks aizkrāsota. Tas nozīmē, ka apgalvojums ir patiess visām parametra vērtībām.

Padomāsim vēl, kāpēc apgalvojuma A(2) patiesumu vajadzēja pierādīt atsevišķi, bet tas nesekoja no 60. lapaspusē pierādītās iduktīvās pārejas A(k)A(2k) un no tā, ka apgalvojums A(1) ir patiess. Ievērojiet, ka induktīvās pārejas A(k)A(2k) pierādījumā 60. lapaspusē mēs izmantojām nevienādību , t.i., apgalvojumu A(2), tāpēc to vajadzēja jau iepriekš pierādīt.

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

(A(n))

Apzīmēsim 1-a_i=b_i, i=1, 2, …, n.

Bāze. Ja n=1, tad jāpierāda nevienādība

Tā acīmredzot ir pareiza.

Pāreja. Pārbaudīsim nosacījumu b). Pieņemsim, ka nevienādība A(n) pareiza, ja n=k, un pierādīsim, ka tā ir pareiza, ja n=2k. Ņemsim kaut kādus skaitļus a₁, a₂,…, a_k, a_k+1,…, a_2k, kuriem pareizas nevienādības 0<a_i1/2, i=1, 2, …, 2k. Tad pēc induktīvā pieņēmuma ir pareizas nevienādības

jeb

un	(1)
.	(2)

Jāpierāda nevienādība

(3)

Sareizinot (1) un (2), iegūstam nevienādību

(4)

Ja mēs prastu pierādīt nevienādību

(5)

tad no nevienādībām (4) un (5) izrietētu pierādāmā nevienādība (3).

Tātad jāpierāda nevienādība (5).

Apzīmēsim a₁+…+a_k=A₁, b₁+…+b_k=B₁, a_k+1+…+a_2k=A₂, b_k+1+…+b_2k=B₂. Tad nevienādību (5) var uzrakstīt šādi:

Velkot k-tās pakāpes sakni no nevienādības abām pusēm (to var darīt, jo visi skaitļi ir pozitīvi), iegūstam nevienādību

Ja B₁>B₂, tad A₁<A₂ , tātad pirmais reizinātājs šīs nevienādības kreisajā pusē ir pozitīvs. Apzīmējot , viegli pierādīt, ka arī otrais reizinātājs ir pozitīvs.

Gadījumus, kad B₁B₂, apskata līdzīgi.

Līdz ar to nevienādība (5) ir pierādīta.

Pārbaudīsim nosacījumu c). Pieņemsim, ka nevienādība A(n) ir pareiza, ja n=k, t.i., ka

(6)

Jāpierāda, ka A(n) pareiza arī, ja n=k-1, t.i., ka

(7)

Nevienādība (6) ir pareiza visiem a_i, kuriem 0<a_{11/2. Izvēlēsimies . Nav grūti saprast, ka , tāpēc šo} a_k vērtību drīkst ievietot nevienādībā (6). Iegūstam patiesu nevienādību, no kuras izriet nevienādība (7). Līdz ar to 5. teorēmas nosacījumi ir apmierināti un tātad nevienādība A(n) pierādīta.

Dažreiz nākas vispārīgos apgalvojumus pierādīt nevis visām parametra pieļaujamajām vērtībām, bet tikai kādai noteiktai parametra vērtību virknei, piemēram, divnieka pakāpēm 2, 4, 8, 16, … . Tādos gadījumos var lietot 5. teorēmas variantu: pārbauda tikai induktīvo pāreju n2n; pāreja nn-1 nav vajadzīga. Līdzīgu gadījumu aplūkojām3. § 27. piemērā.

59. piemērs. Riņķī novilkti 2^n-1 diametri, sadala šo riņķi 2ⁿ kongruentos sektoros.

Pierādīt, ka katrā sektorā var ierakstīt n locekļu virkni, kuras katrs loceklis ir 0 vai 1, tā, lai visas virknes būtu dažādas un katros divos blakus sektoros ierakstītās virknes atšķirtos tieši ar vienu locekli.

Bāze. Ja n=1, apgalvojums patiess (32. zīm.)

Pāreja. Pieņemsim, ka apgalvojums ir patiess, ja n=k. Sadalīsim riņķi 2^k kongruentos sektoros un ierakstīsim tajos k locekļu virknes, kas satāv no 0 un 1 tā, kā prasīts uzdevumā. Sanumurēsim šos sektorus pulksteņa rādītāju kustības virzienā un apzīmēsim ar s₁, s₂, …, s₂^k, bet tajos ierakstītās virknes - attiecīgi ar ₁, ₂, …, ₂^k. Katru sektoru sadalīsim divās kongruentās daļās. Izveidosies 2^k+1 mazāki sektori; apzīmēsim tos pulksteņa rādītāju kustības virzienā ar s₁⁽¹⁾, s₁⁽²⁾, s₂⁽¹⁾, s₂⁽²⁾,… s₂^k(1), s₂^k(2) .

32. zīm.

Ja m- nepāra skaitlis, tad sektorā s_m⁽¹⁾ ierakstīsim virkni , bet sektorā s_m²- virkni , skaidrs ka tās atšķiras tikai ar pēdējo locekli. Ja m- pāra skaitlis, tad sektorā s_m⁽¹⁾ ierakstīsim virkni , bet sektorā s_m⁽²⁾ - virkni ; arī tās atšķiras tikai ar pēdējo locekli. Tātad divi jaunie sektori, kas atrodas blakus un radušies no viena vecā sektora, noteikti satur virknes, kuras atšķiras tikai ar vienu locekli. Virknēs, kas ierakstīas tādos jaunajos blakus sektoros, kuri radušies no dažādiem vecajiem sektoriem, pēdējie locekļi neatšķiras; pēc induktīvā pieņēmuma šīs virknes atšķiras tieši ar vienu no iepriekšējiem locekļiem.

33. zīm.

To, ka visas jaunajos sektoros ierakstītās virknes ir dažādas, ieteicam lasītājam pierādīt patstāvīgi.

1.  zīmējumā parādīta virkņu veidošanās sektoros, ja k=1; 2.

Paragrāfa nobeigumā, izmantojot indukcijas shēmu "uz priekšu un atpakaļ", konstruēsim divu naturālu skaitļu reizināšanas algoritmu, kas lielus naturālus skaitļus reizina ātrāk nekā skolā mācītais algoritms.

Vispirms jāvienojas, kā novērtēt laiku, kurā ar kādu algoritmu iegūst divu naturālu skaitļu reizinājumu. Ja mēs zinātu no galvas jebkuru divu naturālu skaitļu reizinājumu, tad varētu izmantot algoritmu "palūkojies savā atmiņā un saki rezultātu"; laiks, kurā ar šo algoritmu iegūst divu naturālu skaitļu reizinājumu, visiem skaitļu pāriem būtu vienāds. Diemžēl visus reizinājumus nezinām un arī nevaram zināt, jo mūsu smadzenes spēj glabāt tikai galīgu informācijas daudzumu. Toties zinām un atceramies no galvas visu aritmētisko darbību rezultātus ar cipariem, un šos rezultātus izmantojam, reizinot un saskaitot lielus skaitļus. Tāpēc uzskatīsim par aritmētiskas operācijas izpildes algoritma darbības laiku ar cipariem veicamo aritmētisko darbību skaitu, kas nepieciešams rezultāta iegūšanai saskaņā ar šo algoritmu.

Saskaitot divus naturālus n ciparu skaitļus pēc skolā mācītā algoritma, ar cipariem veicamo aritmētisko darbību maksimālo skaitu apzīmēsim ar S(n). Katrā šķirā jāizdara viena saskaitīšana, pie tam var gadīties, ka jāpieskaita pārnesums visās šķirās, izņemot pēdējo.

Tāpēc S(n)=2n-1.

Reizinot divus naturālus n ciparu skaitļus pēc skolā mācītā algoritma, ar cipariem veicamo aritmētisko darbību minimālo skaitu apzīmēsim ar R(n). Reizinot "stabiņā" divus n-ciparu skaitļus, jāizdara n² reizināšanas operācijas ar cipariem, bez tam jāpieskaita pārnesumi un visas reizinot iegūtās rindiņas jāsaskaita. Tātad R(n)n².

Funkcija y=n² aug daudz straujāk nekā funkcija y=2n-1. Tātad reizināšana pēc skolā mācītā algoritma ir daudz darbietilpīgāks process nekā saskaitīšana.

Parādīsim naturālu skaitļu reizināšanas citu metodi. Aprēķinot reizinājumu pēc šīs metodes, jāizdara ievērojami mazāk aritmētisku darbību ar cipariem.

Aprakstīsim šo metodi induktīvi. Pieņemsim, ka ar cipariem veicamo aritmtisko darbību skaits, reizinot divus n-ciparu skaitļus pēc šī algoritma, nepārsniedz F(n) (cik lielas ir F(n) vērtības, pagaidām vēl nav zināms).

Bāze. Ja n ir 1, n-ciparu skaitļus reizina kā ciparus. Lai sareizinātu divus šādus skaitļus, jāizdara viena darbība ar cipariem. Tātad F(1)=1.

Pāreja k2k. Pieņemsim, ka ir zināma divu k-ciparu skaitļu reizināšanas metode. Ar cipariem veicamo darbību skaits, reizinot pēc šīs metodes, ir F(k). Noskaidrosim, kā, izmantojot šo metodi, sareizināt 2k-ciparu skaitļus

Ievērojam, ka

un

Apzīmēsim , , un ; tad A=A₁₁₀^k+A₂, B=B₁₁₀^k+B₂ un AB=(A₁₁₀^k+A₂)(B₁₁₀^k+B₂)= 10^2kA₁B₁+10^k(A₁B₂+A₂B₁)+ A₂B₂.

Aplūkojamā algoritma galvenā ideja ir šāda: izteiksmju A₁B₁, A₂B₂ un A₁B₂+A₂B₁ statistiskās vērtības var atrast, izdarot tikai trīs reizināšanas operācijas:

f₁= A₁B₁, f₂= A₂B₂ un f₃=(A₁+A₂) (B₁+B₂),

jo A₁B₂ + A₂B₁ = f₃-f₁-f₂.

Novērtēsim cik aritmētisko darbību ar cipariem jāveic, lai atrastu izteiksmju f₁, f₂, f₃ un A₁B₂+A₂B₁ vērtības.

Tā kā A₁, B₁, A₂ un B₂ ir k-ciparu skaitļi, tad katru no vērtībām f₁ un f₂ var atrast izdarot F(k) aritmētiskās darbības ar cipariem.

Noskaidrosim, cik darbības ar cipariem jāizdara, lai atrastu (A₁+A₂)(B₁+B₂).

Katru no reizinātājiem C=A₁+A₂ un D=B₁+B₂ var atrast izdarot ne vairāk kā 2k-1 darbības ar cipariem. C un D var būt (k+1)-ciparu skaitļi; pierakstīsim tos formā

kur E un F ir k-ciparu skaitļi, bet c un d- cipari. Tad

Lai aprēķinātu reizinājumu EF, jāveic F(k) aritmētiskās darbības ar cipariem; katru no reizinājumiem cF un dE aprēķina, izdarot ne vairāk kā 2k darbības ar cipariem. Tā kā cF un dE var būt (k+1) ciparu skaitļi, tad summu cF+dE aprēķina, izdarot ne vairāk kā 2(k+1)-1 darbības ar cipariem. Reizinājumu (cF+dE)10^k var aprēķināt ar k darbībām (skaitlim cF+dE labajā pusē pieraksta k nulles). Līdzīgi iegūstam, ka reizinājumu cd10^2k var aprēķināt izdarot 2k+1 aritmētiskās darbības ar cipariem.

Tātad saskaitāmo cd10^2k, (cF+dE)10^k un EF aprēķināšanai jāveic ne vairāk kā

aritmētiskās darbības ar cipariem. Tā kā neviens no izteiksmes f₃ trim saskaitāmajiem nesatur savā pierakstā kā 2k+2 ciparus, tad šos saskaitāmos var summēt izdarot ne vairāk kā 2(2k+2)-1+2(2k+3)-1=8k+8 aritmētiskās darbības ar cipariem.

Esam noskaidrojuši, ka f₃ vērtību var atrast, izdarot ne vairāk kā F(k)+21k+8 aritmētiskas darbības ar cipariem.

Ievērojam, ka neviens no skaitļiem f₁, f₂ un f₃ nesatur vairāk kā 2k+2 ciparus, tāpēc izteiksmes A₁B₂+A₂B₁=f₃-(f₁+f₂) vērtību var atrast, izdarot ne vairāk kā 8k+6 darbības ar cipariem.

No izteiksmes f₁=A₁B₁ vērtības var iegūt 10^2kA₁B₁ vērtību izdarot 2k darbības ar cipariem; no A₁B₂+A₂B₁ vērtības var iegūt (A₁B₂+A₂B₁)10^k vērtību, izdarot k darbības ar cipariem. Tātad lai aprēķinātu saskaitāmos 10^2kA₁B₁, 10^k(A₁B₂+A₂B₁) un A₂B₂, jāizdara ne vairāk kā

darbības ar cipariem. Neviens no minētajiem trim saskaitāmajiem nesatur savā decimālajā pierakstā vairāk kā 4k ciparus, tāpat arī to summa AB. Tāpēc šo summu var atrast ar divām saskaitīšanām, izdarot ne vairāk kā 16k-2 darbības ar cipariem. Esam noskaidrojuši, ka reizinājumu AB var aprēķināt, izdarot ne vairāk kā

darbības ar cipariem.

Tātad

F(2k)3F(k)+60k.

(1)

Noteiksim funkcijas F(n) augšējo robežu. Vispirms atradīsim to n vērtībām, ja n=2^m, m- naturāls skaitlis.

Ievietojot nevienādībā (1) k=2^m-1, k=2^m-2, …, k=2, k=1, iegūstam:

F(2^m)3F(2^m-1)+602^m-1;

F(2^m-1)3F(2^m-2)+602^m-2

. . . . . . . .

F(4)3F(2)+602;

F(2)3F(1)+601.

Pareizinot otro nevienādību ar 3, trešo ar 3², …, m-to ar 3^m-1, visas iegūtās nevienādības saskaitot un pēc tam savelkot līdzīgos locekļus, iegūstam

Tākā F(1)=1, tad iegūstam

F(2m)613m.

(2)

INDUKTĪVĀ PĀREJA "ATPAKAĻ"

Esam noskaidrojuši, kā ar konstruējamo algoritmu reizināt divciparu, četrciparu, astoņciparu, …, 2^k-ciparu, … skaitļus. Katram n var atrast tādu naturālu m, ka

2m-1n<2m.

(3)

Katru n-ciparu skaitli var uzrakstīt ar 2^m cipariem, pierakstot šim skaitlim priekšā vajadzīgo skaitu nuļļu. Tad divu n-ciparu skaitļu reizinājums būs vienāds ar atbilstošo 2^m ciparu reizinājumu, tāpēc

F(n)F(2m)613m.

(4)

No nevienādībām (3) iegūstam, ka m-1log₂n jeb mlog₂n+1 un tātad

Lasītājs pats var pierādīt , ka log₂3<1,6. Tātad, reizinot pēc šī algoritma divus n-ciparu skaitļus, jāizdara ne vairāk kā 183n^1,6 aritmētiskās darbības ar cipariem.

Salīdzināsim šo algoritmu ar skolā mācīto. Lai noskaidrotu, kādām n vērtībām, reizinot pēc jaunā algoritma, jāizdara mazāk darbību ar cipariem, nekā reizinot pēc skolas algoritma, atrisināsim nevienādību

183n^1,6<n²,

n^0,4>183,

n>183^5/2=453030,7949… .

Tātad, vismaz sākot ar 453031-ciparu skaitļiem, jaunais algoritms "strādā" ātrāk nekā skolā mācītais. Tiesa, reizinot pēc šī algoritma, skaitļus ar mazāku ciparu skaitu, būs jāizdara vairāk aritmētisku darbību, nekā izmantojot skolā mācīto algoritmu. Šo trūkumu vismaz principā var novērst šādi: jāsastāda tabula, kurā ir visi tie reizinājumi, kuros abi reizinātāji ir viencipara, divciparu, trīsciparu, …, 453030-ciparu skaitļi. "Mazu" skaitļu reizinājumi atrodami šajā tabulā (t.i. rezultātu iegūst pavisam bez laika patēriņa); "lielus" skaitļus var reizināt, izmantojot aplūkoto algoritmu. Tiesa, var iebilst, ka tādas tabulas sastādīšana un glabāšana ir ārkārtīgi darbietilpīgs process, bez tam skaitļi, kas sastāv no 453031 cipariem, dzīvē nekad nav jāreizina. Tā ir taisnība. Tomēr interesants ir pats fakts, ka ir iespējami algoritmi, kas "strādā" ātrāk nekā parastie, ikdienā lietotie, gan tikai reizinot ļoti lielus skaitļus; tas rada domu, ka varētu atrast citus, vēl "viltīgākus"algoritmus, kuru efektivitāte parādītos, rezinot mazākus skaitļus. Tiešām, tādi algoritmi eksistē; ir izstrādātas metodes, kas "strādā" ātrāk par parasto "skolas algoritmu", reizinot 40 un vairāk ciparu skaitļus. Ir uzbūvētas arī vairākas skaitļojamās mašīnas, kurās izmanto šo efektīvo algoritmu tādu uzdevumu risināšanai, kuros nepieciešams iegūt ļoti precīzu rezultātu (ar 100 un vairāk cipariem aiz komata).

Ir izstrādāti tādi algoritmi, pēc kuriem, reizinot n-ciparu skaitļus, jāizdara ne vairāk kā Cnlog₂n darbības ar cipariem; tā kā funkcija y=nlog₂n aug lēnāk par jebkuru funkciju y=n¹⁺, >0, tad šis algoritms "bezgalībā" (t.i. neierobežoti pieaugot ciparu skaitam n) ievērojami pārspēj mūsu izstrādāto. Tomēr konstante C ir tik liela, ka praktiski izmantot šo algoritmu, lai paātrinātu aprēķinus, nevar; ciparu skaits, ar kuru sākot tas "strādā" ātrāk par parasto algoritmu, ir ļoti liels.

Neviens nav pierādījis, ka neeksistē tāds reizināšanas algoritms, kas n-ciparu skaitļus reizina, izdarot ne vairāk kā Cn darbības ar cipariem (te C- kaut kāda, varbūt ļoti liela konstante). Šāda algoritma atrašana vai arī pierādījums, ka tāda algoritma nav, būtu ļoti nozīmīgs matemātisks atklājums.

Uzdevumi paškontrolei V

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

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

116. Funkcija f(x) definēta visām reālām x vērtībām, un visiem reāliem x un y ir pareiza nevienādība

Pierādīt, ka visiem naturāliem n un visiem reāliem skaitļiem x₁, x₂, …, x_n ir pareiza nevienādība

117. (Tēma skolēnu zinātniskajai biedrībai.) Apzīmēsim ar x kortežu (x₁; x₂; …; x_n), bet ar y- kortežu (1-x₁; 1-x₂; …; 1-x_n). Ja a=(a₁; a₂; …; a_n), bet s- pozitīvs skaitlis, apzīmēsim

Kādiem p, q un kādiem skaitļiem x₁, x₂, …, x_n no nevienādības p<q izriet nevienādība

(Pierādīt, ka 58. piemērā aplūkotā nevienādībair šīs nevienādības speciālgadījums.)

118. Pierādīt, ka no cipariem 1 un 2 var izveidot tādus 2ⁿ⁺¹ dažādus 2ⁿ ciparu skaitļus, ka jebkuri divi no šiem skaitļiem atšķiras vismaz 2^n-1 vietās.

119. Turnīrā piedalās 2ⁿ tenisisti. Pirmajā kārtā tie sadalās pa pāriem un katrs pāris spēlē savā starpā; uzvarētāji otrajā kārtā sadalās pa pāriem un katrs pāris spēlē savā starpā, utt. Pēdējā kārtā spēlē divi priekšpēdējās spēles uzvarētāji, un šīs spēles uzvarētājs kļūst par čempionu. Pirms turnīra sākuma tenisa federācija ir piešķīrusi spēlētājiem numurus 1, 2, 3,…, 2ⁿ. Ir zināms: ja kādā spēlē tiekas divi tenisisti, kuru numuru starpība pārsniedz 2, tad uzvar tenisists ar mazāko numuru. Pierādīt, ka par čempionu var kļūt tenisists ar numuru 2n-1.

120. Pierādīt, ka kvadrātā, kas sastāv no nn rūtiņām, daļu rūtiņu var nokrāsot baltas, bet daļu - melnas tā, ka nevienā kk rūtiņu kvadrātā (kn) pretējām malām pieguļošo rūtiņu rindas nav nokrāsotas vienādi.

ĪSS LITERATŪRAS APSKATS

Nevienādības, kuras var pierādīt ar šajā paragrāfā aplūkoto metodi, ir atrodamas darbā [37]. Dažus aritmētisko operāciju izpildes algoritmus, kas "strādā" ātrāk nekā skolā aplūkotie, var atrast grāmatā [29]; visu šo algoritmu aprakstos tiek izmantotas dažādas indukcijas shēmas.