Школьная задачка

vital_m

Квадрат 8x8 клеток выкрашен в белый цвет. Разрешается выбрать в нем любой прямоугольник
из трех клеток и перекрасить все их в противоположный цвет
(белую клетку --- в черный, черную клетку --- в белый).
Удастся ли несколькими такими операциями перекрасить весь квадрат в
черный цвет?
Не могу решить

greekdom

Удастся ли несколькими такими операциями перекрасить весь квадрат в
серный цвет?
Из условий задачи очевидно что нет

vital_m

Очепятка (по Фрейду).

asgrig

почему это?

naami_moloko

Вероятно доказывается что нет (по индукции? по крайней мере придумал индукционный метод как перекрасить любой квадрат NxN, N - нечётное, больше одного.

ddeev

В черный цвет всю доску не перекрасить.
Достаточно рассмотреть следующее множество клеток:
10110110
00000000
10110110
10110110
00000000
10110110
10110110
00000000
За одно перекрашивание свой цвет меняет четное количество клеток, обозначенных цифрой 1. Но сначала все они белые и их нечетное кол-во. Значит, не перекрасить.

ddeev

С помощью моей раскраски доказывается, что для 7х7 твой метод не работает.

naami_moloko

В условии написано, что изначально квадрат белый, а не такой как у тебя...
А вообще я свой метод не рассказал...

milana1

боюсь, только для 3*n работает

vital_m

Круто !
Огромное спасибо !

Ksun

У Паши ('a) правильное решение Квадрат у него изначально белый, единички - это для инварианта (четность количества клеток одного цвета на этих местах при перекрашивании не меняется)

zuzaka

Так сказать, заведомо не работает для 3n+1 и 3n+2

naami_moloko

Согласен

Totti2008

Может, быть я не права - исправьте!
Рассмотрим квадрат 2*2 белого цвета. И будем выбирать на нем фигуру из 3-х клеток, как показано на рисунке, тогда его возможно перекрасить в черный. Тогда возможно и для квадрата 8*8

vital_m

Там требовалось раскрашивать прямоугольниками из трех клеток.

viktor-69

К сожалению, уголок не является прямоугольником.

Totti2008

тогда жаль

vital_m

Да забей,ведь задачу уже решили.
Оставить комментарий
Имя или ник:
Комментарий: