Permasalahan 100 dan 99

September 14, 2010

Permasalahan 100 dan 99

Filed under: Brain Teaser, Logaritma, Matematika — Hendra Jaya @ 7:42 am

Problem

Mana yang lebih besar? ${100}^{99}$ atau ${99}^{100}$

Pembahasan (via Logaritma)

Pendekatan yang paling mudah adalah pendekatan melalui logaritma. Sekedar napak tilas untuk menyegarkan ingatan, penulis akan menyajikan ulang dua buah identitas pada logaritma :

$\log a^b=b.\log a$
Untuk bilangan bulat positif $a$ dan $b$ , jika diketahui $a\geq b$ , maka $\log a\geq\log b$

Sekarang, kita asumsikan bahwa ${100}^{99}>{99}^{100}$ , sehingga diharapkan $\log {100}^{99}>\log {100}^{99}$

Sesuai dengan rumus logaritma, kita memperoleh bahwa $\log {100}^{99}=99\log 100=198$ dan sebaliknya, kita juga memperoleh $\log {99}^{100}=100\log 99$

Sekarang, pertanyaannya berubah menjadi “Apakah $\log 99<1.98$ ?” Kita tidak tahu dengan pasti berapa nilai dari $\log 99$ , tetapi kita tahu dengan pasti bahwa $\log 100$ adalah 2.

Seharusnya – hanya feeling – , $\log 99$ nilainya sekitar 1.99xxx.

Yap. $\log 99$ nilainya 1.9956351945975499153 di kalkulator.

Sehingga pertidaksamaan $\log 99<1.98$ bernilai salah dan dengan demikian asumsi awal yang dibuat pun salah. Suatu kontradiksi yang mengakibatkan pernyataan yang benar adalah ${99}^{100}>{100}^{99}$

Logarithm Under My Bed

Pembahasan (via Bilangan Euler)

Jika kita misalkan $A=100^{99}$ dan $B=99^{99}$ maka kita peroleh

$\begin{array}{lll}\frac{A}{B}&=&\frac{100^{99}}{99^{99}}\\\\\frac{A}{B}&=&(\frac{100}{99})^{99}\\\\\frac{A}{B}&=&(1+\frac{1}{99})^{99}\end{array}$

Bentuk $\frac{A}{B}$ di atas sangat mirip dengan bentuk legendaris $e=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n$ .

Dengan memerhatikan bahwa $f(n)=(1+\frac{1}{n})^n$ adalah sebuah fungsi yang monoton naik dan konvergen, yakni

Monoton naik karena $f(n+1)>f(n)$

Konvergen karena $f(n+1)-f(n)>f(n+2)-f(n+1)$ . Tes konvergensi via perbandingan rasio

Selanjutnya, walaupun 99 tidak bisa dikatakan “tak terhingga”, namun bentuk di atas dapat memberi kita keyakinan bahwa

$(1+\frac{1}{99})^{99}<e<99$

atau sederhananya

$(1+\frac{1}{99})^{99}<99$

Dengan demikian $\frac{100^{99}}{99^{99}}<99$

Sebagai akibatnya $100^{99}<99^{100}$

Secara umum, kita dapat mengatakan bahwa $(n+1)^n<n^{n+1}$ berlaku untuk $n\geq 3\text{ , }n\in\mathbb{Z}$ atau dalam kelompok bilangan lain (real) pertidaksamaan berlaku dengan syarat $n>e\text{ , }n\in\mathbb{R}$ dimana $e$ adalah bilangan Euler.

Simplified Version

Pembahasan (via Binomial Newton)

Jika diketahui $0\leq a<k\leq n$ dimana $n,k,a\in\mathbb{Z}$

Kita peroleh pertidaksamaan 1:

$\begin{array}{rcll}k&>&a\\k-a&>&0\\k-a&\geq&1&\text{ karena }k-a\text{ adalah bilangan bulat}\\\frac{1}{k-a}&\leq&1\\\end{array}$

Lalu, karena $a\geq 0$ , kita peroleh pertidaksamaan 2:

$\begin{array}{rcl}a&\geq&0\\-a&\leq&0\\n-a&\leq&n\end{array}$

Dengan menggabungkan kedua pertidaksamaan, kita peroleh $\frac{n-a}{k-a}\leq n$

Selanjutnya

$\begin{array}{rcl}\frac{n-0}{k-0}&\leq&n\\\frac{n-1}{k-1}&\leq&n\\\frac{n-2}{k-2}&\leq&n\\&\ldots\\\frac{n-(k-2)}{k-(k-2)}&\leq&n\\\frac{n-(k-1)}{k-(k-1)}&\leq&n\end{array}$

Sehingga

$\begin{array}{rcll}\frac{n-0}{k-0}.\frac{n-1}{k-1}.\frac{n-2}{k-2}\ldots\frac{n-(k-2)}{k-(k-2)}.\frac{n-(k-1)}{k-(k-1)}&\leq&n^k\\\\\frac{n}{k}.\frac{n-1}{k-1}.\frac{n-2}{k-2}\ldots\frac{n-k+2}{2}.\frac{n-k+1}{1}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{k.(k-1).(k-2)\ldots 2.1}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{k!}&\leq&n^k&\text{Definisi faktorial, yaitu }k!=k.(k-1).(k-2)\ldots 3.2.1\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{1}.\frac{1}{k!}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1).(n-k).(n-k-1).(n-k-2)\ldots 2.1}{(n-k).(n-k-1).(n-k-2)\ldots 2.1}.\frac{1}{k!}&\leq&n^k&\text{Kalikan pembilang dan penyebut dengan }(n-k).(n-k-1).(n-k-2)\ldots 2.1\\\\\frac{n!}{(n-k)!}.\frac{1}{k!}&\leq&n^k&\text{Definisi faktorial}\\\\\frac{n!}{k!(n-k)!}&\leq&n^k\\\\\binom{n}{k}&\leq&n^k&\text{Definisi kombinasi }\binom{n}{k}=\frac{n!}{k!(n-k)!}\end{array}$

Dari definisi binomial Newton kita tahu bahwa $(x+1)^n=\sum_{k=0}^n\binom{n}{k}x^k$

Selanjutnya, dengan mengambil $x=n$ , kita peroleh $(n+1)^n=\sum_{k=0}^n\binom{n}{k}n^k$

Setelah dijabarkan kita peroleh $(n+1)^n=\binom{n}{0}n^0+\binom{n}{1}n^1+\binom{n}{2}n^2+\cdots+\binom{n}{n-1}n^{n-1}+\binom{n}{n}n^n$

$\begin{array}{rlrlrlrlrlclrlr}(n+1)^n&=&\binom{n}{0}n^0&+&\binom{n}{1}n^1&+&\binom{n}{2}n^2&+&\binom{n}{3}n^3&+&\cdots&+&\binom{n}{n-1}n^{n-1}&+&\binom{n}{n}n^n\\\\(n+1)^n&=&1&+&n^2&+&\binom{n}{2}n^2&+&\binom{n}{3}n^3&+&\cdots&+&\binom{n}{n-1}n^{n-1}&+&\binom{n}{n}n^n\\\\(n+1)^n&\leq&1&+&n^2&+&n^n&+&n^n&+&\cdots&+&n^n&+&n^n\end{array}$

Dengan mengambil asumsi berani, yaitu :

$n^2+1<n^n$

Kita peroleh :

$\begin{array}{llllr}(n+1)^n&\leq&(n^2+1)+(n-1).n^n&<&n^n+(n-1).n^n\\\\(n+1)^n&&&<&(1+n-1).n^n\\\\(n+1)^n&&&<&n.n^n\\\\(n+1)^n&&&<&n^{n+1}\end{array}$

Satu-satunya yang mengganjal pada aljabar pertidaksamaan di atas adalah asumsi berani kita, yaitu $n^2+1<n^n$ .

Secara intuitif jelas sekali bahwa kecepatan “terbang” fungsi kuadratik $n^2$ akan kalah jauh dibanding $n^n$ . Hal ini wajar karena “pangkat” dari fungsi kuadratik adalah konstan, yaitu 2. Hal ini mirip dengan notasi Big-O pada ilmu komputasi. Pembaca yang berlatar belakang pemrograman tentu sudah menyadari hal ini.

Lantas, pada $n$ berapa, pertidaksamaan $n^2+1<n^n$ berlaku? Pada saat $n=2$ , sisi kiri masih lebih besar dari sisi kanan, yaitu $2^2+1>2^2$ . Akan tetapi pada saat $n=3$ , sisi kiri sudah kalah (dan akan terus kalah) dari sisi kanan, yaitu $3^2+1<3^3$ .

Sehingga pertidaksamaan $(n+1)^n<n^{n+1}$ berlaku untuk $n\geq 3\text{ , }n\in\mathbb{Z}$

Pretty Heavy Stuff

Like this:

Be the first to like this post.

Komentar (6)

6 Komentar »

Oke, otak saya mulai overload

Komentar oleh ageng — Oktober 25, 2010 @ 11:52 am

Balas
- Halo.
  Makasih udah mengunjungi blog saya.
  
  Ada apa? Kenapa bisa overload?
  
  Komentar oleh Hendra Jaya — Oktober 25, 2010 @ 11:53 am
  
  Balas
Kok pake pembuktian menggunakan kontradisi segala sih? Gak langsung aja kek dibandingkan kalo mana yg lebih besar.

Lagipula mencari logaritma sendiri belum tentu cara yg mudah. Bagaimana cara kalkulator kita menghitungnya? Jangan2 pake perpangkatan juga dari definisi logaritmanya. Harusnya ditunjukkan juga cara mencari logaritma2 itu sampai ketelitian yg diperlukan yg membutuhkan kalkulasi yg lebih ringan dibandingkan perpangkatan langsung.

Komentar oleh Mauri Sombowadile — Oktober 27, 2010 @ 3:28 pm

Balas
- Terima kasih atas saran dan masukannya.
  
  Artikel menggunakan logaritma dan kontradiksi karena itu yang “terbayang” pertama kali
  Akan saya coba cari cara yang lain untuk membandingkan kedua angka-angka tersebut.
  
  Memang benar bahwa teknik menghitung logaritma sepertinya saat ini belum banyak dipelajari. Nanti saya akan coba tulis artikel tentang metode menghitung logaritma.
  
  Update : Artikel tentang teknik menghitung logaritma bisa dilihat di sini
  
  Komentar oleh Hendra Jaya — Oktober 28, 2010 @ 7:53 am
  
  Balas
Perhatikan bahwa mencari nilai logaritma sampai ketelitian tepat mungkin sama beratnya dengan menggunakan perpangkatan. Karena itu di atas kubilang “sampai ketelitian yg diperlukan.”

Komentar oleh Mauri Sombowadile — Oktober 28, 2010 @ 10:59 am

Balas
- Mungkin yang dimaksud dengan ketelitian disini adalah “angka di belakang koma” atau biasanya dikenal dengan nama Fractional Part.
  
  Teknik mencari logaritma yang saya tahu adalah menggunakan Binary Logarithm, yaitu logaritma dalam basis 2. Artikel di wikipedia, menurut saya, sudah sangat lengkap. Artikel itu menjelaskan algoritma pencariannya sampai pada ketelitian yang diinginkan plus contoh implementasi dalam Python.
  
  Untuk mencari logaritma dalam basis yang lain mungkin dapat menggunakan identitas $\qquad\log_b(x)=\frac{\log_2(x)}{\log_2(b)}$ dimana $x$ adalah angka yang ingin dihitung dan $b$ adalah basis/radix perhitungan.
  
  Komentar oleh Hendra Jaya — Oktober 29, 2010 @ 6:58 am
  
  Balas