Some Problems need help

(1) is it b-a = 7

(2) total = 2012 pairs

Let |A| = r, Then A can be chosen in \binom{n}{r} ways , 1\le r \le n. Let |A\cap B|= t. then B can be chosen in \binom{r}{t}\cdot \binom{n-r}{p}\; \; , \; 1 \le t\le r , 1\le p \le n-r ways. Given A\cap B\cap C = \phi. Let |B\cap C| = k. Then C can be chosen in \binom{p}{k}\cdot 2^{r-t}\cdot 2^{n-r-p} = \binom{p}{k}\cdot 2^{n-p-t} ways. So total number of ways of choosing A,B,C is ------

\sum_{r=1}^{n}\sum_{t=1}^{r}\sum_{p=1}^{n-r}\sum_{k=1}^{p}\left (\binom{n}{r}\cdot \binom{r}{t}\cdot \binom{n-r}{p}\cdot \binom{p}{k}\cdot 2^{n-p-t}\right )

Which after computations (which only requires binomial theorem) , reduces (indeed reduces ,i have done the computation by hand) to \boxed{7^n + 5^n - 2\times 6^n}.

Notify if you need help with the computation. Basically sum up wrt. k,p,t,r in order.

Btw i know of a simpler solution...see here http://olympiads.hbcse.tifr.res.in/uploads/rmo-2004

For 2nd please how the solution!

Thanks Shubhodip for very Nice answer.

I also want some Light on that line which is mentioned by vivek

Thanks

I will show you the proof of the fact that :

if t= mq+ r, gcd(t,m) = gcd(m,r)

note that if k|a and k|b, then k≤ gcd(a,b)

Let gcd(t,m) = c

so c|t , and c|m, and you can see that c|r

since c|m and c|r, c= gcd(t,m)≤ gcd(m,r) (*)

Also gcd(m,r)|m and gcd(m,r)|r so gcd(m,r)|t

hence gcd(m,r)≤ gcd(m,t) (**)

combine (*) and (**) to get that gcd(m,r) = gcd(m,t). qed

For more see any elementary number theory book.

Here n²+ n = 1*(n²+ 1) + n-1, so by the above fact gcd(n²+ n,n²+1)= gcd(n²+1, n-1)

and n²+1 = (n+1)(n-1)+ 2

so gcd(n²+1,n-1) = gcd(n-1,2)

Now you can easily see that gcd(n-1,2) = 1, if n is even and = 2, if n is odd...

"Then C can be chosen in"

Unclear for this! Help!

Sorry for not explaining

Follow my notations

There are t elements in common between A and B. So those must not be in C. Apart from those t elements there are B has got p elements. Since you want something common in between B and C, you must choose some k elements from t. Hence C(p,k). Also nothing said about A ∩ C. A has r elements , of them B has got t. So those t are strict NO for C. But you can choose any number of elements from r-t elements. So 2^r-t. You can just as well select any number of elements from.. And there are n-r elements that are not in A. of those n-r, we have taken p for B. There are n-r-p left. You can choose any number of elements from them. so 2^n-r-p .

Now multiply them...

As for the computations, I wont be able to upload it...It's two page long...See the link to the official solution given by me...I was just looking for a direct and straightforward way to solve it...which resulted in what i posted above..

thanks shubhodip i am trying to understant it

thanks

@subho.. Thanks.

But the rmo solution is really miraculous!! Very Nice it is!