Soal OSN Pertamina 2011- Babak 3 Besar Nasional

Ada $n$ orang penduduk asli di suatu pulau dimana setiap dua orang dari mereka bisa merupakan teman atau musuh. Masing-masing penduduk memakai sebuah kalung, dengan anak kalungnya masing-masing terdiri atas beberapa buah batu permata berwarna (banyaknya permata merupakan bilangan bulat tak negatif). Setiap dua orang yang berteman harus memiliki satu batu permata dengan warna sama di kalung mereka. Sedangkan dua orang yang bermusuhan memiliki susunan batu permata yang sama sekali berbeda. Tentukan banyaknya warna minimum untuk menggambarkan relasi semua warga di pulau tersebut?
Misalkan $n$ adalah bilangan bulat tidak kurang dari $3$ dan misalkan $a_1,a_2,\dots,a_n$ adalah suatu barisan bilangan bulat positif sehingga untuk $k=2,3,\dots,n$ berlaku $n(a_k+1)-(n-1)a_{k-1}=1$ . Buktikan bahwa $a_n$ tidak habis dibagi oleh $(n-1)^2$
Tunjukan bahwa untuk $x>1$ , maka $\frac{x+x^{-1}}{1} < \frac{x^2+x^{-2}}{2}<\dots<\frac{x^n+x^{-n}}{n}<\dots$
Buktikan persamaan differensial $M(t,y)+N(t,y)y=0$ mempunyai faktor integrasi $\frac{1}{M^2+N^2}$ jika $\frac{\partial M}{\partial y}=\frac{\partial N}{\partial y}$ dan $\frac{\partial M}{\partial y}=-{\frac{\partal N}{\partial t}}$