Fdtxjr

How to explain what's wrong with this application of the chain rule?

What was the exact wording from Ivanhoe of this advice on how to free yourself from slavery?

Travelling outside the UK without a passport

Open a doc from terminal, but not by its name

Why did the HMS Bounty go back to a time when whales are already rare?

What is the evidence for the "tyranny of the majority problem" in a direct democracy context?

Why is it that I can sometimes guess the next note?

A social experiment. What is the worst that can happen?

Biological Blimps: Propulsion

Lowest total scrabble score

Why do we read the Megillah by night and by day?

Is a bound state a stationary state?

How do you respond to a colleague from another team when they're wrongly expecting that you'll help them?

Can someone explain how this makes sense electrically?

Creepy dinosaur pc game identification

Which one is correct as adjective “protruding” or “protruded”?

The IT department bottlenecks progress. How should I handle this?

Store Credit Card Information in Password Manager?

Is it improper etiquette to ask your opponent what his/her rating is before the game?

How can "mimic phobia" be cured or prevented?

Is it better practice to read straight from sheet music rather than memorize it?

Does a 'pending' US visa application constitute a denial?

What does chmod -u do?

What is Cash Advance APR?

Let X be an n element set

Intersection Safe FamiliesFinite sets with densityAbout two equinumerous partitions of the same set.Picking set not containing any specified subsetHypergraph rainbow colouring of $1 dots n$ for $A = A_1, dots A_k : A_i subset 1, dots n$Prove that the intersection of all the sets is nonempty.The structure of a family of k- subsets of a n-setThe pigeonhole principle(?)Counting sequences of subsets that have a certain property.Proving that there is an element common to all $35$ sets given certain set restrictions

1

1

$begingroup$

Let $X$ be an n element set, and let $A_1, ..., A_m$ be not
necessarily distinct, nonempty subsets of $X$. Prove that there exists
a subset from the list such that every element of this subset is
contained in at least $m/n$ sets among $A_1, ..., A_m$.

I have spent quite a time to come up with something but I am stuck. My first idea was to create a random variable $O_x$ so it represents the number of occurences for a given number $x$. I was able to see $E[O_x] geq m/n$ but the rest didn't go as I expected.

Now I think of another approach. It would be to calculate the probability of having 1 element among $m/n$ sets and raising that expression to power of $k$-- the cardinality of the wanted set, if I could show it is greater than zero it should be cleared, right?

There is also proof by contradiction. If you assume the result is false, then this means for all $A_i$, there exists some $x in A_i$ such that x is contained in at most $m/n$ sets among $A_1,...,A_m$. I think with this maybe I can show $|cup A_i| < m$, but this is a contradiction as $A_1,...,A_m$ is guaranteed to be at least $|m|$ since they are all non-empty.

Anyway, I think I am lost on this one and I would kindly ask for a hint or a directive.

combinatorics

share|cite|improve this question

edited Oct 24 '18 at 11:13

bof

52.5k558121

asked Oct 23 '18 at 21:35

user2694307user2694307

336311

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is it $mge n?$
  $endgroup$
  – mfl
  Oct 23 '18 at 21:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @mfl It is not given in the question, but I think if you take $m$ less than $n$, the claim still holds.
  $endgroup$
  – user2694307
  Oct 23 '18 at 21:45
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @bof D'oh silly me, ill delete my comment!
  $endgroup$
  – Slugger
  Oct 23 '18 at 23:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Assume it were not true. Try to prove that that would mean $|cup_i=1^m A_i| > n$.
  $endgroup$
  – fleablood
  Oct 23 '18 at 23:22
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @fleablood Yes, I am also working on contradiction. Just to be sure, is the negation of the claim "for all $A_i$, there exists an $xin A_i$ s.t $x$ is contained in at most $m/n$ sets among $A_1, ..., A_m$"?
  $endgroup$
  – user2694307
  Oct 23 '18 at 23:26
  
  

  
  
  
  

 | 
show 4 more comments

1

1

$begingroup$

Let $X$ be an n element set, and let $A_1, ..., A_m$ be not
necessarily distinct, nonempty subsets of $X$. Prove that there exists
a subset from the list such that every element of this subset is
contained in at least $m/n$ sets among $A_1, ..., A_m$.

I have spent quite a time to come up with something but I am stuck. My first idea was to create a random variable $O_x$ so it represents the number of occurences for a given number $x$. I was able to see $E[O_x] geq m/n$ but the rest didn't go as I expected.

Now I think of another approach. It would be to calculate the probability of having 1 element among $m/n$ sets and raising that expression to power of $k$-- the cardinality of the wanted set, if I could show it is greater than zero it should be cleared, right?

There is also proof by contradiction. If you assume the result is false, then this means for all $A_i$, there exists some $x in A_i$ such that x is contained in at most $m/n$ sets among $A_1,...,A_m$. I think with this maybe I can show $|cup A_i| < m$, but this is a contradiction as $A_1,...,A_m$ is guaranteed to be at least $|m|$ since they are all non-empty.

Anyway, I think I am lost on this one and I would kindly ask for a hint or a directive.

combinatorics

share|cite|improve this question

edited Oct 24 '18 at 11:13

bof

52.5k558121

asked Oct 23 '18 at 21:35

user2694307user2694307

336311

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Is it $mge n?$
  $endgroup$
  – mfl
  Oct 23 '18 at 21:44
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @mfl It is not given in the question, but I think if you take $m$ less than $n$, the claim still holds.
  $endgroup$
  – user2694307
  Oct 23 '18 at 21:45
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @bof D'oh silly me, ill delete my comment!
  $endgroup$
  – Slugger
  Oct 23 '18 at 23:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Assume it were not true. Try to prove that that would mean $|cup_i=1^m A_i| > n$.
  $endgroup$
  – fleablood
  Oct 23 '18 at 23:22
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @fleablood Yes, I am also working on contradiction. Just to be sure, is the negation of the claim "for all $A_i$, there exists an $xin A_i$ s.t $x$ is contained in at most $m/n$ sets among $A_1, ..., A_m$"?
  $endgroup$
  – user2694307
  Oct 23 '18 at 23:26
  
  

  
  
  
  

 | 
show 4 more comments

$begingroup$

Let $X$ be an n element set, and let $A_1, ..., A_m$ be not
necessarily distinct, nonempty subsets of $X$. Prove that there exists
a subset from the list such that every element of this subset is
contained in at least $m/n$ sets among $A_1, ..., A_m$.

I have spent quite a time to come up with something but I am stuck. My first idea was to create a random variable $O_x$ so it represents the number of occurences for a given number $x$. I was able to see $E[O_x] geq m/n$ but the rest didn't go as I expected.

Now I think of another approach. It would be to calculate the probability of having 1 element among $m/n$ sets and raising that expression to power of $k$-- the cardinality of the wanted set, if I could show it is greater than zero it should be cleared, right?

There is also proof by contradiction. If you assume the result is false, then this means for all $A_i$, there exists some $x in A_i$ such that x is contained in at most $m/n$ sets among $A_1,...,A_m$. I think with this maybe I can show $|cup A_i| < m$, but this is a contradiction as $A_1,...,A_m$ is guaranteed to be at least $|m|$ since they are all non-empty.

Anyway, I think I am lost on this one and I would kindly ask for a hint or a directive.

combinatorics

share|cite|improve this question

edited Oct 24 '18 at 11:13

bof

52.5k558121

asked Oct 23 '18 at 21:35

user2694307user2694307

336311

$endgroup$

share|cite|improve this question

edited Oct 24 '18 at 11:13

bof

52.5k558121

asked Oct 23 '18 at 21:35

user2694307user2694307

336311

share|cite|improve this question

edited Oct 24 '18 at 11:13

bof

52.5k558121

asked Oct 23 '18 at 21:35

user2694307user2694307

336311

edited Oct 24 '18 at 11:13

bof

52.5k558121

edited Oct 24 '18 at 11:13

bof

52.5k558121

asked Oct 23 '18 at 21:35

user2694307user2694307

336311

asked Oct 23 '18 at 21:35

user2694307user2694307

336311

1 Answer
1

active

oldest

votes

1

$begingroup$

The statement is false for $m=0$ so let's assume $mgt0$, which I'm sure is what you intended.

Write $[m]=1,dots,m$.

For $xin X$ let $I_x=iin[m]:xin A_i$.

Let $B=I_x$.

If $B=emptyset$ any $A_i$ will work, so let's assume $Bneemptyset$. Then
$$sum_xin B|I_x|ltsum_xin Bfrac mn=|B|frac mnle|X|frac mn=m$$
and so
$$left|bigcup_xin BI_xright|lesum_xin B|I_x|lt m.$$
Therefore we can choose an index $iin[m]$ such that $inotinbigcup_xin BI_x$, which means that $A_icap B=emptyset$, which means that $|I_x|gefrac mn$ for every $x$ in $A_i$.

share|cite|improve this answer

answered Oct 24 '18 at 11:05

bofbof

52.5k558121

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot! I try to understand the last sentence though. How do we conclude the "for all" part? Besides, my approach in the end was to assume the negative, retrieve the $<m$ part, and conclude it's a contradiction since it should be greater than or equal to $m$. Would this be a valid proof also?
  $endgroup$
  – user2694307
  Oct 24 '18 at 15:00
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  In the last sentence I can conclude that $|I_x|gefrac mn$ for every $x$ in $A_i$ because, if it failed for some $x$ in $A_i$, then for that $x$ we would have both $xin A_i$ and $|I_x|ltfrac mn$, that is, $xin A_i$ and $xin B$, contradicting the fact that $A_icap B=emptyset$.
  $endgroup$
  – bof
  Oct 24 '18 at 21:23
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2968286%2flet-x-be-an-n-element-set%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

The statement is false for $m=0$ so let's assume $mgt0$, which I'm sure is what you intended.

Write $[m]=1,dots,m$.

For $xin X$ let $I_x=iin[m]:xin A_i$.

Let $B=I_x$.

If $B=emptyset$ any $A_i$ will work, so let's assume $Bneemptyset$. Then
$$sum_xin B|I_x|ltsum_xin Bfrac mn=|B|frac mnle|X|frac mn=m$$
and so
$$left|bigcup_xin BI_xright|lesum_xin B|I_x|lt m.$$
Therefore we can choose an index $iin[m]$ such that $inotinbigcup_xin BI_x$, which means that $A_icap B=emptyset$, which means that $|I_x|gefrac mn$ for every $x$ in $A_i$.

share|cite|improve this answer

answered Oct 24 '18 at 11:05

bofbof

52.5k558121

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot! I try to understand the last sentence though. How do we conclude the "for all" part? Besides, my approach in the end was to assume the negative, retrieve the $<m$ part, and conclude it's a contradiction since it should be greater than or equal to $m$. Would this be a valid proof also?
  $endgroup$
  – user2694307
  Oct 24 '18 at 15:00
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  In the last sentence I can conclude that $|I_x|gefrac mn$ for every $x$ in $A_i$ because, if it failed for some $x$ in $A_i$, then for that $x$ we would have both $xin A_i$ and $|I_x|ltfrac mn$, that is, $xin A_i$ and $xin B$, contradicting the fact that $A_icap B=emptyset$.
  $endgroup$
  – bof
  Oct 24 '18 at 21:23
  

  
  
  
  

add a comment | 

1

$begingroup$

The statement is false for $m=0$ so let's assume $mgt0$, which I'm sure is what you intended.

Write $[m]=1,dots,m$.

For $xin X$ let $I_x=iin[m]:xin A_i$.

Let $B=I_x$.

If $B=emptyset$ any $A_i$ will work, so let's assume $Bneemptyset$. Then
$$sum_xin B|I_x|ltsum_xin Bfrac mn=|B|frac mnle|X|frac mn=m$$
and so
$$left|bigcup_xin BI_xright|lesum_xin B|I_x|lt m.$$
Therefore we can choose an index $iin[m]$ such that $inotinbigcup_xin BI_x$, which means that $A_icap B=emptyset$, which means that $|I_x|gefrac mn$ for every $x$ in $A_i$.

share|cite|improve this answer

answered Oct 24 '18 at 11:05

bofbof

52.5k558121

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks a lot! I try to understand the last sentence though. How do we conclude the "for all" part? Besides, my approach in the end was to assume the negative, retrieve the $<m$ part, and conclude it's a contradiction since it should be greater than or equal to $m$. Would this be a valid proof also?
  $endgroup$
  – user2694307
  Oct 24 '18 at 15:00
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  In the last sentence I can conclude that $|I_x|gefrac mn$ for every $x$ in $A_i$ because, if it failed for some $x$ in $A_i$, then for that $x$ we would have both $xin A_i$ and $|I_x|ltfrac mn$, that is, $xin A_i$ and $xin B$, contradicting the fact that $A_icap B=emptyset$.
  $endgroup$
  – bof
  Oct 24 '18 at 21:23
  

  
  
  
  

add a comment | 

$begingroup$

The statement is false for $m=0$ so let's assume $mgt0$, which I'm sure is what you intended.

Write $[m]=1,dots,m$.

For $xin X$ let $I_x=iin[m]:xin A_i$.

Let $B=I_x$.

If $B=emptyset$ any $A_i$ will work, so let's assume $Bneemptyset$. Then
$$sum_xin B|I_x|ltsum_xin Bfrac mn=|B|frac mnle|X|frac mn=m$$
and so
$$left|bigcup_xin BI_xright|lesum_xin B|I_x|lt m.$$
Therefore we can choose an index $iin[m]$ such that $inotinbigcup_xin BI_x$, which means that $A_icap B=emptyset$, which means that $|I_x|gefrac mn$ for every $x$ in $A_i$.

share|cite|improve this answer

answered Oct 24 '18 at 11:05

bofbof

52.5k558121

$endgroup$

share|cite|improve this answer

answered Oct 24 '18 at 11:05

bofbof

52.5k558121

answered Oct 24 '18 at 11:05

bofbof

52.5k558121

answered Oct 24 '18 at 11:05

bofbof

52.5k558121