2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Бесконечные депутаты
Сообщение19.08.2020, 19:50 


18/07/20
42
Известная задача:
В парламенте каждый депутат имеет не более 15-и врагов. Докажите, что парламент можно разделить на две палаты так, что у каждого депутата будет не более 7-и врагов внутри палаты.
Доказательство, которое я знаю, основывается на том, что число депутатов конечно. Что происходит в случае бесконечного их числа?

 Профиль  
                  
 
 Re: Бесконечные депутаты
Сообщение19.08.2020, 20:13 
Заслуженный участник


26/05/14
981
Разбиение для бесконечного множества строится конструктивно из конечных.

 Профиль  
                  
 
 Re: Бесконечные депутаты
Сообщение20.08.2020, 09:33 
Заслуженный участник


12/08/10
1609
Это работает только для счетного множества депутатов.

 Профиль  
                  
 
 Re: Бесконечные депутаты
Сообщение20.08.2020, 11:45 


18/07/20
42
Их число в одной компоненте связности не более чем счётно.

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


23/08/07
5420
Нов-ск

(Оффтоп)

mecak17 в сообщении #1479959 писал(а):
Их число в одной компоненте связности ...
Депутатов было так много, что их соединяли в вязанки.

 Профиль  
                  
 
 Re: Бесконечные депутаты
Сообщение20.08.2020, 19:44 


18/07/20
42
Похоже, это частный случай Теоремы де Брёйна-Эрдёша. Надо было получше разобраться в теме перед тем, как постить :-(

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

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



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

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


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

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