nivotko

Soal polinomial di OSN 2020

OSN 2020 baru saja berlangsung dan diadakan secara virtual. Senang sekali ada soal polinomial di OSN kali ini. Berikut adalah soalnya.

Soal. Misalkan $a,b,c$ bilangan real dan $p(x)=ax^2+bx+c$ . Jika $p(a)=bc, p(b)=ca$ , dan $p(c)=ab$ , buktikan bahwa

$(a-b)(b-c)(c-a)(a+b+c)=0$ .

Jawaban. Jika $a,b,c$ ada yang sama, maka $(a-b)(b-c)(c-a)=0$ sehingga persamaan yang ingin dibuktikan pasti benar. Asumsikan $a,b,c$ merupakan tiga bilangan real yang berbeda-beda.

Misalkan $q(x)=xp(x)-abc=ax^3+bx^2+cx-abc$ .

Karena $p(a)=bc$ sehingga $q(a)=ap(a)-abc=abc-abc=0$ . Dengan cara serupa, $q(b)=q(c)=0$ .

Jika $a=0$ , maka $q(x)=bx^2+cx$ . Namun ini berarti, $a,b,c$ ada yang sama. Kontradiksi dengan asumsi yang kita ambil terakhir bahwa $a,b,c$ berbeda-beda.

Asumsikan $a \ne 0$ , maka $\deg q = 3$ dan $q$ punya maksimum tiga akar. Karena $a,b,c$ berbeda-beda, maka ketiga akarnya adalah $a,b,c$ . Karena koefisien utama (koefisien dari $x^3$ ) dari $q(x)$ adalah $a$ , maka $q(x)=a(x-a)(x-b)(x-c)$ .

Membandingkan kedua representasi $q(x)$ , perhatikan bahwa

$ax^3-a(a+b+c)x^2+a(ab+bc+ca)x-a^2bc = ax^3 + bx^2 + cx - abc$ .

Jadi, diperoleh

$-a(a+b+c)=b$ … (i)

$a(ab+bc+ca)=c$ … (ii)

$-a^2bc=-abc$ … (iii)

Karena $a \ne 0$ , cukup ditunjukkan $b=0$ . Asumsikan $b \ne 0$ .

Dari persamaan (iii), $abc(a-1)=0$ . Karena $a \ne 0, b \ne 0$ , maka $c=0$ atau $a=1$ .

Jika $c=0$ , maka dari persamaan (ii), $ab = 0$ . Kontradiksi dengan $a \ne 0, b \ne 0$ .

Jika $a=1$ , maka dari persamaan (ii), $bc+b+c=c$ sehingga $b(c+1)=0$ . Jadi $b=0$ atau $c=-1$ . Karena $b \ne 0$ , maka $c=-1$ . Dari persamaan (i), karena $a=1$ dan $c=-1$ , diperoleh $-b = b$ yang mengakibatkan $b=0$ , kontradiksi lagi dengan $b \ne 0$ .

Jadi, haruslah $b = 0$ dan karena $a \ne 0$ , berlaku $a+b+c=0$ , jika $a,b,c$ semuanya berbeda-beda.

Menyimpulkan semuanya, diperoleh $(a-b)(b-c)(c-a)(a+b+c)=0$ . $\blacksquare$

Catatan: Soal yang cukup baik untuk OSN meskipun banyak “jurang jebakan” yang bisa menyesatkan peserta dari mendapatkan kesimpulan yang tepat.

An ugly bound for the harmonic series

I found the following inequality in one of my math book last night. Looks kind of scary but I think the proof is kind of cute.

Proposition. For any $n \in \mathbb{N}$ , the following inequality holds:

$\dfrac{1}{1}+\dfrac{1}{2}+\dots+\dfrac{1}{n} \ge n \left( \sqrt[n]{n+1} -1 \right)$ .

Proof.

Rearrange the terms in the inequality to

$n+\dfrac{1}{1}+\dfrac{1}{2}+\dots+\dfrac{1}{n} > n \sqrt[n]{n+1}$

$\left(1+\dfrac{1}{1}\right)+\left(1+\dfrac{1}{2}\right)+\dots+\left(1+\dfrac{1}{n}\right) > n\sqrt[n]{n+1}$ .

Applying AM-GM inequality, we obtain

$\left(1+\dfrac{1}{1}\right)+\left(1+\dfrac{1}{2}\right)+\dots+\left(1+\dfrac{1}{n}\right)$

$= \dfrac{2}{1}+ \dfrac{3}{2} + \dots + \dfrac{n+1}{n}$

$\ge n \sqrt[n]{ \dfrac{2}{1} \cdot \dfrac{3}{2} \cdot \dots \cdot \dfrac{n+1}{n}}$

$= n \sqrt[n]{n+1}$ ,

as desired. Note that clearly $\dfrac{2}{1} \ne \dfrac{n+1}{n}$ . $\blacksquare$

Many of you probably know that $1+\dfrac{1}{2}+\dots+\dfrac{1}{n}$ has $\Theta(\log n)$ asymptotic growth; this is a tight bound. If you know this, a quite natural question would be how is the inequality above compare to the $O(\log n)$ bound of the harmonic series, at least?

OK, it has a very small chance of winning against $O(\log n)$ since we already know it is of tight bound. But, here are some propositions you might be willing to check.

Proposition. There is $c>0,N>0$ such that $n(\sqrt[n]{n+1}-1) \le c \cdot \log n$ for all $n \ge N$ . (In other words, $n(\sqrt[n]{n+1}-1) = O(\log n)$ .

Moreover, can we find $c_1>0,N_1>0$ such that $c_1 \cdot \log n \le n(\sqrt[n]{n+1}-1)$ for all $n \ge N_1$ ? (In other words, is $n(\sqrt[n]{n+1}-1) = \Omega(\log n)$ as well?).

Let me know what you think in the comments below.

Ekspektasi rata-rata hasil pelemparan dadu hingga mendapatkan 6 (help?)

Misalkan kita melempar dadu terus-menerus sampai mendapatkan angka 6. Kita tahu bahwa ekspektasi banyak lemparan yang dibutuhkan adalah 6. Pertanyaan yang mau saya ajukan di sini adalah: berapa ekspektasi dari rata-rata angka yang muncul?

Tiba-tiba kepikiran aja soal ini. Karena saya hanya tahu probabilitas dasar, saya akan coba jawab pakai metode yang saya tahu. Saya mulai dengan membuat variabel acak $X$ untuk rata-rata hasil pelemparan dadu hingga dapat angka 6.

Awalnya, saya mau menyiapkan variabel acak $X_1,X_2,\dots$ yang menyatakan hasil dari pelemparan ke-1, ke-2, dan seterusnya. Kalau banyak pelemparannya adalah $k$ , tentu rata-ratanya adalah $\dfrac{X_1+X_2+\dots+X_k}{k}$ . Namun, masalahnya $k$ di sini juga merupakan variabel acak (variabel acak yang muncul sebagai indeks…). Mungkin kalau dipaksakan ya, $k=6$ (karena ekspektasi $k$ adalah $6$ berdasarkan distribusi geometrik $\text{Geo}(\frac{1}{6})$ . Jadinya, ekspektasinya harusnya $\dfrac{X_1+X_2+X_3+X_4+X_5+X_6}{6}$ dan diperoleh lagi ekspektasinya adalah $\dfrac{1}{6} \sum_{i=1}^6 \mathbb{E}[X_i] = \mathbb{E}[X_i] = 3.5$ . Tapi saya kurang bisa menerima jawaban ini….

Lalu, saya coba cari ide lain.

Oke, mungkin saya mau pertimbangkan semua kemungkinan nilai $X$ . Yang pasti rata-ratanya ga mungkin kurang dari 1, dan ga mungkin lebih dari 6. Pasti di antara 1 dan 6 (inklusif). Lalu, dengan sedikit merenung, saya tahu bahwa $X$ haruslah rasional (karena rata-ratanya bentuknya pasti bulat dibagi bulat).

Waduh, apakah semua bilangan rasional di antara 1 dan 6 mungkin jadi rata-rata hasil pelemparan? Sepertinya demikian. Misalkan $\dfrac{a}{b}$ adalah bilangan rasional dengan $a,b$ bilangan bulat positif yang memenuhi $b \le a \le 6b$ (agar nilainya di antara 1 dan 6), kita dapat ambil $k=b$ (banyak pelemparan $b$ ). Kemudian, pasti ada cara untuk menghasilkan $a$ dengan menjumlahkan $b$ buah bilangan dari 1-6 (saya asumsikan pembaca percaya hehe, tapi buktinya kayak ngisi kotak aja sih… ada $b$ kotak, masing-masing berisi maks 6 bola; pasti bisa masukkan $a$ bola ke kotak-kotak itu dengan kondisi kotaknya ga ada yang kosong dan maks berisi 6 bola masing-masing).

OK, jadi $X$ punya ruang sampel $\mathbb{Q} \cap [1,6]$ . Waduh masak saya harus pakai integral yang aneh-aneh… sampai sini dulu train of thoughts saya di subuh hari ini. Let me know kalau ada pembaca yang punya strategi lain atau ada referensi buku atau internet.