A problem on minimization

Let |S| denote the number of elements in the set S while n(S) denote the number of subsets of S including itself and the null set.

If A, B, C are sets for which
n(A) + n(B) + n(C) = n(A U B U C) and |A|=|B|=100,
find the minimum value of |A\cap B\cap C|.

(This problem appeared in AHSME 1991. I first thought of putting this problem in the Olympiad section, but its rather on the easier side. So finally decided to put it here.)

17 Answers

11
Devil ·

\left|A\cup B\cup C \right|=\sum{|A|}-\sum{|A\cap B|}+|A\cap B\cap C|

Again as before, let |C|=d and |A\cup B\cup C| =x - and again as before d=101 and x=102.

So from the 1st eqn our |A\cap B\cap C| ={|A\cup B\cup C}|-\left(\sum{|A|} \right)+\sum{\left|A\cap B \right|}.

I need to minimise \sum{\left|A\cap B \right|}

I have the following information at hand :- If I see set A as a reference, then there are just 2 elements (not belonging to A ) in the entire union set of A,B,C - since A\cup B\cup C=102.

Let m of these "new " elements be in set B.

Clearly 0\le m\le 2.

And also let n of these elements be in set C.

Let m≥n - then 100-m<101-n.

So our \sum{\left|A\cap B \right|}=(100-m)+n+(101-n)+100-m =301-2m.

For this to be minimum m=2, so finally the correct answer turns out to be 98.

Thank GOD!

1
Techboy ·

ans is 2 but how?????

11
Devil ·

@ srk, ans is 2.

@ Anant sir, - I think it can also be got from what I did. If the last part of my soln is unclear, then I'm elaborating it here.

As already said, in the union of A,B,C there must be 2 elements that are not present in any of the sets, let me set set A as my reference.

Let these "new" elemenets be x and y.

Also let m of these elements be in B and n in C.

CASE -1, m>n.

(m,n)=(2,1).

So that gives \left|A\cup C \right|=100.

\left|A\cup B \right|=98 & \left|C\cup B \right|=99.

Also \boxed{ \sum{\left|C\cup B \right|}=297}....(1).

CASE-II m=n.

a) x in B, y in C.
b) x,y present in both sets B and C, that in the previous fashion gives a) \sum{|A\cap B|}>297 & for b) \sum{|A\cap B|}=297.

CASE 3 when n>m. (n,m)=(2,0) (2,1) - in similar fashion we have for (n,m)=(2,0) \sum{|A\cap B|}> 297 & for (n,m)=(2,1) \sum{|A\cap B|}= 297.

Thus minimum {|A\cap B \cap C|}= 297-\left(\sum{|A|} \right)+\sum{|A\cup B\cup C|} =98.

Now pls reply, whether correct or not.

1
Techboy ·

IF x,y belongs toR AND x2+y2 +xy=1,then minimum value of

x3y+xy3+4=?

1
harsh jindal ·

kaymant sir
consider \left|A\bigcap{B}\bigcap{C} \right|=97
IT MEANS THAT \left|A\bigcup{B} \right|\geq 103
ALSO\left|A\bigcup{B\bigcup{C}} \right|\geq 103
IT SHOWS THAT THE LEAST VALUE MUST BE 98

11
Devil ·

Sir, but what is wrong in my soln?

66
kaymant ·

Sorry that's wrong sign in my previous post. Editing.

1
harsh jindal ·

if \left| A\bigcap{B\bigcap{C}}\right| <\ 97 then how can be it is a problem of minimization

66
kaymant ·

I have the following:
The given condition n(A)+n(B)+n(C)=n(AUBUC) translates to the equation
2101 + 2|C| = 2|AUBUC|
That is
1 + 2|C|-101 = 2|AUBUC|-101
Since LHS > 1, an odd number and same as a power of 2, we must have |C| =101 and hence |AUBUC| = 102.

Next, we have from PIE, that
|A\cup B\cup C| = \sum_\mathrm{cyc}|A|-\sum_\mathrm{cyc}|A\cap B|+|A\cap B\cap C|
Further,
|A\cap B|=|A|+|B|-|A\cup B|
and similarly for the other two intersections, so we get
|A\cap B\cap C| = |A\cup B\cup C|+(|A|+|B|+|C|)-\sum_\mathrm{cyc}|A\cup B|
Further, since A\cup B \subset A\cup B\cup C, so |A\cup B|\le |A\cup B\cup C|
and similarly for other two unions.
Hence, we get
|A\cap B\cap C|\ge |A|+|B|+|C|-2|A\cup B\cup C|=97
So, |A\cap B\cap C| is bounded below by 97.

The question is whether or not the equality be attained.

1
harsh jindal ·

i think it will be 98 ???

1
harsh jindal ·

it should be 98

1
buzz ·

ooohh i realized my solution is wrong...
coz if to sets are unique... the there will also subset including members of both the sets... which will increase the no. of subsets....

:( :( :( :(

1
buzz ·

the ans is zero....


hence now... unique sets so |a∩b∩c| will be zero... coz a∩b∩c is zero....

1
harsh jindal ·

kaymant Sir please tell the correct answer

1
harsh jindal ·

Soumik check my given sets and find error ?
i am again getting 98

1
harsh jindal ·

consider
set A={1,2,3,4........100}
set B={3,4,5,6........102}
set C={1,2,3,4........101}

1
harsh jindal ·

YAAR SOUMIK I WAS GETTING EXACTLY 98

Your Answer