Квадрат розміром 99×99 клітинок, кожна пофарбована в чорний або білий колір. Дозволяється одночасно змінити колір усіх клітинок одного рядка або стовпця на той, що був найбільш поширеним у цьому рядку/стовпці до зміни. Чи завжди можна зробити всі клітинки однакового кольору?
Розв’язання
Позначимо кількість чорних клітинок у рядку i як ci, а білих — bi. За умовою ci+bi=99.
Якщо ми обираємо для фарбування рядок, де чорних клітинок більше (ci>bi), то після перефарбування всі клітинки стануть чорними. Кількість чорних клітинок збільшиться на bi.
Якщо ми обираємо рядок, де білих клітинок більше (bi>ci), то після фарбування всі стануть білими. Кількість чорних клітинок зменшиться на ci.
Отже, операція дозволяє збільшувати або зменшувати кількість чорних клітинок у вибраному рядку/стовпці. Однак, щоб зробити всі клітинки однакового кольору, нам потрібно, щоб в кожному рядку та стовпці переважав один колір, і ми могли б «привести» їх до єдиного стану.
Розглянемо випадок, коли в кожному рядку та стовпці кількість клітинок одного кольору більша за іншу (тобто ci=49 або bi=49, оскільки 99 — непарне число). Якщо існує хоча б один рядок, де чорних менше, ніж білих, ми можемо зробити цей рядок повністю білим. Але якщо в кожному рядку та стовпці кількість клітинок одного кольору однакова (наприклад, 49 чорних і 50 білих), то операція завжди дає переважний колір.
Проте, якщо початкова конфігурація така, що в кожному рядку та стовпці кількість клітинок одного кольору більша за іншу (наприклад, чорних більше), ми можемо зробити всі клітинки чорними. Якщо ж є рядок, де білих більше, а в стовпці — чорних більше, то ситуація складніша.
Насправді, якщо існує хоча б один рядок або стовпець, де кількість клітинок одного кольору більша за іншу, ми можемо використовувати цю перевагу для «перетягування» всього квадрата до цього кольору. Якщо ж у кожному рядку та стовпці кількість чорних і білих клітинок однакова (що неможливо для непарного 99), то ситуація інша.
Оскільки 99 — непарне число, в будь-якому рядку або стовпці кількість клітинок одного кольору завжди більша за іншу. Отже, ми завжди можемо вибрати колір, який переважає в кожному рядку/стовпці, і «привести» весь квадрат до цього кольору.
Відповідь:
Так, завжди можна зробити всі клітинки квадрата однакового кольору.
Квадрат розміром 99×99 клітинок, кожна пофарбована в чорний або білий колір. Дозволяється одночасно змінити колір усіх клітинок одного рядка або стовпця на той, що був найбільш поширеним у цьому рядку/стовпці до зміни. Чи завжди можна зробити всі клітинки однакового кольору?
Що треба знати
Ключова властивість — операція не змінює різницю між кількістю чорних та білих клітинок в будь-якому рядку чи стовпці, якщо рахувати їх як +1 і −1.
💡 Підказка — спробуй спершу сам
Розгляньте загальну кількість чорних клітинок у всьому квадраті. Як змінюється ця кількість після однієї операції? Чи можна досягти стану, коли всі клітинки одного кольору, починаючи з будь-якої початкової конфігурації?
Розв’язання крок за кроком
Позначимо кількість чорних клітинок у рядку i як ci, а білих — bi. За умовою ci+bi=99.
Якщо ми обираємо для фарбування рядок, де чорних клітинок більше (ci>bi), то після перефарбування всі клітинки стануть чорними. Кількість чорних клітинок збільшиться на bi.
Якщо ми обираємо рядок, де білих клітинок більше (bi>ci), то після фарбування всі стануть білими. Кількість чорних клітинок зменшиться на ci.
Отже, операція дозволяє збільшувати або зменшувати кількість чорних клітинок у вибраному рядку/стовпці. Однак, щоб зробити всі клітинки однакового кольору, нам потрібно, щоб в кожному рядку та стовпці переважав один колір, і ми могли б «привести» їх до єдиного стану.
Розглянемо випадок, коли в кожному рядку та стовпці кількість клітинок одного кольору більша за іншу (тобто ci=49 або bi=49, оскільки 99 — непарне число). Якщо існує хоча б один рядок, де чорних менше, ніж білих, ми можемо зробити цей рядок повністю білим. Але якщо в кожному рядку та стовпці кількість клітинок одного кольору однакова (наприклад, 49 чорних і 50 білих), то операція завжди дає переважний колір.
Проте, якщо початкова конфігурація така, що в кожному рядку та стовпці кількість клітинок одного кольору більша за іншу (наприклад, чорних більше), ми можемо зробити всі клітинки чорними. Якщо ж є рядок, де білих більше, а в стовпці — чорних більше, то ситуація складніша.
Насправді, якщо існує хоча б один рядок або стовпець, де кількість клітинок одного кольору більша за іншу, ми можемо використовувати цю перевагу для «перетягування» всього квадрата до цього кольору. Якщо ж у кожному рядку та стовпці кількість чорних і білих клітинок однакова (що неможливо для непарного 99), то ситуація інша.
Оскільки 99 — непарне число, в будь-якому рядку або стовпці кількість клітинок одного кольору завжди більша за іншу. Отже, ми завжди можемо вибрати колір, який переважає в кожному рядку/стовпці, і «привести» весь квадрат до цього кольору.
Відповідь:
Так, завжди можна зробити всі клітинки квадрата однакового кольору.