?

Log in

Удивительное рядом - 301 Moved Permanently
September 12th, 2014
10:29 am
[User Picture]

[Link]

Previous Entry Share Next Entry
Удивительное рядом
tl;dr про математику

Знаете ли вы, что такое Frankl's conjecture, оно же Union-closed sets conjecture? Я тут узнал и впечатлен.

Удивительная гипотеза: для любого конечного набора конечных множеств (за исключением набора, состоящего только из пустого множества), замкнутого относительно объединения, есть элемент, принадлежащий как минимум половине множеств набора.

Ещё более удивительный факт: эта гипотеза была сформулирована в 1979 году, и до сих пор нет ни доказательства, ни контрпримера.

Согласно википедии, прогресс более чем скромный: доказана верность гипотезы в одном из следующих случаев:
  • В наборе не более 46 множеств
  • Объединение всех множеств набора содержит не более 11 элементов
  • В наборе есть наименьшее множество из одного или двух элементов.
Я придумал штук десять почти доказательств, каждое из которых упиралось в какую-то маленькую "очевидную" деталь.

herereplycomment count unavailablecomments

Current Mood: excitedexcited
Current Music: Mind Ecology + Natural Elements + Shakti
Tags:

(2 comments | Leave a comment)

Comments
 
[User Picture]
From:bromozel
Date:September 12th, 2014 02:03 pm (UTC)
(Link)
Ага, я тоже пытался доказать и дважды уже начинал писать доказательство начистоту :)
Но у меня был интерес, так как мы написали пару статей про кооперативные игры, где кооперироваться разрешалось только коалициям из некоторого union closed семейства.
[User Picture]
From:k_shemyak
Date:September 16th, 2014 03:35 pm (UTC)
(Link)
Ну что уж стесняться, давай опубликуй здесь самое короткое из "очевидных" ;-)
Unnkerr blog Powered by LiveJournal.com