Sākums

LV.VOL.2008.11.5   lv

Kvadrāts sastāv no \(10 \times 10\) vienādām kvadrātiskām rūtiņām. Katra rūtiņa nokrāsota vienā no \(10\) krāsām; katrā krāsā nokrāsotas tieši \(10\) rūtiņas. Pierādīt: var atrast vai nu tādu rindu, vai tādu kolonnu, kurā sastopamas vismaz \(4\) krāsas.

Hide solution

Atrisinājums

Pieņemsim, ka \(i\)-tā krāsa sastopama \(x_{i}\) rindiņās un \(y_{i}\) kolonnās. Tad \(x_{i} \cdot y_{i} \geq 10\). Tāpēc \(x_{i}+y_{i} \geq 2 \sqrt{x_{i} y_{i}} \geq 2 \sqrt{10} \geq 2 \cdot 3, \ldots>6\), tātad \(x_{i}+y_{i} \geq 7\). Tāpēc \(\left(x_{1}+y_{1}\right)+\left(x_{2}+y_{2}\right)+\ldots+\left(x_{10}+y_{10}\right) \geq 70\). Ja katra rinda un katra kolonna saturētu ne vairāk par \(3\) krāsām, tad būtu ne vairāk kā \(3 \cdot(10+10)=60\) "gadījumu", kad kāda krāsa sastopama kādā rindā vai kolonnā - pretruna.