Комбинаторика на устном туре Турнира Городов
Ошибка.
Попробуйте повторить позже
Дан клетчатый квадрат 
где 
Кроссвордом будем называть любое непустое множество его клеток, а словом — любую
горизонтальную и любую вертикальную полоску (клетчатый прямоугольник шириной в одну клетку), целиком состоящую из клеток
кроссворда и не содержащуюся ни в какой большей полоске из клеток кроссворда (ни горизонтальной, ни вертикальной). Пусть 
количество слов в кроссворде, 
— наименьшее количество слов, которыми можно покрыть кроссворд. Найдите максимум отношения 
при данном 
Источники:
Подсказка 0
Минимальное количество слов в кроссворде не совпадает с общим количеством слов в случае, когда какие-то слова идут параллельно друг другу и имеют общую границу клеток.
Подсказка 1
Для начала получим оценку. Рассмотрим, ско́льким словам может принадлежать одна клетка. Сколько среди них может быть вертикальных и горизонтальных? Сколько могут не принадлежать минимальному разложению?
Подсказка 2
Верно, каждая клетка содержится максимум в одном горизонтальном и одном вертикальном слове. Назовём слова из минимального покрытия кроссворда правильными, все остальные - неправильными. Каждая клетка должна принадлежать хотя бы одному правильному слову. Что тогда можно сказать об общем количестве клеток в неправильных словах?
Подсказка 3
Правильно, каждая клетка входит не более чем в одно неправильное слово, тогда сумма клеток в таких словах не больше общего количества клеток в кроссворде (пусть всего их z). Теперь, когда нам известна верхняя граница на количество клеток в таких словах, мы можем найти верхнее ограничение на количество самих неправильных слов, если разделим z на минимум клеток в одном неправильном слове
Подсказка 4
Так как слова, состоящие из одной клетки точно правильные, то в одном неправильном слове хотя бы 2 клетки. Аналогично найдём количество правильных слов: сначала выясним, сколько суммарно букв в правильных словах (воспользуемся тем, что правильные слова покрывают все клетки) и поделим на минимальное количество букв в одном правильном слове.
Подсказка 5
Остаётся только найти искомое отношение и составить подходящий пример. Такой случай легко находится, если вспомнить, что максимальное количество неправильных слов достигается, когда в одном неправильном слове 2 клетки.
Пример. Для прямоугольника 
получаем 
Оценка. Пусть в кроссворде 
клеток. Выберем некоторое его покрытие наименьшим количеством слов. Слова из этого покрытия
назовём правильными, а остальные неправильными.
Каждая клетка содержится не более чем в одном горизонтальном и одном вертикальном слове. Хотя бы одно из этих слов правильное,
так как правильные слова покрывают весь кроссворд. Значит, каждая клетка принадлежит не более чем одному неправильному слову.
Поэтому сумма количеств клеток в неправильных словах не больше 
Если клетка является словом, то к ней не примыкает другая клетка кроссворда ни по горизонтали, ни по вертикали. Следовательно,
клетка входит в любое покрытие кроссворда словами и, значит, является правильным словом. Поэтому все неправильные слова содержат не
меньше чем по две клетки и количество неправильных слов не больше 
Так как правильные слова покрывают весь кроссворд, сумма количеств клеток в них не меньше 
Каждое слово содержит не больше
клеток, поэтому количество правильных слов не меньше 
Отсюда
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
