Loading [MathJax]/jax/output/SVG/jax.js

Республиканская олимпиада по математике, 2023 год, 9 класс


\q3 Өлшемі 2n×2n ұяшықты тақта берілген. Самат тақтаның кейбір ұяшықтарын көк немесе қызыл түске бояйды. Ол жалпы дәл k ұяшықты бояу керек. Содан кейін Фархат қалған барлық боялмаған ұяшықтарды көк немесе қызыл түске келесі шарттар орындалатындай бояйды:
   әр қатарда және әр бағанда көк және қызыл ұяшықтар саны тең;
   ешқандай қатарда және ешқандай бағанда қатар келген бір түсті үш ұяшық жоқ;
   кез келген екі қатар әртүрлі және кез келген екі баған әртүрлі. (Егер r1 және r2 қатарларының бір бағанда жататын әртүрлі түсті екі ұяшығы табылса, ондай r1 және r2 қатарларын әртүрлі деп есептейміз. Дәл сол сияқты баған үшін әртүрлі бағандарды анықтаймыз.)
   Фархат Саматтың қалай бояғанына қарамастан тақтаны ең көп дегенде бір әдіспен ғана бояй алатындай n-ге тәуелді ең кіші мүмкін k санын табыңыз. (Ұяшықты бірінші рет бояғаннан кейін үстінен тағы бояуға болмайды.) ( Сам Ф. )
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 4   3
2 года назад #

Ответ: 4n23. Из первого условия выходит однозначность.

Теперь пример для 4n24. Главная идея заключается в том, что если перекрасить шахматный квадратик 2×2 (или любые 4 точки которые образуют шахматный прямоугольник), то это сохранит условие 1 и почти сохраняет условия 2 и 3. Осталось придумать пример. Когда n=1 или n=2:

Когда n>2 разбиваем на четный и нечетный случай (слева для четных n, справа для нечетных):

И не закрашенные клетки можно раскрасить двумя шахматными способами.