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
9255
Цюрих
В базовой постановке задача эквивалентна "верно ли, что для любого графа с несчетным числом вершин либо сам граф, либо его дополнение содержат несчетный путь"? И увеличение числа цветов для точек (пока их не слишком много - чтобы точек хотя бы одного цвета было меньше континуума) задачу не меняет.
Если потребовать, чтобы все отрезки ломаной имели длину $1$, то вопрос существования хорошей ломаной из 1 звена в зависимости от числа цветов для точек эквивалентен вопросу о хроматическом числе плоскости, который открыт.

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

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



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

Сейчас этот форум просматривают: gogoshik


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

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