каждая клетка квадрата 13*13 окрашена в красный или синий цвет. Клетка называется доминирующей, если в её строке, так и в её столбце больше половины клеток её цвета. Могло ли доминирующих оказаться меньше 25?

задан 23 Апр '17 14:56

Клетка называется доминирующей, если в её строке, так и в её столбце больше половины клеток её цвета - из условия не следует, что сама клетка не учитывается в большей половине при подсчёте ...

(28 Апр '17 7:36) all_exist

@all_exist: эта клетка обязательно учитывается в обоих случаях. Нужно, чтобы общее количество клеток в строке/столбце было нечётно.

(28 Апр '17 9:46) falcao

@falcao, как всегда не так прочитал условие... мне показалось "строка или столбец" ...

(28 Апр '17 15:45) all_exist

@all_exist: там ещё написано не очень чётко. Поскольку присутствует слово "так", перед этим должно быть "как". То есть правильно было бы сказать "как в её строке, так и в её столбце".

(28 Апр '17 16:10) falcao
10|600 символов нужно символов осталось
2

Да, могло. Раскрасим в шахматном порядке квадрат 12x12. Допишем к нему слева красный столбец, а к тому, что получится, добавим снизу синюю строку. Ясно, что красный цвет преобладает в первых 12 строках и первом столбце, а синий -- в последней строке и последних 12 столбцах. Никакая клетка квадрата 12x12, с которого мы начинали, доминирующей не будет. То же насчёт левой нижней клетки. Остаётся только по 12 доминирующих клеток из последней строки и из первого столбца.

Вместе с тем, значение 24 будет уже наименьшим, что легко обосновывается.

Добавление. Тут попросили обосновать, что число 24 наименьшее. Прилагаю соответствующее рассуждение.

В каждой строке нечётное число клеток. Какой-то цвет в пределах этой строки преобладает. Напишем справа от таблицы К или С для каждой строки, указывая символически её преобладающий цвет. Аналогично поступим со столбцами.

Рассмотрим случай, когда и в строках, и в столбцах хотя бы один раз встречается и К, и С. Пусть К для строк встречается x раз, а для столбцов С встречается y раз, где 1<=x<13, 1<=y<13. Доминирующие клетки возникнут на пересечении строк с меткой К и столбцов с меткой К, а также на пересечении строки и столбцов с меткой С. Всего получится s=x(13-y)+y(13-x) доминирующих клеток. Нетрудно проверить, что минимум достигается при x=y=1. Действительно, 2s=13^2-(13-2x)(13-2y), а максимум модуля как для 13-2x, так и для 13-2y равен 11. Это даёт значение s=24, описанное в решении.

Теперь рассмотрим случай, когда во всех строках преобладает один и тот же цвет -- можно считать, что это цвет К. Тогда красных клеток в таблице больше чем синих как минимум на 13. Если столбец с меткой К всего один, то в нём не более 13 красных клеток, а в остальных столбцах преобладает синий цвет, и тогда разницы в 13 и более не получается. Значит, столбцов с меткой К не менее двух. Пусть их имеется t, и красных клеток в них m, синих 13t-m. В остальных 13-t столбцах синих клеток больше как минимум на это значение. Тогда в первых t столбцах превышение количества красных клеток над синими должно составлять как минимум 26-t. Итого m-(13t-m)=2m-13t>=26-t, то есть m>=13+6t>=25. Любая из m красных клеток доминирующая, и здесь их получается не меньше 25.

Оказалось, что "легко" не так уже и легко -- добавленный текст существенно длиннее решения.

ссылка

отвечен 23 Апр '17 16:49

изменен 28 Апр '17 16:46

не очень понял как внутри квадрата заполнять

(24 Апр '17 22:45) ролонок555

@ролонок555: я же всё описал в явном виде. Заполняем сначала квадрат без первой строки и последнего столбца. Раскраска шахматная, то есть цвета соседних по стороне клеток чередуются. Потом слева добавляем красный столбец, а снизу -- синюю строку.

(24 Апр '17 22:50) falcao

Я не очень хорошо понял условие и не понимаю почему квадрат 12x12 там нет доминирующей клетки.

(25 Апр '17 18:09) ролонок555

Ой уже понял)

(25 Апр '17 18:09) ролонок555

@ролонок555: как мало нужно для понимания! :) Я имею в виду время его достижения.

На всякий случай: если мы берём любую клетку квадрата 12x12, то в его пределах наблюдается баланс цветов, и всё решают добавленные клетки. Но у них цвета разные, поэтому в строке будет больше красного, а в столбце больше синего. Ни красная, ни синяя клетка квадрата 12x12 по этой причине не будет доминировать.

(25 Апр '17 18:46) falcao

@falcao, что-то я затупил - как легко обосновывается минимальность 24?

(28 Апр '17 7:04) bot

@bot: я это рассуждение не приводил. Если интересно, могу написать чуть позже.

(28 Апр '17 9:46) falcao

@falcao: интересно, да

(2 Май '17 7:31) bot

@falcao: Если центральную клетку квадрата покрасить в чёрный цвет, а все остальные в белый, то центральная клетка не доминирует, хотя и лежит на сказанном пересечении.

(3 Май '17 5:11) bot

@bot: а разве это противоречит чему-то из сказанного?

(3 Май '17 9:17) falcao
1

@falcao: "Доминирующие клетки возникнут на пересечении строк с меткой К и столбцов с меткой К, а также на пересечении строки и столбцов с меткой С"

(3 Май '17 9:23) bot

@bot: я понял, что Вы имеете в виду. Мы оцениваем число доминирующих клеток снизу, а нахождение на пересечении столбцов с преобладанием определённого цвета ещё ничего не гарантирует. Мне поначалу утверждение казалось "очевидным", но было это "по модулю" неверного факта.

Сейчас я думаю, что оптимальная оценка числа доминирующих клеток далеко не так проста, и имеет смысл задать отдельный вопрос по этому поводу, и постепенно его разрешить. Пока что я доказательством не располагаю, а написанное мной Дополнение я уберу, так как рассуждение в нём ошибочно.

(3 Май '17 22:27) falcao
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,698

задан
23 Апр '17 14:56

показан
1147 раз

обновлен
3 Май '17 22:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru