November 2016

S M T W T F S
  1 2345
6789101112
13141516171819
20212223 242526
27282930   

Style Credit

Expand Cut Tags

No cut tags
Friday, September 12th, 2014 10:29 am
tl;dr про математику

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

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

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

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