| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 2 | maomao90 | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Дан квадрат NxN. N > 2.
Закрасим чёрным цветом N клеток так, что никакие две из них не смежны по стороне. Закрасим белым цветом клетки, смежные по стороне с чёрными. Доказать что количество белых клеток ≥ N + floor(N / 2) при любой такой покраске.
Например для квадрата 3x3. Красим диагональ в чёрный цвет. Количество белых 4.
Автокомментарий: текст был обновлен пользователем Guliash (предыдущая версия, новая версия, сравнить).
Неверно для 2х2 :)
А вообще: нужно доказать, что есть такая покраска черными? Или что это верно при любой покраске? Второе интереснее, но тогда пример с диагональю не в тему.
Контрпример побольше есть. На доске 24х24 строим "ромбик" из черных со стороной 5 без одного угла. Белых будет, очевидно (5+1)^2-1=35, но при этом 24+24/2=36.
UPD. Если все-таки первое, то диагональ всегда дает 2(N-1), что явно подходит. А если второе, то мой контрпример с ромбиком подходит для любых N>=24. Наращивая ромбик по одной черной клетке мы увеличиваем число белых один раз на 2, а потом несколько раз на 1. Число N+[N/2] тоже увеличивается на 1 и на 2, но по очереди, что идет быстрее. Для N<24 можно тоже что-то попробовать придумать, но немного влом :)
Ага, спасибо за 2x2. Подправил условие. Не совсем понял про ромбик. То есть по квадрату в вершинах. И по 5 квадратов между вершинами. И того их 24. Прижмём его ещё к левому верхнему. Если так, то там гораздо больше 36 (внутренние белые клетки и внешние).
Нужно доказать, что это верно при любой покраске.
Спасибо=)
Автокомментарий: текст был обновлен пользователем Guliash (предыдущая версия, новая версия, сравнить).
Возьмем достаточно большое N и нарисуем в уголке квадрат размера
и сделаем ему шахматную закраску так, что будет N черных. Белых после отметки будет 
. Эта величина порядка N, а не 
.
Пример:
N = 18
B = 18
W = 24 < 18 + 9
Квадраты не дорисовывал
Ребята, а если всё так хорошо, то может докажем, что для http://acm.timus.ru/problem.aspx?space=1&num=1480 n2 + floor(n / 2) + 1 есть ответ? Просто вопрос возник как раз из этой задачи.
Могу врать, но у меня, кажется, n^2+3 получается... Идея в предыдущей правке.
Там просто в комментариях говорят, что та формула AC.
Пардон, это я свой шаблон неправильно посчитал, такая же формула и выходит, да :) А вот доказательство... Возможно, конструктивное и подходит. То есть, берем максимальное число и пихаем к нему минимальные. Следующий максимум ставим рядом и к нему оставшиеся минимумы. И так далее. Но не могу честно доказать, почему при отступлении от этой стратегии будет получаться больше.
Мне почему-то кажется, что такую задачу для n = 10 я встречал в книге "Всероссийские олимпиады школьников по математике 1993 — 2009", сейчас поищу (но нужно сперва саму книгу найти).
UPD. Да, это восьмая задача параллели 9 класса заключительного этапа 1996 - 1997 учебного года (в книге имеет номер 528).
UPD2. Номер неправильный, так как я посмотрел книгу за 1993-2006 годы.
По традиции олимпиад по математике n должно было быть равно 1997.
К слову, на проблемс.ру есть решение этой задачи: клац.