Sākums

LV.SOL.2014.9.5   lv

Vairākās kaudzēs kopā ir \(n\) konfektes. Ar vienu gājienu atļauts izvēlēties jebkuras \(2\) kaudzes un no lielākās pārlikt mazākajā tik konfekšu, cik mazākajā jau ir (vai apvienot abas kaudzes vienā kaudzē, ja tajās ir vienāds konfekšu daudzums).
Vai taisnība, ka visas konfektes var apvienot vienā kaudzē neatkarīgi no to sākotnējā sadalījuma, ja
a) \(n=64\),
b) \(n=100\)?

Hide solution

Atrisinājums

a) Tas ir iespējams. Sākumā kaudzīšu ar nepāra skaitu konfekšu ir pāra skaits. Apvienojam tās pa pāriem un no lielākās kaudzītes pārliekam mazākajā kaudzītē atbilstošo konfekšu skaitu. Tagad visās kaudzītēs ir pāra skaits konfekšu. Uzskatīsim, ka mums tagad ir \(32\) dubultkonfektes, kuras turpmāk neatdalīsim. Tagad mums ir pāra skaits kaudzīšu, kurās ir nepāra skaits dubultkonfekšu. Atkārtojot iepriekšējo operāciju, iegūstam kaudzītes, kurās kopā ir \(16\) kvadrokonfektes. Atkārtojot iepriekšējo operāciju, iegūstam kaudzītes, kurās kopā ir \(8\) oktāvkonfektes (\(8\) apvienotas konfektes). Līdzīgi iegūstam \(4\) \(16\)-konfektes, \(2\) \(32\)-konfektes un vienu kaudzi ar \(64\) konfektēm.

b) Nē, ne vienmēr. Pieņemsim, ka sākumā mums ir \(5\) kaudzītes pa \(20\) konfektēm katrā. Lai visas konfektes pēdējā gājienā apvienotu vienā kaudzē, iepriekšējā gājienā jāiegūst divas kaudzes ar \(50\) konfektēm katrā. Taču visās kaudzēs konfekšu skaits visu laiku dalīsies ar \(20\), bet \(50\) ar \(20\) nedalās.