Рассмотрим множество квадратов с окрашенными сторонами $%X$% вместе с выделенным квадратом $%x_0\in X$%. Известно, что для любого натурального $%m$%, множеством $%X$% можно замостить $%m\times m$% решетку в левом нижнем углу первой четверти плоскости, используя $%x_0$% в левом нижнем углу. Докажите, что тогда множеством $%X$% можно замостить всю 1 четверть (так чтобы в левом нижнем углу был квадрат $%x_0$%). Можно прибегать к результатам типа леммы Кёнига о бесконечном пути.

задан 30 Авг '19 3:10

изменен 30 Авг '19 3:12

10|600 символов нужно символов осталось
2

Надо рассмотреть граф, вершинами которого служат возможные замощения для разных значений m. Если замощение для числа m+1 продолжает замощение для m, то проводим ориентированное ребро из одной вершины в другую. Из природы задачи понятно, что из каждой вершины исходит лишь конечное число рёбер. Также понятно, что перед нами дерево (разные замощения не могут продолжиться в одно и то же). Дерево локально конечно, и при этом имеет сколь угодно длинные ветви, так как m может принимать любые значения. По лемме Кёнига, в дереве есть бесконечная ветвь. Она показывает, как надо замостить клетки координатного угла.

Добавление. Чтобы было понятнее, попробуем считать, что никакой леммы мы не знаем и не используем, а будем рассуждать "с нуля". У нас есть частичные покрытия координатного угла для сколь угодно больших m, их бесконечно много. Надо доказать, что весь угол можно покрыть. Угловая клетка покрыта однозначно. Пробуем покрыть соседнюю с ней справа. Это можно сделать конечным числом способов. Будем называть способ верным, если такое покрытие имеет бесконечное число продолжений. Из общих соображений следует, что хотя бы один способ покрытия второй клетки является верным. В противном случае мы имели бы для каждого случая из конечного набора конечное число продолжений, и их общее число было бы конечным.

Итак, мы покрыли вторую клетку, и знаем, что наше покрытие из двух клеток имеет бесконечное число продолжений. Пробуем покрыть третью (нумерация здесь в принципе произвольна). Для неё есть конечное число вариантов, и хотя бы один будет верным в силу тех же соображений. Покрываем её верным способом, и далее индукция.

Это неявное доказательство той же леммы Кёнига. Способ здесь принципиально неконструктивный: мы не знаем, какой именно способ покрытия очередной клетки будет верным, но мы точно знаем, что хотя бы один способ из конечного набора в таком качестве подходит.

ссылка

отвечен 30 Авг '19 3:48

изменен 30 Авг '19 21:59

Не очень понятно устройство графа. Вот пример двух замощений: http://s1.bild.me/bilder/110417/2382916clipboard.png

Квардат на 1 рисунке - замощение для случая m=1. Четыре квадрата на втором рисунке - замощение для m=2. Эти замощения должны входить в множество вершин. То есть во множество вершин что ли будут входить центр квадрата на первом рисунке и точка пересечения четырех квадратов на втором рисунке? Или Вы говорите об абстрактном графе, и его не надо представлять визуально? И что будет ребрами?

(30 Авг '19 4:08) logic

Граф содержит информацию о всех возможных замощениях квадратов. Их конечное число для каждого m. Ребро проводим тогда и только тогда, когда одно замощение продолжает другое. То есть когда к имеющемуся замощению что-то дополнительно пририсовали. Те две картинки, которые у Вас -- это просто две вершины, которые между собой не соединены. Квадрат в левом нижнем углу картинки для 2x2 не есть картинка для квадрата 1x1.

Граф имеет сложный вид, и представлять его целиком не надо. Это абстрактная вещь.

(30 Авг '19 4:16) falcao

Что значит "картинка для квадрата 1x1" в предложении Квадрат в левом нижнем углу картинки для 2x2 не есть картинка для квадрата 1x1?

Как из того, что разные замощение не могут продолжаться в одно следует, что мы имеем дело с деревом? Для деревянности надо доказать, что существует единственный путь из некоторой фиксированной вершины в любую другую, насколько я понимаю. То есть надо доказать, что (1) некоторое фиксированное замощение для некоторого m продолжается до любого наперед взятого замощения квадрата (m+k)x(m+k) и (2) что такое продолжение единственно. Или я не так интерпретирую?

(30 Авг '19 4:36) logic

@logic: Вы нарисовали две картинки -- примеры замощений квадрата 1x1 и 2x2. Это какие-то вершины графа. Скажем, u и v. Я смотрю на левый нижний угол второй картинки. Вижу, что он не такой, как квадрат на картинке u. Это значит, что в графе нет ребра из u в v.

Замощение для m может не продолжаться до замощения m+1: в дереве могут быть висячие вершины. То, что получается именно дерево, доказывается через отсутствие циклов. Если есть цикл, то берём его вершину, для которой значение m максимально. В неё заходят 2 ребра с уровня m-1. Такого не может быть по указанной выше причине.

(30 Авг '19 10:54) falcao

Какое определение дерева тут используется? Это "ацикличный ориентированный граф, в котором только одна вершина имеет нулевую степень захода, а все остальные вершины имеют степень захода 1"?

Насчет последнего абзаца последнего комментария - почему в неё заходят 2 ребра с уровня m-1? Цикл может иметь вид a->b->a. Тут в любую вершину заходит по 1 ребру.

И почему граф связен?

(30 Авг '19 21:07) logic

@logic: определение обычное: деревом называется связный граф без циклов (циклических подграфов). Отсутствие циклов я обосновал, а для связности достаточно брать связную компоненту начальной вершины -- покрытия квадрата 1x1.

Ориентация на рёбрах тут вспомогательная. Рёбра соединяют вершины соседних уровней. Если в цикле взять вершину максимального уровня m, то соседние с ней в цикле находятся на уровне m-1. Тогда получается, что в вершину уровня m заходят два ребра с предыдущего уровня из разных вершин. По смыслу это значит, что разные покрытия квадрата со стороной m-1 имеют одно продолжение.

(30 Авг '19 21:48) falcao

Добавление несколько понятнее, но почему замощений конечной части угла любого размера m x m бесконечно много? И когда говорится о продолжениях, имеется в виду продолжение до покрытия угла какого размера? На каждом шагу говорится о продолжении до покрытия угла одного и того же размера, или же определение "продолжения" зависит от шага?

(31 Авг '19 20:04) logic

@logic: для каждого m число покрытий квадрата mxm конечно, но m может быть любое, поэтому общее число частичных покрытий бесконечно. Под частичным покрытием понимается правильное покрытие какого-нибудь конечного множества клеток. Удобно брать не только квадраты, а любые покрытия. Например, клетки угла нумеровать вдоль диагоналей и последовательно их покрывать. Под продолжением понимается то, что мы на каждом шаге что-то добавляем к уже имеющемуся. Скажем, на шаге n покрываем клетку с номером n.

(31 Авг '19 20:11) falcao

А в первом аргументе то, что перед нами дерево, по сути не нужно? Для локальной конечности надо доказать, что не существует вершины, для которой верно по крайней мере одно из двух: (1) в нее входит беск много ребер (2) из нее исходит беск много ребер. Если бы существовала вершина с (1), то разные покрытия продолжались бы до одного. Если бы существовала вершина с (2), то покрытие m-квадрата продолжалось бы беск числом способом до покрытия (m+1)-квадрата. Эти случаи невозможны. Т.е. граф локально конечен. Отдельно доказываем связность. И граф бесконечен. Поэтому можноприменить лемму.

(31 Авг '19 21:33) logic

@logic: лемму Кёнига можно формулировать по-разному. Есть такие варианты, где свойство быть деревом не требуется. Одно к другому сводится без проблем. Надо заметить, что если есть дерево (корневое), то на рёбрах сразу задаётся ориентация (от центра к периферии). Если граф не является деревом, то нужно задавать ориентацию самим. Следить достаточно за тем, чтобы из любой вершины можно было выйти по стрелкам конечным числом способов. Здесь это так, потому что раскрасить очередную клетку можно лишь конечным числом вариантов. Важно только то, чтобы в доказательстве были конечные объединения.

(31 Авг '19 22:50) falcao
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,463

задан
30 Авг '19 3:10

показан
205 раз

обновлен
31 Авг '19 22:50

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru