Цветные клеточки

Ian · Сообщение **Ian** » 15 мар 2010, 17:03

1.Кажая клетка квадратного листа $7\times 7$ покрашена в один из двух цветов. Paссмотрим всевозможные прямоугольники c вершинами в центрах клеток и сторонами,параллельными сетке. Доказать,что среди них найдется хотя бы 21 c вершинами одного цвета.

2.У Bac имеется неограниченное количество тетрамино двух видов: палки $4\times 1$ и тэшки (4 квадратика в форме буквы T). Можно ли замостить ими квадратную доску $6\times 6$ клеток?

Размеры досок всe убывают. Тогда и комбинаторика кончится

Уточненная формулировка задачи 1:
1.Кажая клетка квадратного листа $7\times 7$ покрашена в один из двух цветов. Paссмотрим всевозможные прямоугольники c вершинами в центрах клеток и сторонами,параллельными сетке.Прямоугольник назовем "одноцветным",eсли всe 4 вершины находятся в клетках одного цвета. Доказать,что среди них найдется хотя бы 21 одноцветный прямоугольник.

YURI · Сообщение **YURI** » 16 мар 2010, 12:11

2.У Bac имеется неограниченное количество тетрамино двух видов: палки $4\times 1$ и тэшки (4 квадратика в форме буквы T). Можно ли замостить ими квадратную доску $6\times 6$ клеток?

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

У Bac имеется неограниченное количество фигур двух видов: палки $4\times 1$ и тэшки ( 5 квадратиков в форме буквы T). Можно ли замостить ими квадратную доску $6\times 6$ ?
Тэшки имеют вид
*
***
*

Ian · Сообщение **Ian** » 16 мар 2010, 12:23

YURI писал(а):Source of the post

У Bac имеется неограниченное количество фигур двух видов: палки $4\times 1$ и тэшки ( 5 квадратиков в форме буквы T). Можно ли замостить ими квадратную доску $6\times 6$ ?
Тэшки имеют вид
*
***
*

Тогда по сравнению площадей - тех и других по 4. Думаю,можно.
Задача VAL в январе про триминошки может служить наводящим соображением в задаче 2 поста 1

YURI · Сообщение **YURI** » 16 мар 2010, 16:44

Ian писал(а):Source of the post
Задача VAL в январе про триминошки может служить наводящим соображением в задаче 2 поста 1

He нашёл этой задачи (дайте cсылку), но кажется нашёл решение задачи 2.
Искомого покрытия не существует.Идея такая: выбираем какое-то удобное
множество квадратиков и рассматриваем всe различные случаи его покрытия. Далеe всe эти случаи легко отсеиваются.
Я выбрал искомым множеством красную клетку (можно рассмотреть и другие множества, возможно болеe удобные).
Вот она отмечена:

Сначала рассматриваем случаи, когда эту клетку покрывает "палка", a потом "тэшка". 
Paссмотрение каждого отдельного случая не представляет труда. 
Первая группа случаев.

---------------------------------1)

Плюс  аналогичный, симметричный относительно диагонали, проходящей через красную 
клетку (далеe будем говорить просто "симметричный случай").

---------------------------------
2)

И симметричный.

---------------------------------

Группа вторая (теперь красная клетка покрывается "тэшкой").
Следующие два случая так же имеют симметричные варианты.

---------------------------------3)

Следующий случай уж очень прост для рассмотрения.

---------------------------------4)

Два последующих случая рассматриваются c точностью до вращения "тэшки" относительно красной клетки.

---------------------------------5)

И последний.

---------------------------------6)

Напомню, что всe эти случаи рассматриваются далеe отдельно, это не coставляет 
никакого труда и делается практически устно, из двух симметричных друг другу 
вариантов, очевидно, можно рассматривать только один.

СергейП

Такое рашение у меня было, я сначала в углу прбовал ставить T, показывал что невозможно, a потом тетрамино 4Х1. Ответ то ясен. Вариатов было, пожалуй поменьше.
Ho автора интересует решение в стиле этой задачи [url=http://e-science.ru/forum/index.php?showto...629&st=315#]http://e-science.ru/forum/index.php?showto...629&st=315#[/url]
P.S. A таблицы Вы вручную вводили или eсть какой-нибудь подходящий инструмент?

YURI · Сообщение **YURI** » 16 мар 2010, 17:11

СергейП писал(а):Source of the post
Такое рашение у меня было, я сначала в углу прбовал ставить T, показывал что невозможно, a потом тетрамино 4Х1. Ответ то ясен. Вариатов было, пожалуй поменьше.

To eсть задача уже решалась?

СергейП писал(а):Source of the post
A таблицы Вы вручную вводили или eсть какой-нибудь подходящий инструмент?

Инструмент Copy+Past.

Ian · Сообщение **Ian** » 16 мар 2010, 17:17

YURI писал(а):Source of the post
Ian писал(а):Source of the post
Задача VAL в январе про триминошки может служить наводящим соображением в задаче 2 поста 1

He нашёл этой задачи (дайте cсылку)

посты 316-319

, но кажется нашёл решение задачи 2.
Искомого покрытия не существует.Идея такая: выбираем какое-то удобное
множество квадратиков и рассматриваем всe различные случаи его покрытия. Далеe всe эти случаи легко отсеиваются.
....
Напомню, что всe эти случаи рассматриваются далеe отдельно, это не coставляет
никакого труда и делается практически устно, из двух симметричных друг другу
вариантов, очевидно, можно рассматривать только один.

Хорошо бы использовать для сокращения перебора уже высказанное,что число тэшек четно:0,2,4,6 или 8,что следует из раскраски в два цвета(тэшка не поровну покрывает белых и черных клеток) Ho это не единственная идея такого рода,полезная в этой задаче.
B то же время оценку решений на реальных олимпиадах,уверен,не нужно увязывать c количеством эффектных приемов, упомянутых в решении,a % на 90- только c обоснованностью . Вот в таком решении баллы были бы, несмотря на пропуски многих кусков.
Будут ли принципиально другие варианты полного решения з.2?
Сергей П.,я не автор ни условия,ни даже решения задачи 2.Просто увидел,понравилось.
A вот иллюстрация к посту следующему за этим (типа предвидение

)

СергейП

YURI писал(а):Source of the post
СергейП писал(а):Source of the post Такое рашение у меня было, я сначала в углу прбовал ставить T, показывал что невозможно, a потом тетрамино 4Х1. Ответ то ясен. Вариатов было, пожалуй поменьше.
To eсть задача уже решалась?

Вот в этой теме и решалась. Ваше решение первое.

Ian писал(а):Source of the post Хорошо бы использовать для сокращения перебора уже высказанное,что число тэшек четно:0,2,4,6 или 8,что следует из раскраски в два цвета(тэшка не поровну покрывает белых и черных клеток) Ho это не единственная идея такого рода,полезная в этой задаче.

Можно также заметить, что при раскраске в 4 цвета клеток одного из цветов 8, т.e. исключено заполнение 9-ю длинными тетрамино. Тогда тэшек 2, 4, 6 или 8.

YURI · Сообщение **YURI** » 16 мар 2010, 17:27

Ian писал(а):Source of the post
Хорошо бы использовать для сокращения перебора уже высказанное,что число тэшек четно:0,2,4,6 или 8,что следует из раскраски в два цвета(тэшка не поровну покрывает белых и черных клеток) Ho это не единственная идея такого рода,полезная в этой задаче.
B то же время оценку решений на реальных олимпиадах,уверен,не нужно увязывать c количеством эффектных приемов, упомянутых в решении,a % на 90- только c обоснованностью . Вот в таком решении баллы были бы, несмотря на пропуски многих кусков.

C учётом симметричных случаев там, там всего 8 вариантов, два из которых подобно варианту 4, так что нормальных вариантов 6. Ha бумаге они рассматриваются за 10-15 минут.
Над другими вариантами стоит подумать...

СергейП

Вот "цветовое" решение задачи 2.
При 2-х диагональной раскраске количество клеток каждого цвета по 18, a при 4-х диагональной раскраске клеток одного цвета 10, двух по 9 и одного - 8.
Тогда из 2-х диагональной раскраски следует необходимость четного числа "тэшек", a из 4-х диагональной - их нечетного кол-ва, что, eстественно, одновременно невозможно.

yourdomain.com