не слишком сложная задачка

[avva]

"Квадрат размером 103x103 клетки можно полностью покрыть непересекающимися квадратами размерами 2x2 и 3x3 клетки."

Доказать или опровергнуть.

Update: Исправлено первоначально неверное условие задачи, пр. пр.

Update (3 часа после записи): в комментах появилось правильное решение! Те, кто хотят думать сами - не заглядывайте.

Comments

[gera.livejournal.com]

Квадрат 10х10 покрывается четырьмя квадратами 3х3 (в углу), а остаток - шестнадцатью по 2х2. И так сто раз.

Re:

[avva.livejournal.com]

Исправил, сорри (в первоначальном условии задачи было неправильно написано, что большой квадрат размером 100x100 - всем).

[anton.livejournal.com]

Слева и сверху два ряда 2x2, остальное поле 99x99 выложить квадратами 3x3.

Re:

[avva.livejournal.com]

Тоже неверно, просчитайте это чуть подробнее.

[bezukh.livejournal.com]

Думается мне, что я нашел некий закон- какие прямоугольники можно разбить таким вот образом (квадратами 2х2 и 3х3), а какие- нет. В данном случае (прямоугольник 103х103)- нельзя. Но доказать этот закон я не могу (голая интуиция...). Так мне его тут написать или без доказательства он не покатит?

Re:

[avva.livejournal.com]

Не, без доказательства неинтересно!

[haraz-bey.livejournal.com]

Квадрат 99х99 от начала системы координат (для простоты) заполняем клетками-тройками, а оставшееся по бокам пространство сверху и справа выкладываем слоем по две двойки.

[bezukh.livejournal.com]

Подобные варианты уже предлагали (см. выше), но так выложить не получится!
Хотя чем дальше думаешь над этой задачей, тем больше таких вот нелепых вариантов в голову лезет! Я только сейчас более менее абстрагировался от них... :-)

Re:

[avva.livejournal.com]

Не получится. Присмотритесь.

[haraz-bey.livejournal.com]

Нет, прикинул - так не канает. На стыке не сойдется. Значит, невозможно. Надо думать над доказательством

Вот если взять

[vels.livejournal.com]

103 квадрата 2х2 и 73 квадрата 3х3, то должны влезть.

Но как их туда засунуть ?
Ума не приложу :))

Re: Вот если взять

[avva.livejournal.com]

;-)

Re: Вот если взять

[(Anonymous)]

Мало того, что влезут, там еще место останется ;-)
103*2х2 + 73*3х3 = 1069
Площадь большого квадрата = 10609

[jsn.livejournal.com]

допустим, такое разбиение существует, рассмотрим его.
пронумеруем вертикали большого квадрата слева направо, для удобства.
очевидно, что каждая вертикаль пересекает нечетное число квадратов 3x3.
начнем двигаться слева направо, рассматривая соответствующие вертикали.
вертикаль #1 проходит через нечетное количество 3x3.
вертикаль #2 проходит через все те же 3x3, что и вертикаль #1, плюс, возможно, еще какое-то четное число 3x3, которые нам неинтересны.
та же фигня с вертикалью #3.
при переходе от вертикали #3 к вертикали #4 все 3x3, через которые проходит #1, заканчиваются. но поскольку #4 проходит через нечетное число 3x3, то в ней возникает нечетное число новых 3x3.
двигаясь дальше таким же образом, мы наблюдаем, как в каждой третьей вертикали обязательно возникают новые квадраты 3x3 (в нечетном количестве).
в частности, это случается и на вертикали #103, а этого не может быть, так как тут большой квадрат заканчивается.
все неверно? :)

[avva.livejournal.com]

Да, кажется, всё верно. Браво!
Это серьёзно сложнее, чем то док-во, которое я знаю, однако ;)

Вот, кажется, как Ваше доказательство можно сильно упростить и сделать более понятным:

1. Каждая вертикаль пересекает нечётное кол-во квадратов 3x3 (т.к. если бы было чётное, то сумма , на данной вертикали, их клеток плюс клеток квадратов 2x2 была бы чётной и не равной 103).

2. Начиная с первой вертикали, выбрасываем все квадраты 3x3, кроме одного (любого). При этом мы выбрасываем чётное кол-во квадратов, значит, в соседних вертикалях кол-во пересекающих их квадратов остаётся нечётным. После 1-й вертикали делаем то же самое со второй и так до конца.

3. Теперь у нас каждую вертикаль пересекает ровно 1 квадрат 3x3. Т.к. каждый такой квадрат касается 3-х вертикалей, то общее количество вертикалей должно делится на 3. Но их 103. Что и требовалось доказать.

Моё док-во всё равно красивее ;)

[bezukh.livejournal.com]

Красивое доказательство... Обидно, что мне даже не пришла в голову идея повозиться с этими вертикалями (горизонталями- какая разница!)...

[myafa.livejournal.com]

таки ерунда...

[haraz-bey.livejournal.com]

А если пойти таким путем: общая площадь квадрата равна 103*103=10609 клеток.
Следовательно, нужно найти корни уравнения 9х + 4у = 10609, либо доказать их отсутствие. Надо думать дальше.

Re:

[avva.livejournal.com]

Нет проблем их найти. Возьмите x=1 ;)

[avva.livejournal.com]

Т.к. jsn решил задачу (см. выше), напишу также другое доказательство, известное мне, и более визуальное, что ли.

1. Красим наш квадрат в два цвета: чёрный и белый. Первую горизонталь красим в чёрный, вторую в белый, третью в чёрный, итд. до конца: 103-ю в чёрный.

2. Теперь у нас на одну чёрную горизонталь больше, чем белую, поэтому непокрытых чёрных клеток на 103 больше, чем непокрытых белых клеток. Если нам удастся покрыть весь квадрат, то эта разница в 103 клетки должна упасть до 0 (т.к. не будет непокрытых клеток ни одного цвета).

3. Квадрат 2x2 занимает всегда 2 белых и 2 чёрных клетки и потому разницы не меняет. Квадрат 3x3 занимает всегда 6 клеток одного цвета и 3 другого, и поэтому меняет разницу на 3. Т.к. первоначальная разница равна 103 и на 3 не делится, то она никогда не упадёт до нуля.

Что и требовалось доказать.

[(Anonymous)]

А я зачем-то красил в шахматном порядке ;-)
Не будет ли справедливым утверждать, что раскраска является основным методом решения подобных задач про наложение?

[vels.livejournal.com]

Да, в предыдущем коментарии я полную глупость сморозил :)

На самом деле, я тут еще немного подумал и вот к чему пришел:

Начнем закрашивать большой квадрат маленькими по-спирали. Ставим 3х3 в левый нижний и красим нижнюю горизонталь вправо, пока не останется 4 клеточки до конца. Потом из правого нижнего красим 4х2 (2 по 2х2) вверх до тех пор пока не останется 3 клеточки до конца. Потом 3х3 в правый верхний и влево до тех пор пока не останется 4 клеточки до левого верхнего, и, наконец, 4х2 из левого верхнего вниз до упора.

Сложновато, признаюсь, но так уж у меня мозги работают :)

После этой процедуры у нас останется незакрашенный прямоугольник (в центре) размером 95х98. Повторяем закраску в нем и получаем незакрашенный квадрат размером 89х89. Двигаясь дальше по спирали, мы будем уменьшать стороны незакрашенного квадрата на 14 за каждые два прохода. В конце-концов, мы придем к квадрату 5х5 (7 * 14 = 98, 103 - 98 = 5).

Закрасить квадрат 5х5 квадратами 2х2 и 3х3 невозможно.

Последнее утверждение очевидно, но красивого и емкого доказательства на ум не пришло. А пришло такое:

В каждой ленте из трех горизонталей будет определенное число квадратов 2х2 и квадратов 3х3 (если какой-то квадрат находиться в двух лентах одновременно, мы считаем его только в одной, например в той, в которой находиться его верхняя часть).

Тогда будет верно следующее:

2 * х1 + 3 * y1 = 5
2 * х2 + 3 * y2 = 5

Где х1, у1 - количество квадратов 2х2 и 3х3, соответственно, в первой ленте. А х2 и у2 - во второй (причем вторая лента немножко "вылазит" за пределы квадрата 5х5, но это не страшно :).

Отсюда:

2 * (х1 + х2) + 3 * (у1 + у2) = 10

Заменим - х1 + х2 на х, а у1 + у2 - на у:

2х + 3у = 10

Так же верно и следующее:

4х + 9у = 25

Т.к. х - общее количество квадратов 2х2, а у - 3х3, а 25 - площадь квадрата 5х5.

Из этих двух уравнений выходит, что у = 5/3. Что невозможно, т.к. количество квадратов должно быть целым числом.

Вот такое сложное, громоздкое, но Альтернативное доказательство :))

а такое доказательство не подойдет?

[(Anonymous)]

т.к. фигуры - только квадраты, то можно свернуть квадрат в одну линию - его диагональ
т.е. задача упрощается до найти разбиение диагонали большого квадрата на диагонали маленьких

root(103*103) = n*root(4+4)+k*root(9+9)
103*103 = 8n + 18k + k*n*root(8*18) = 8n + 18k + 12kn = 2(4n + 9k + 6kn) = 2(2n +3k)(2n +3k)

103 = root(2)(2n+3k) - решения в целых числах не имеет

Re: а такое доказательство не подойдет?

[avva.livejournal.com]

Но ведь большая диагональ большого квадрата вовсе необязательно будет состоять из больших диагоналей меньших квадратов, а может вполне частично состоять из других диагоналей.

[ex-ilyavinar899.livejournal.com]

Я где-то видел упрощенный вариант: из шахматной доски вырезаны два квадратика на противоположных концах. Можно ли остаток полностью покрыть доминошками 1x2?

подход Конвея

[falcao.livejournal.com]

Случайно нашёл этот пост. Подумать только, 2002 год! У меня тогда не только не было ЖЖ -- я даже не знал, что такая штука существует! :)

Сразу подумалось о решении при помощи теории групп (этот подход популяризировал Джон Конвей). Достаточно доказать, что если в группе a^2 коммутирует с b^2 и a^3 с b^3, то a^103 не обязательно коммутирует с b^103.

Наложим дополнительные соотношения a^2=1 и b^3=1. Тогда условия коммутирования соблюдены, и получается свободное произведение gp(a)*gp(b) групп Z_2 и Z_3. Это неабелева группа, и в ней a^103=a, b^103=b не коммутируют.

Этот подход работает и в общем случае, то есть когда размер большого квадрата не делится на размер каждого из маленьких. Для решения задачи с 2 и 3 можно вместо свободного произведения рассматривать группу S_3, полагая a=(12) и b=(123).

Re: подход Конвея

[avva.livejournal.com]

Можете объяснить вкратце подход? Т.е. почему Достаточно доказать, что если в группе a^2 коммутирует с b^2 и a^3 с b^3, то a^103 не обязательно коммутирует с b^103?

Возможно, я это знал когда-то, а потом забыл. Сейчас что-то не доходит.