Katrs naturāls skaitlis no \(1\) līdz \(10\) ieskaitot uzrakstīts uz vienas baltas, vienas melnas, vienas sarkanas un vienas zaļas kartītes; uz katras kartītes uzrakstīts tikai viens skaitlis. Šīs kartītes kaut kā izvietotas \(4\) rindās un \(10\) kolonnās. Ar vienu gājienu var mainīt vietām divas kartītes, uz kurām uzrakstīti vienādi skaitļi. Pierādiet: var panākt, ka katrā kolonnā pārstāvētas visas \(4\) krāsas.
Pieņemsim, ka pirmajās \(k-1\) kolonnās ir visas krāsas, bet \(k\)-jā kolonnā - nē \((k=1;\ 2;\ \ldots;\ 9 \); skaidrs, ka nevar būt \(k=10\)). Parādīsim, kā "izlabot" \(k\)-to kolonnu, "nesabojājot" pirmās \(k-1\) kolonnas.
Pieņemsim, ka \(k\)-tajā kolonnā krāsa \(x\) sastopama vismaz divas reizes, bet krāsa \(y\) tur nav sastopama. Katru no kolonnām attēlosim ar punktu. Katram \(i=1;\ 2;\ \ldots;\ 10\) novilksim bultiņu no tās kolonnas, kurā skaitlis \(i\) ir krāsā \(x\), uz to kolonnu, kurā skaitlis \(i\) ir krāsā \(y\). Katrā no pirmajām \(k-1\) kolonnām viena bultiņa ieiet un viena bultiņa iziet. Savukārt \(k\)-jā kolonnā neieiet neviena bultiņa, bet no tās iziet vismaz \(2\) bultiņas.
Ja mēs sāksim iet pa bultiņām no \(k\)-tās kolonnas, mēs varam sasniegt kolonnu ar numuru \(>\boldsymbol{k}\). Pretējā gadījumā mēs nonākam pirmo \(k-1\) kolonnu grupā, no kuras ārā iziet vairs nevaram, un tas nozīmē, ka pirmo \(k-1\) kolonnu grupai ir vairāk ieejošo bultiņu nekā izejošo (pa vienai agrāk pieminētajai un vēl tā bultiņa, pa kuru mēs nonākam šajā grupā no kolonnas \(k\)) - pretruna. Tātad eksistē bultiņu virkne, kas sākas ar \(k\)-to kolonnu un beidas ar kolonnu " \(>k\) ". Izdarot maiņas, kas atbilsts šīm bultiņām (maiņas sākam no kolonnas ar numuru \(>k\)), mēs "izlabojam" kolonnu ar numuru \(k\) attiecībā uz krāsu \(y\). Izlabojot to, ja vajadzīgs, attiecībā uz citām krāsām, panākam, ka arī \(k\)-tā kolonna ir laba.