Atrisinājums

Dosim risinājumu (B) gadījumam. Skaidrs, ka, ja uzdevuma prasības var izpildīt ar \(99\) ierīces lietojumiem, tad ar \(100\) lietojumiem to arī var izdarīt.

Ar matemātisko indukciju pierādīsim, ka, ja ir \(n\) kredītkartes, ( \(n \geq 5\) ), tad ar \(n-1\) ierīces lietojumiem pietiek, lai atrastu gan kredītkarti ar vislielāko naudas summu, gan kredītkarti ar otro lielāko naudas summu.

Induktīvā bāze. Pierādīsim, ka starp \(5\) kredītkartēm ar \(4\) ierīces lietojumiem var atrast kredītkarti ar lielāko naudas summu.

Apzīmēsim kredītkartes ar \(1, 2, 3, 4, 5\). Pieņemsim, ka kredītkartē \(1\) ir vislielākā naudas summa, kredītkartē \(2\)- otra lielākā, utt., kredītkartē \(5\)- starp šīm piecām vismazākā naudas summa.

Iespējami \(5\) veidi, kā lietot ierīci:

a. Ievieto \(1, 2, 3, 4\). Ierīce paziņo- \(2\). b. Ievieto \(1, 2, 3, 5\). Ierīce paziņo- \(2\). c. Ievieto \(1, 2, 4, 5\). Ierīce paziņo- \(2\). d. Ievieto \(1, 3, 4, 5\). Ierīce paziņo- \(3\). e. Ievieto \(2, 3, 4, 5\). Ierīce paziņo- \(3\).

Tātad ierīce vienmēr paziņos \(2\) vai \(3\). Tāpēc iespējams šāds algoritms kredītkaršu \(1\) un \(2\) identificēšanai.

1. Ievietosim ierīcē jebkuras \(4\) kredītkartes. Pieņemsim, ka ierīce paziņo \(A\). Tad \(A=2\) vai \(A=3\).
2. Izmēģināsim visas četru kredītkaršu kombinācijas, kas satur \(A\). (Tādu pavisam ir \(4\), un viena no tām jau ir izmēģināta.)

a. Ja trijos no četriem gadījumiem ierīce pazino \(A\) , tad \(A=2\). \(1\) ir kredītkarte, kas nebija ievietota ierīcē vienīgajā gadījumā, kad ierīce neziņoja \(2\) (tad bija ievietotas kredītkartes \(2, 3, 4, 5\).) b. Ja divos no četriem gadījumiem ierīce paziņo \(A\), tad \(A=3\). \(2\) ir kredītkarte, ko ierīce paziņo pārējos divos gadījumos. \(1\) ir kredītkarte, kas nebija ievietota ierīcē tajā reizē, kad ierīcē bija gan \(2\), gan arī \(A=3\), un ierīce paziņoja \(A(=3)\).

Induktīvais pieņēmums. Pieņemsim, ka starp \(5 \leq k \leq n\) kredītkartēm, lietojot ierīci \(k-1\) reizi, var noteikt kartes ar vislielāko un otro lielāko naudas summu.

Induktīīā pāreja. Ja mums ir \(n+1\) kredītkarte, tad:

1. Izvēlēsimies \(n\) kredītkartes (visas, atskaitot karti \(X\)). Saskaņā ar induktīvo pieņēmumu, starp tām ar \(n-1\) ierīces lietojumu var atrast kredītkartes \(A\) un \(B\), kas satur lielāko un otro lielāko naudas summu starp šīm \(n\) kredītkartēm.
2. \(n\)-tajā ierīces lietošanas reizē ievietosim ierīcē kredītkartes \(X, A, B\) un jebkuru citu kredītkarti. Iespējami šādi varianti:

a. Ierīce pazino, ka otrā lielākā naudas summa ir kartē \(B\). Tad kredītkartē \(X\) ir mazāk naudas nekā kredītkartēs \(A\) un \(B\), tātad \(A\) un \(B\) joprojām paliek kartes ar vislielākajām naudas summām.

b. Ierīce paziņo, ka otrā lielākā naudas summa ir kartē \(A\). Tad kredītkartē \(X\) ir visvairāk naudas, kartē \(A\) ir otra lielākā naudas summa.

c. Ierīce paziņo, ka otrā lielākā naudas summa ir kartē \(X\). Tad kartē \(A\) ir visvairāk naudas, bet kartē \(X\)- otra lielākā naudas summa.