LV.VOL.2021.9.2 lv
Dots naturāls skaitlis \(n\). Pierādīt, ka \(4n \times 4 n\) rūtiņu tabulā var aizkrāsot \(4n^{2}\) rūtiņas tā, ka katrā rindā un katrā kolonnā ir aizkrāsotas tieši \(n\) rūtiņas un nekādām divām aizkrāsotām rūtiņām nav kopīgu punktu (tas ir, iekrāsotās rūtiņas neatrodas blakus un nesaskaras pat ar stūriem).
Atrisinājums
Vispirms aplūkosim gadījumu, ja \(n=1\). Tad \(4 \times 4\) rūtiņu tabulā rūtiņas var aizkrāsot, kā parādīts 1.att. šis tabulas krāsojums atbilst visām prasībām.
Ievērosim, ka, sadalot aizpildīto tabulu \(2 \times 2\) rūtiņas lielos kvadrātos, iegūsim vienādi aizpildītus \(2 \times 2\) rūtiņu kvadrātus, kas pagriezti attiecībā viens pret otru. Izmantojot šo ideju, veidosim tabulas aizpildījumu patvaļīgai \(n\) vērtībai.
Vispirms izveidosim \(2n \times 2n\) rūtiņu tabulu, kurā īpaši izdalīsim \((2n-1) \times(2n-1)\) kvadrātu, kam papildus ir viena tukša rinda un viena tukša kolonna. Šajā \((2n-1) \times(2n-1)\) kvadrātā aizkrāsosim \(n\) rūtiņas katrā otrajā rindā un kolonnā, katrā virzienā atstājot pa tukšai rūtiņai starp iekrāsotajām (skat. 2.att., kur parādīts gadījums \(n=3\)).
Pagriežot šo kvadrātu un sakombinējot tā, kā \(2 \times 2\) kvadrāti tika sakombinēti \(4 \times 4\) tabulā, iegūstam nepieciešamo tabulas aizpildijumu (skat. 3.att.).