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