2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Придумал задачу на раскраску и не могу решить
Сообщение07.02.2022, 10:43 


20/04/15
20
Придумал следующую задачу на раскраску:

Пусть каждая точка плоскости раскрашена в 2 цвета, и каждый отрезок плоскости раскрашен в 2 цвета.
Назовём ломаную (все вершины различны) с конечным или бесконечным количеством звеньев хорошей, если все её звенья какого-то одного цвета и все её вершины какого-то одного цвета.
Пусть $f$ — какая-то раскраска точек и отрезков.
Введём следующие предикаты:
$A(f) = $"существует хорошая ломаная с бесконечным числом звеньев";
$B(f) = $"все хорошие ломаные имеют конечное число звеньев, но существуют хорошие ломаные со сколь угодно большим числом звеньев";
$C(f) = $"существует $n$ такое, что все хорошие ломаные имеют не более $n$ звеньев".

Очевидно, что всегда существует хорошая ломаная из одного звена и очевидно, что верно ровно одно из следующих утверждений:
$Q=\forall fA(f)$;
$W=\exists fB(f)\&\forall f(\neg A(f)\to B(f))$
$E=\exists fC(f)$

Так какое из них верно?

Можно ввести ещё один предикат:
$D(f) = $"существует хорошая ломаная, уходящая в бесконечность"
и выяснить истинность утверждения
$R=\forall f(A(f)\to D(f))$

Если задача показалась лёгкой, то введите одно или несколько следующих дополнительных условий на хорошую ломаную:
1) Отрезки ломаной пересекаются не более чем в одной точке;
2) Отрезки ломаной не пересекаются;
3) Отрезки ломаной имеют одинаковую длину;
4) Отрезки ломаной имеют натуральную длину;
5) Направления звеньев ломаной ограничено конечным числом;
6) Направления звеньев ломаной ограничено счётным множеством;

Другие варианты усложнения задачи:
1) То же для $n$ цветов;
2) То же для счётного множества цветов;
3) То же для континуального множества цветов;
4) А если количество цветов для точек и отрезков различно?

Можно попытаться расширить для многогранников (с треугольными гранями и раскраской для треугольников) или пространственных ломаных.

Приводит ли какая-то комбинация условий к интересной задачи, или все они решаются в пару действий?

 Профиль  
                  
 
 Re: Придумал задачу на раскраску и не могу решить
Сообщение07.02.2022, 13:21 
Заслуженный участник
Аватара пользователя


16/07/14
9151
Цюрих
В базовой постановке задача эквивалентна "верно ли, что для любого графа с несчетным числом вершин либо сам граф, либо его дополнение содержат несчетный путь"? И увеличение числа цветов для точек (пока их не слишком много - чтобы точек хотя бы одного цвета было меньше континуума) задачу не меняет.
Если потребовать, чтобы все отрезки ломаной имели длину $1$, то вопрос существования хорошей ломаной из 1 звена в зависимости от числа цветов для точек эквивалентен вопросу о хроматическом числе плоскости, который открыт.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group