Some Problems need help

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

@man111- 1)Ans:49 2) Ans:2012

(2)

$\hspace{-16}Let $\mathbf{a+ib=z}$ and $\mathbf{a-ib=\bar{z}}$\\\\ Then $\mathbf{(a+ib)^{2010}=(a-ib)\Leftrightarrow z^{2010}=\bar{z}}$\\\\ $\mathbf{\mid z \mid^{2010}=\mid z\mid }$\\\\ $\mathbf{\mid z\mid .\left(\mid z \mid ^{2009}-1\right)=0}$\\\\ $\mathbf{\mid z \mid =1}$\\\\ Now Given that $\mathbf{z^{2010}=\bar{z}\Leftrightarrow z^{2011}=z.\bar{z}=\mid z\mid ^2}$\\\\ So $\mathbf{z^{2011}=1\Leftrightarrow z=1^{\frac{1}{2011}}=\cos\left(\frac{2k\pi}{2011}\right)+\sin\left(\frac{2k\pi}{2011}\right) }$\\\\ So $\mathbf{z=e^{\frac{2k\pi}{2011}}}$\\\\ Where $\mathbf{k\in \left\{0,1,2,........2010\right\}$\\\\ So Total $\mathbf{2011}$ solution\\\\ Now $\mathbf}z=0$ is also a solution \\\\ So Total $\mathbf{2011+1=2012}$ Solution

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...