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