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