Prove or Disprove:

Given a finite collection of of sets, closed under union (that is, if AA and BB are sets belonging to the collection, then ABA\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.

Note by Calvin Lin
5 years ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

I'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 - 5 years 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 nn sets and then try to prove it for n+1n+1sets.

Sandeep Bhardwaj - 5 years ago

Log in to reply

As explained, a collection of sets is closed under union if given any 2 sets AA and BB in the collection, then AB 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 - 5 years ago

Log in to reply

Any hints, @Calvin Lin?

Agnishom Chattopadhyay Staff - 5 years ago

Log in to reply

Not really. Brian gave it away by stating that it is an open question.

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 - 5 years ago

Log in to reply

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.

Brian Charlesworth - 4 years, 12 months ago

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 - 5 years ago

Log in to reply

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

Calvin Lin Staff - 5 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...