Given a finite collection of of sets, closed under union (that is, if \(A\) and \(B\) are sets belonging to the collection, then \(A\cup B\) is also a set in the collection.)

Prove or disprove: There exists an element that belongs to at least half the sets in the collection.

## Comments

Sort by:

TopNewestI'll be impressed if someone comes up with a proof/disproof here, as it is presently an open question in mathematics, (first posed by Peter Frankl in 1979). :) – Brian Charlesworth · 2 years, 4 months ago

Log in to reply

I don't know about what does this "closed under union" means exactly !! No theoretical knowledge about it. But I think It can be proved using the

Principle of Mathematical Induction. One can easily show it for only sets (that is A and B). Assume it true for \(n\) sets and then try to prove it for \(n+1\)sets. – Sandeep Bhardwaj · 2 years, 4 months agoLog in to reply

closed under unionif given any 2 sets \(A\) and \(B\) in the collection, then \( A \cup B \) must also be in the collection.Standard Induction on the number of sets in the collection would unlikely work. Strong Induction might offer a possibility of approach. – Calvin Lin Staff · 2 years, 4 months ago

Log in to reply

Any hints, @Calvin Lin? – Agnishom Chattopadhyay · 2 years, 3 months ago

Log in to reply

Sometimes, open questions are solved by "amateur mathematicians" who had no idea that the problem was really difficult. This is a question that has "Olympiad Combinatorics" roots, so I felt was interesting to the L4/5's, and so I posted it. I was hoping that someone had an ah-ha moment, and could figure out a way to solve this.

I am interested in seeing approaches that people tried, and how far they pushed it out. – Calvin Lin Staff · 2 years, 3 months ago

Log in to reply

– Brian Charlesworth · 2 years, 3 months ago

Sorry for spoiling the fun, but I thought it would help others to know the background of the question and what approaches have been taken before.Log in to reply

I was going to mention the empty set, but then I realized that you mentioned that "there exists an ELEMENT", not a set. If that were the case, this conjecture would have been proven a long time ago. – Tytan Le Nguyen · 2 years, 4 months ago

Log in to reply

– Calvin Lin Staff · 2 years, 4 months ago

Well, avoid trivial cases by adding "non-empty collection" into the conditions.Log in to reply