Sākums

LV.SOL.2007.11.5   lv

Apskatām tabulu ar izmēriem \(2\times n\) rūtiņas (skat. 7. zīm.).

  1. zīm.

Visās rūtiņās kopā kaut kā izvietotas \(2^n\) monētas. Ar vienu gājienu var izvēlēties rūtiņu, kurā ir vismaz \(2\) monētas, vienu no šīm monētām aizvākt no tabulas, bet otru pārbīdīt vai nu vienu vietu uz augšu (ja to iespējams izdarīt), vai vienu vietu pa labi. Pierādiet: var panākt, lai labējās kolonnas augšējā rūtiņā atrastos kāda monēta.

Hide solution

Atrisinājums

Lemma. Ja tabulā ir \(1\) rindiņa ar \(n\) rūtiņām un tajā izvietotas \(\ge 2^{n-1}\) monētas, tad var panākt, lai pēdējā rūtiņā atrastos kāda monēta.
Lemmu pierāda ar matemātisko indukciju. Bāze \(n=1\) ir triviāla. Apskatām pāreju. Ja sākumā pēdējā rūtiņā jau ir kāda monēta, viss kārtībā. Pretējā gadījumā apskatām \(1\cdot(n-1)\) tabulu, kurā ir divi komplekti monētu, katrā pa \(\ge 2^{n-2}\) monētām; saskaņā ar induktīvo hipotēzi katrs no šiem komplektiem var „nogādāt” \((n-1)\)-ā rūtiņā vismaz vienu monētu. Tās abas izmantojot, iegūst vajadzīgo tabulai \(1\cdot n\). Lemma pierādīta.
Piešķiram rūtiņām koordinātas, kā parādīts 20. zīmējumā.

  1. zīm.

Risinām ar indukciju sākotnējo uzdevumu. Pie \(n=1\) apgalvojums ir acīmredzams (ir tikai \(3\) sākuma konfigurācijas). Pieņemsim, ka tas patiess tabulām \(2\cdot(n-1)\). Apskatām tabulu \(2\cdot n\). Šķirojam iespējas:
a) \(n\)-jā kolonnā ir \(\ge 2\) monētas; viss acīmredzams
b) \(n\)-jā kolonnā ir \(1\) monēta. Ja tā ir rūtiņā \((1,n)\), viss jau ir kārtībā. Ja tā ir rūtiņā \((2,n)\), tad tabulā \(2\cdot(n-1)\) ir \(2^n-1\) monētas. Ir divi apakšgadījumi:

\(b_1\)) \(1.\) rindiņā ir \(\ge 2^{n-1}\) monētas; lietojam lemmu tabulas \(2\cdot n\) augšējai rindiņai.

\(b_2\)) \(1.\) rindiņā ir \(<2^{n-1}\) monētas; tad \(2.\) rindiņā ir \(\ge 2^{n-1}\) monētas. Lietojot lemmu, nogādājam vienu no tām rūtiņā \((2,n)\) un ar nākošo gājienu sasniedzam vajadzīgo.

c) \(n\)-jā kolonnā monētu nav. Tad tabulā \(2\cdot(n-1)\) ir divi komplekti, katrā pa \(2^{n-1}\) monētām. Saskaņā ar induktīvo hipotēzi nogādājam rūtiņā \((1,n-1)\) \(2\) monētas, un ar nākošo gājienu sasniedzam mērķi.