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

[avva]

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

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

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

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

Comments

[avva.livejournal.com]

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

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

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

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

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

[(Anonymous)]

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

Re:

[avva.livejournal.com]

Чёрт его знает. Я не очень хорошо знаком с такими задачами. Эта конкретная ведь типично "олимпиадная" по своей сути, но есть и действительно серьёзные задачи в этой области. Не думаю, что раскраска часто в них помогает.

Если не ошибаюсь, например, довольно долго оставался открытым такой вопрос: можно ли заполнить квадрат меньшими квадратами с неповторяющимися размерами? (можно)

Another One

[(Anonymous)]

А Вам знакома задача из схожей "Олимпиадной" тематики про 12 мешков?
Имеется 12 мешков. Один из них отличается весом, остальные 11 - одинаковые. За три (3) взвешивания на рычажных весах нужно не только найти отличающийся мешок, но и определить, легче он или тяжелее, чем остальные.
P.S. Я до сих пор над ней бьюсь, хотя лично знаю трех людей, ее решивших. В том числе девушку, решившую ее за недолгую поездку в маршрутке. Но пока не сдаюсь ;-)

Re: Another One

[avva.livejournal.com]

Очень старая задачка. Я её знаю, да.

Re: Another One

[peretz.livejournal.com]

кстати, по поводу этой задачки про 12 мешков - мне известно ее решение с буквами. а есть какое-нибудь объяснение, формализованное с точки зрения логики? потому что к решению с буквами за время поездки в маршрутке не придешь...

Re: Another One

[haraz-bey.livejournal.com]

Есть. Даже два. Могу намылить.

Re: Another One

[peretz.livejournal.com]

Если не сложно...

Условие?

[(Anonymous)]

А можно уточнить условие, особенно - про "непотворяющиеся размеры" квадратов?

Re: Условие?

[avva.livejournal.com]

Найти такое n, и такое разбиение квадрата размером nxn клеток на конечное количество меньших квадратов, что никакие два из этих меньших квадратов не имеют одинаковый размер.

[kukukas.livejournal.com]

Вот еще пример задачки "на раскраску":

Из шахматной доски вырезали поля А1 и Н8.
Доказать возможность или невозможность заполнения доски доминошками (31 штука, каждая занимает 2 клетки).

[(Anonymous)]

А1 и Н8 - черные клетки (в общем случае - клетки одного цвета). Если их вырезать (из шахматной раскраски), то останется 30 черных клеток и 32 белых. Каждая доминошка покрывает одну черную и одну белую клетку. После покрытия 30-ю доминошками останется две белых клетки, которые не могут быть накрыты одной доминошкой ;-)