ГДЗ Геометрія 9 клас Мерзляк А. Г. — сторінка 62

Завдання 5.51

Логічна задача про фарбування клітинок

Квадрат розміром $99 \times 99$ клітинок, кожна пофарбована в чорний або білий колір. Дозволяється одночасно змінити колір усіх клітинок одного рядка або стовпця на той, що був найбільш поширеним у цьому рядку/стовпці до зміни. Чи завжди можна зробити всі клітинки однакового кольору?

Розв’язання

Позначимо кількість чорних клітинок у рядку $i$ як $c_{i}$ , а білих — $b_{i}$ . За умовою $c_{i} + b_{i} = 99$ .
Якщо ми обираємо для фарбування рядок, де чорних клітинок більше ( $c_{i} > b_{i}$ ), то після перефарбування всі клітинки стануть чорними. Кількість чорних клітинок збільшиться на $b_{i}$ .
Якщо ми обираємо рядок, де білих клітинок більше ( $b_{i} > c_{i}$ ), то після фарбування всі стануть білими. Кількість чорних клітинок зменшиться на $c_{i}$ .
Отже, операція дозволяє збільшувати або зменшувати кількість чорних клітинок у вибраному рядку/стовпці. Однак, щоб зробити всі клітинки однакового кольору, нам потрібно, щоб в кожному рядку та стовпці переважав один колір, і ми могли б «привести» їх до єдиного стану.
Розглянемо випадок, коли в кожному рядку та стовпці кількість клітинок одного кольору більша за іншу (тобто $c_{i} \neq = 49$ або $b_{i} \neq = 49$ , оскільки $99$ — непарне число). Якщо існує хоча б один рядок, де чорних менше, ніж білих, ми можемо зробити цей рядок повністю білим. Але якщо в кожному рядку та стовпці кількість клітинок одного кольору однакова (наприклад, $49$ чорних і $50$ білих), то операція завжди дає переважний колір.
Проте, якщо початкова конфігурація така, що в кожному рядку та стовпці кількість клітинок одного кольору більша за іншу (наприклад, чорних більше), ми можемо зробити всі клітинки чорними. Якщо ж є рядок, де білих більше, а в стовпці — чорних більше, то ситуація складніша.
Насправді, якщо існує хоча б один рядок або стовпець, де кількість клітинок одного кольору більша за іншу, ми можемо використовувати цю перевагу для «перетягування» всього квадрата до цього кольору. Якщо ж у кожному рядку та стовпці кількість чорних і білих клітинок однакова (що неможливо для непарного $99$ ), то ситуація інша.
Оскільки $99$ — непарне число, в будь-якому рядку або стовпці кількість клітинок одного кольору завжди більша за іншу. Отже, ми завжди можемо вибрати колір, який переважає в кожному рядку/стовпці, і «привести» весь квадрат до цього кольору.

Відповідь:

Так, завжди можна зробити всі клітинки квадрата однакового кольору.