Можно ли будет покрыть квадрат 8 x 8, если одну квадратную плитку заменить прямоугольной полоской?

1. Сначала посчитаем площадь большого квадрата: $8 \times 8 = 64$ клетки. Плитки $2 \times 2$ имеют площадь $2 \times 2 = 4$ клетки. Полоски $1 \times 4$ имеют площадь $1 \times 4 = 4$ клетки. Каждая плитка или полоска занимает 4 клетки. Если мы заменим одну квадратную плитку $2 \times 2$ на прямоугольную полоску $1 \times 4$, то площадь, которую они покрывают, останется неизменной (по 4 клетки каждая). Задача состоит в том, можно ли в принципе покрыть квадрат $8 \times 8$ такими плитками и полосками. Рассмотрим раскраску доски в 4 цвета. Доска $8 \times 8$ имеет 64 клетки. Если раскрасить доску в 4 цвета, например, "горизонталями" (то есть, каждая строка имеет свой цвет, или каждые 4 строки повторяют цвета), то: - Плитка $2 \times 2$ всегда покрывает по одной клетке каждого цвета, если раскраска цветов $1, 2, 3, 4, 1, 2, 3, 4$ по строкам или столбцам. - Полоска $1 \times 4$ всегда покрывает 4 клетки одного цвета, если она лежит в одной строке/столбце, или по одной клетке каждого цвета, если раскраска по одной из осей. Если использовать раскраску в 4 цвета таким образом, что каждые 4 столбца имеют свои цвета, повторяющиеся по кругу. То есть, столбцы 1, 5 — цвет 1; столбцы 2, 6 — цвет 2; столбцы 3, 7 — цвет 3; столбцы 4, 8 — цвет 4. Тогда: * Плитка $2 \times 2$: каждая плитка $2 \times 2$ будет покрывать две клетки одного цвета и две клетки другого цвета, если она лежит вдоль границы цветов. Или по одной клетке каждого цвета, если она пересекает границы всех 4 цветов. * Полоска $1 \times 4$: если полоска $1 \times 4$ располагается горизонтально, она покроет 4 клетки разных цветов (1, 2, 3, 4). Если вертикально, она покроет 4 клетки одного цвета. Теперь, если мы раскрасим доску в 4 цвета таким образом, чтобы каждая клетка $(i, j)$ имела цвет $(i \pmod 4) \times 2 + (j \pmod 2) + 1$ (это одна из возможных раскрасок). Рассмотрим более простую раскраску: клетки $(i,j)$ имеют цвет $C(i,j) = ((i \pmod 2) + (j \pmod 2)) \pmod 2$. Это раскраска в 2 цвета (шахматная). Тогда плитка $2 \times 2$ всегда покроет 2 белые и 2 чёрные клетки. Полоска $1 \times 4$ покроет 2 белые и 2 чёрные клетки. Значит, это не помогает. Давай попробуем раскраску в 4 цвета, где клетки $(i,j)$ имеют цвет $(i \pmod 4)$. * Квадрат $8 \times 8$ имеет по $8 \times 2 = 16$ клеток каждого цвета ($0, 1, 2, 3$). * Плитка $2 \times 2$: если она лежит, например, в строках $k, k+1$, то она покрывает 2 клетки цвета $k \pmod 4$ и 2 клетки цвета $(k+1) \pmod 4$. Она не покрывает все 4 цвета сразу. Она покрывает 2 клетки одного цвета и 2 другого. * Полоска $1 \times 4$: если она горизонтальная, то она покрывает 4 клетки одного цвета ($i \pmod 4$). Если вертикальная, она покрывает 4 клетки разных цветов ($i \pmod 4, (i+1) \pmod 4, (i+2) \pmod 4, (i+3) \pmod 4$). Теперь, если раскрасить доску в 4 цвета так, что каждая клетка $(i, j)$ имеет цвет $C(i, j) = (i \pmod 2, j \pmod 2)$ (это не 4 цвета, а 4 комбинации $00, 01, 10, 11$). Давай попробуем раскраску, где цвета повторяются каждые две клетки по горизонтали и каждые две клетки по вертикали, то есть цвет клетки $(i,j)$ будет $C(i,j) = (i \pmod 2) + 2(j \pmod 2)$. Это даст 4 цвета: 0, 1, 2, 3. На доске $8 \times 8$ будет по 16 клеток каждого цвета. * Плитка $2 \times 2$ (квадрат): любая плитка $2 \times 2$ всегда покрывает по одной клетке каждого из 4 цветов. Значит, каждая плитка $2 \times 2$ покрывает по 1 клетке каждого цвета. * Полоска $1 \times 4$: * Если она лежит горизонтально, она может покрыть либо 2 клетки цвета $C(i,j)$ и 2 клетки цвета $C(i, j+1)$, либо по одной клетке всех 4 цветов, либо все 4 клетки одного цвета, в зависимости от того, как она расположена. * Если она лежит вертикально, она покроет 2 клетки цвета $C(i,j)$ и 2 клетки цвета $C(i+1, j)$. Пусть раскраска будет такой: клетке $(i, j)$ присвоим цвет $i \pmod 4$. * Квадрат $8 \times 8$ имеет 8 строк. Каждая из строк $0, 4$ имеет цвет 0. Каждая из строк $1, 5$ имеет цвет 1. Каждая из строк $2, 6$ имеет цвет 2. Каждая из строк $3, 7$ имеет цвет 3. В итоге у нас по $2 \times 8 = 16$ клеток каждого цвета. * Плитка $2 \times 2$: если она лежит в строках $i, i+1$, она покрывает 2 клетки цвета $i \pmod 4$ и 2 клетки цвета $(i+1) \pmod 4$. * Полоска $1 \times 4$: * Если она горизонтальная, она лежит в одной строке, поэтому все 4 клетки будут одного цвета ($i \pmod 4$). * Если она вертикальная, она покрывает 4 клетки в строках $i, i+1, i+2, i+3$. То есть она покроет по одной клетке каждого из 4 цветов. Теперь к вопросу: Если изначально квадрат $8 \times 8$ покрыт $N$ плитками $2 \times 2$ и $M$ полосками $1 \times 4$. Общая площадь $4N + 4M = 64$. Если одну плитку $2 \times 2$ заменить на полоску $1 \times 4$, то количество клеток каждого цвета, покрываемых этими фигурами, изменится. Рассмотрим раскраску "диагоналями" в 4 цвета, где цвет клетки $(i,j)$ равен $(i+j) \pmod 4$. На доске $8 \times 8$ количество клеток каждого цвета будет: Цвет 0: 16 клеток Цвет 1: 16 клеток Цвет 2: 16 клеток Цвет 3: 16 клеток * Плитка $2 \times 2$: Пусть верхний левый угол плитки находится в $(i,j)$. Клетки плитки: $(i,j)$ - цвет $(i+j) \pmod 4$ $(i,j+1)$ - цвет $(i+j+1) \pmod 4$ $(i+1,j)$ - цвет $(i+1+j) \pmod 4$ $(i+1,j+1)$ - цвет $(i+1+j+1) \pmod 4 = (i+j+2) \pmod 4$ Эти 4 клетки будут иметь цвета $X, X+1, X+1, X+2$ (по модулю 4). То есть два цвета будут одинаковыми, а два других - разными. Например, $0, 1, 1, 2$. Значит, плитка $2 \times 2$ покрывает по одной клетке двух цветов и по две клетки одного цвета, или по две клетки двух цветов. Например: $(0,0)$ имеет цвет 0. Тогда плитка $2 \times 2$ с началом в $(0,0)$ покроет цвета $0, 1, 1, 2$. То есть: 1 клетка цвета 0, 2 клетки цвета 1, 1 клетка цвета 2. * Полоска $1 \times 4$: * Горизонтальная полоска в строке $i$, начиная с $j$: $(i,j), (i,j+1), (i,j+2), (i,j+3)$. Цвета: $(i+j) \pmod 4, (i+j+1) \pmod 4, (i+j+2) \pmod 4, (i+j+3) \pmod 4$. Она покроет по одной клетке каждого из 4 цветов. * Вертикальная полоска в столбце $j$, начиная с $i$: $(i,j), (i+1,j), (i+2,j), (i+3,j)$. Цвета: $(i+j) \pmod 4, (i+1+j) \pmod 4, (i+2+j) \pmod 4, (i+3+j) \pmod 4$. Она покроет по одной клетке каждого из 4 цветов. Итак, при раскраске доски в 4 цвета "диагоналями", каждая полоска $1 \times 4$ покрывает ровно по одной клетке каждого из 4 цветов. А плитка $2 \times 2$ покрывает 1 клетку одного цвета, 2 клетки другого цвета и 1 клетку третьего цвета. Если одна плитка $2 \times 2$ заменяется на полоску $1 \times 4$, то изменение в покрытии цветов происходит так: Было: (1, 2, 1, 0) для плитки $2 \times 2$ (например, цвета $0,1,2,3$). Стало: (1, 1, 1, 1) для полоски $1 \times 4$. Это значит, что для одного цвета количество клеток, покрытых плитками, уменьшится на 1, для другого — увеличится на 1, для третьего — уменьшится на 1, а для четвертого — увеличится на 1. То есть, общее количество клеток каждого цвета, покрытых фигурами, изменится. Если изначально покрытие было возможно, то есть сумма покрытых клеток каждого цвета делилась нацело на 16 (так как по 16 клеток каждого цвета), то после замены оно может стать невозможным. При такой раскраске, если покрытие было возможно, то сумма клеток каждого цвета, покрытых плитками и полосками, должна быть кратна 16. Если у нас есть $N$ плиток $2 \times 2$ и $M$ полосок $1 \times 4$. Для плитки $2 \times 2$ с началом $(i,j)$ цвета: $C_0=(i+j)\pmod 4$, $C_1=(i+j+1)\pmod 4$, $C_2=(i+j+1)\pmod 4$, $C_3=(i+j+2)\pmod 4$. Для полоски $1 \times 4$ все цвета $0,1,2,3$ покрыты поровну. Если все $N$ плиток $2 \times 2$ и $M$ полосок $1 \times 4$ покрывают всю доску, то общее количество клеток каждого цвета, покрытых всеми плитками, должно быть 16. Если мы заменим одну плитку $2 \times 2$ на полоску $1 \times 4$, то для данной раскраски распределение по цветам изменится. Из-за этого изменение, покрытие может стать невозможным. Именно раскраска в 4 цвета "диагоналями" часто используется для доказательства невозможности покрытий. **Ответ:** 1. Нет, у меня не получилось. 2. Диагоналями