IMO 2019 Problem 4

After having the access to the problems of this year’s IMO, I skipped question three for a while and did problem 4 and 5 instead. I wish that I will have more time to think more thoroughly about question 3 and 6 in the future, and I promise to definitely share my thoughts about the solutions in my blog later.

Now, let’s talk about this year’s problem 4. This is supposed to be the easiest problem for the second exam.

I think it is quite easy for IMO standard. It can be solved using well-known methods in number theory. Unfortunately, my solution used a pretty heavy facts, namely Bertrand’s postulate (which is actually a theorem now). Bertrand’s postulate states that for any integer n>1, there exists a prime number p such that n<p<2n. I think that this is kind of cheating, but this will easily crack the problem. Also, because of this solution (which is actually a very biased and narrow perspective), I do not really like the problem, but I hope there must be a better and more elegant solution. I like the problem statement, though.

My solution to IMO 2019 Problem 4 can be downloaded here: pdf.

IMO 2019 Problem 2

I am very happy that I can still solve a supposedly medium problem in IMO for this year.

The second problem this year is a geometry problem. Usually, I use complex numbers to solve geometry problem in real contest. Now that I have more time to sit, relax, and think about the problem, I try to solve it using a nicer argument which involves less algebra and more geometric argument such as angle chasing and some properties about circles. I was not very good at using these methods usually but I think my skill is getting better since I taught a senior high school student this year for preparing him for a national level contest.

In my opinion, second problem of this year’s edition of IMO is quite easy once you understand how to draw the diagram. By drawing the diagram, I mean, knowing how to construct the points (and other geometric objects) geometrically such that the properties required are satisfied.

I wrote up not only the solution but also the train of thoughts in my solution. I hope that the interested readers will enjoy. Please be cautious that my solution is in bahasa Indonesia. Download below.

IMO 2019 Problem 2: pdf

IMO 2019 Problem 1

International Mathematical Olympiad is an annual event which invites young students from all over the world to solve 6 challenging and fresh problems in mathematics in two 4.5 hours exam. Some field medalists and top mathematicians took part in this competition in their youth.

I wrote up a solution to the first problem at International Mathematical Olympiad 2019 which was held this week. This year’s first problem is about functional equation. The quest is to find all possible mappings from a set of objects to another set of objects (in this case, from the set of integers to the set of integers) that satisfies a certain requirement (in this case an equation).

Usually, the first problem in this contest can solved using a good use of standard technique. If you get used to olympiad style problem, you should not find any difficulty in solving it (as Feynman said, you just get used to it 🙂 ).

I wrote the solution in Bahasa Indonesia and is downloadable below. Good luck to Indonesian team and all young mathematicians in the world.

Solution to IMO 2019 Problem 1 (in Bahasa Indonesia): pdf

Sketsa fungsi f(x) = x^{x^{x^{x^…}}}

Saya iseng-iseng membaca buku Information Theory-nya MacKay dan ketemu soal ini. Tidak ada hubungannya sama teori informasi, hanya saja berhubungan dengan fungsi entropi Shannon p \log \frac{1}{p}.

Misalkan f adalah fungsi yang didefinisikan dengan rumus

f(x)=x^{x^{x^{x^{x^{\dots}}}}}.

Bagaimana grafik y=f(x)? Apakah kita bisa men-sketsanya?

Petunjuk yang disediakan bukunya cukup cerdik, yaitu dengan melakukan manipulasi terlebih dahulu y=x^y kemudian menyatakan x dalam y. Kita peroleh \ln y = y \cdot \ln x. Kita asumsikan x>0 dan y>0. Dari sini, diperoleh \ln x = \dfrac{\ln y}{y} sehingga diperoleh x = y^{1/y}.

Nah, kita bisa mencoba terlebih dahulu mensketsa grafik y=x^{1/x}. Kalau ini bisa digambarkan, maka grafik x=y^{1/y} dapat diperoleh hanya dengan merotasi bidang-xy kita (karena (x,y) pada grafik awal dipandang sebagai (y,x) pada grafik yang ingin didapatkan).

Bagaimana grafik y=x^{1/x}?

Untuk 0<x \le 1, grafiknya adalah sebagai berikut:

Grafik y=x^{1/x} untuk 0<x<1. Diambil dari WolframAlpha.

Untuk x>1, grafiknya adalah sebagai berikut:

Grafik y=x^{1/x} untuk x>1. Diambil dari WolframAlpha.

Mudah diverifikasi bahwa untuk x \rightarrow \infty, nilai x^{1/x} >1 dan x^{1/x} \rightarrow 1 meskipun secara sangat lambat. Ini berarti, jika kita transpose grafik di atas, grafiknya tidak berbentuk grafik fungsi lagi. 😦 Mungkin ini juga menjelaskan mengapa x^{x^{x^{\dots}}} tidak konvergen untuk x>1.

Bagaimana dengan f(x)=x^{x^{x^{\dots}}} untuk 0<x<1? Grafiknya harusnya seperti grafik pertama namun dengan menganggap sumbu-x sebagai sumbu-y dan sumbu-y sebagai sumbu-x. 🙂

x^x = 2

Di ujian tengah semester kuliah yang saya ajar semester ini, saya meminta mahasiswa mencari bilangan riil x yang memenuhi x^x = 2, yaitu bilangan apakah yang jika dipangkatkan dengan dirinya sendiri akan memberikan nilai 2?

Persamaan ini dapat ditulis sebagai f(x)=0 dengan f(x)=x^x-2. Mudah dicek bahwa f(x) kontinu untuk x>0 (dan cukup chaotic untuk x \leq 0).

Selain itu, f(1)=1^1-2=-1 dan f(2)=2^2-2=2 sehingga pasti ada suatu nilai x \in [1,2] yang memenuhi f(x)=0 berdasarkan Intermediate Value Theorem. (Dengan analisis lebih lanjut, kita dapat tunjukkan bahwa nilai di interval tersebut adalah satu-satunya akar f(x)=0, dengan menunjukkan bahwa f(x)=x^x-2 monoton naik tegas).

Dari plot, sepertinya x yang memenuhi x^x=2 bernilai sekitar 1.55. Jika kita ingin mendapatkan nilai yang lebih presisi, kita bisa menggunakan metode Bisection, Newton, Secant, dll. Di sini saya akan menggunakan metode yang konvergensinya cukup cepat, yaitu metode Newton yang konvergensinya kuadratik. Rumus iterasi untuk menyelesaikan persamaan non-linear f(x)=x^x-2=0 adalah

x_{k+1}=x_k - \frac{x_k^{x_k}-2}{x_k(1+\ln (x_k))}

dengan tebakan awal x_0=1.55. Berikut adalah kode yang saya gunakan untuk iterasi.

function newton1d(f, df, x) %Metode Newton untuk menyelesaikan persamaan f=0 %dengan tebakan awal x dan fungsi derivatif df TOL = 0.5*10^(-10); backward_error = f(x); while abs(backward_error)>TOL x = x – f(x)/df(x) backward_error = f(x) endwhile endfunction

Dan berikut adalah implementasi fungsi f(x)=x^x-2 dan f'(x)=x^x(1+\ln(x)).

function out = selfpower(x) out = x^x; endfunction function out = dselfpower(x) out = (x^x)*(1+log(x)); endfunction

Setelah menjalankan algoritma Newton ternyata kita akan mendapatkan nilai x yang backward error-nya kurang dari \frac{1}{2} \cdot 10^{-10} hanya dengan 3 iterasi saja.

>> newton1d(@selfpower, @dselfpower, 1.55) x = 1.559698156643721 backward_error = 2.533380326248391e-04 x = 1.559610476721754 backward_error = 2.097143347867814e-08 x = 1.559610469462369 backward_error = 0

Perhatikan bahwa jika kita ambil lima angka penting c = 1.55961, maka diperoleh c^c = 1.999998643783822. Tidak sesempurna yang terlihat, namun dapat dilihat bahwa nilainya cukup c^c tersebut sangat dekat dengan 2.

[Olimpiade] Putnam 2016 B1

Sudah lama sekali saya tidak mengerjakan soal olimpiade matematika. Tapi saya akhir-akhir lebih suka melihat soal lomba tingkat kuliah karena soalnya bagi saya lebih mudah untuk dijadikan motivasi untuk memahami teori baru di matematika. Kali ini soal yang saya bahas adalah soal William Lowell Putnam Competition tahun 2016 yang diadakan di Amerika Serikat. Soalnya tidak sulit dan dapat diselesaikan dengan konsep-konsep yang dipelajari di kuliah Kalkulus 2 di kampus saya, misalnya.

Soal. Barisan \{x_n\}_{n \ge 1} didefinisikan dengan x_1 = 1 dan untuk setiap n \ge 1, berlaku

x_{n+1} = \ln \left( e^{x_n} - x_n \right).

Tunjukkan bahwa deret x_1 + x_2 + \dots konvergen dan tentukan hasil jumlahnya.

Solusi. Pertama, kita buktikan terlebih dahulu bahwa x_n>0 untuk setiap n. Kita buktikan dengan induksi. Untuk n=1, jelas benar, karena 1>0. Asumsikan benar untuk suatu n=k. Maka e^{x_k} - x_k >1 karena untuk setiap x>0, berlaku e^x > 1+x (bisa dilihat dari ekspansi Taylor). Dengan demikian, x_{k+1} = \ln \left(e^{x_k}-x_k \right) > 0. Terbukti.

Karena x_1,x_2,\dots positif, maka deret parsial S_k = x_1 + x_2 + \dots + x_k naik tegas sehingga untuk membuktikan bahwa S_k konvergen, cukup ditunjukkan bahwa S_k terbatas di atas. Untuk membuktikan ini, kita gunakan sifat bahwa

e^{x_{n+1}} = e^{\ln (e^{x_n}-x_n)} = e^{x_n}-x_n
x_n = e^{x_n} - e^{x_{n+1}}.

Dengan menggunakan sifat teleskop, kita dapat tunjukkan bahwa S_k = x_1+x_2+ \dots +x_k = e^{x_1} - e^{x_{k+1}} untuk setiap k \ge 1. Dengan demikian, karena x_{k+1}>0 untuk setiap n, maka S_k< e^{x_1}- e^0 = e-1 untuk setiap k. Karena S_k terbatas di atas, maka deret x_1+x_2+\dots konvergen.

Karena deretnya konvergen, haruslah \lim x_n = 0. Oleh karena itu, \lim_{n \rightarrow \infty} S_k = \lim_{n \rightarrow \infty} e^{x_1}-e^{x_{k+1}} = e^1 - e^0 = e-1.

Terbukti bahwa x_1 + x_2 + \dots konvergen dan hasil jumlahnya adalah e-1. \blacksquare

Persamaan diferensial dan dikejar dinosaurus

Misalkan posisi Anda pada waktu t pada bidang-xy adalah (x(t),y(t)) dengan x(0)=y(0)=0. Seekor dinosaurus awalnya berada pada titik (x_0,y_0) berlari dengan kecepatan v dengan arah lari selalu mengikuti arah Anda bergerak. Bagaimanakah bentuk lintasan yang dilalui oleh dinosaurus ini?

Kita dapat menggunakan persamaan diferensial untuk permasalahan ini. Misalkan posisi dinosaurus ini pada waktu t adalah (x_d(t),y_d(t)). Arah gerak dinosaurus ini pada waktu t adalah garis singgung lintasannya pada waktu t, yaitu \left( \begin{array}{c} x_d'(t) \\ y_d'(t) \end{array} \right). Karena salah satu syaratnya adalah ia bergerak mengikuti Anda, maka vektor ini harus proposional dengan \left( \begin{array}{c} x(t)-x_d(t) \\ y(t) - y_d(t) \end{array} \right). Jadi, kita perlu mencari konstanta \lambda, sehingga

\left( \begin{array}{c} x_d'(t) \\ y_d'(t) \end{array} \right) = \lambda \left( \begin{array}{c} x(t)-x_d(t) \\ y(t) - y_d(t) \end{array} \right) . (*)

Bagaimana cara menentukan \lambda? Kita dapat menentukan \lambda dengan menggunakan informasi yang belum digunakan yaitu kecepatan berlari dinosaurus yaitu suatu konstanta v (tanpa informasi ini, maka informasi yang kita dapatkan tidak cukup lengkap untuk bisa menentukan nilai \lambda). Perhatikan bahwa kecepatan berlari dinosaurus yang mengikuti lintasan (x(t),y(t)) adalah \sqrt{x'(t)^2 + y'(t)}. Jadi, kita menginginkan agar v=\sqrt{x'(t)^2 + y'(t)^2}. Ruas kanan dari persamaan terakhir pada dasarnya adalah norma dari vektor \left( \begin{array}{c} x_d'(t) \\ y_d'(t) \end{array} \right), jadi kita dapat menghitung \lambda dengan menghitung norma dari vektor di masing-masing ruas dari persamaan (*). Dari sini, kita akan memperoleh v = \lambda \sqrt{(x(t)-x_d(t))^2 + (y(t)-y_d(t))^2} sehingga kita peroleh

\displaystyle \lambda =\frac{v}{\sqrt{(x(t)-x_d(t))^2 + (y(t)-y_d(t))^2}}.

Jadi, untuk menentukan lintasan yang dibentuk oleh dinosaurus, kita dapat menyelesaikan sistem persamaan diferensial berikut:

\displaystyle \frac{d}{dt}x(t) = v \frac{x(t) - x_d(t)}{\sqrt{(x(t)-x_d(t))^2 + (y(t)-y_d(t))^2}}

\displaystyle \frac{d}{dt}y(t) = v \frac{y(t) - y_d(t)}{\sqrt{(x(t)-x_d(t))^2 + (y(t)-y_d(t))^2}}.

Sekarang, dengan senang hati, kita dapat melakukan simulasi pergerakannya dengan menggunakan metode numerik untuk persamaan diferensial, misalnya dengan metode Euler. Saya mencoba mengimplementasikannya dengan MATLAB / Octave berikut.

function [zxo, zyo] = onestepeuler(px, py, zxi, zyi, zv, t, h)
%Implemtasi satu langkah metode Euler untuk menyelesaikan persamaan diferensial
%px : x(t)
%py : y(t)
%zxi : x_d(t)
%zyi : y_d(t)
%zv : v
%t : t
%h : besar langkah metode Euler
  n = norm([px-zxi; py - zyi]);
  zxo = zxi + h * zv * (px - zxi)/n;
  zyo = zyi + h * zv * (py - zyi)/n;
endfunction
function simulate(x, y, pxi, pyi, zxi, zyi, zv)
%Mensimulasikan pergerakan orang dan dinosaurus
%x: function handle untuk pergerakan orang x(t)
%y: function handle untuk pergerakan orang y(t)
%(pxi, pyi): posisi inisial orang
%(zxi,zxyi): posisi inisial dinosaurus
%zv: v
  h = 0.01;
  n = 20/h;
  t = 0;
  zx = zeros(n,1);
  zy = zeros(n,1);
  px = zeros(n,1);
  py = zeros(n,1);
  px(1) = pxi;
  py(1) = pyi;
  zx(1) = zxi;
  zy(1) = zyi;
  for i=1:n-1
    pxi = px(i);
    pyi = py(i);
    zxi = zx(i);
    zyi = zy(i);
    [zxo, zyo] = onestepeuler(pxi,pyi,zxi,zyi,zv, t, h);
    zx(i+1) = zxo;
    zy(i+1) = zyo;
    t = t+h;
    px(i+1) = x(t);
    py(i+1) = y(t);
  endfor
  plot(px, py); 
  hold on;
  plot(zx, zy);
endfunction

Berikut adalah hasil simulasinya. Misalnya orang pada posisi t berada pada posisi (t,t) (jadi, x(t)=t, y(t)=t) untuk 0 \le t \le 10. Ada lima dinosaurus yang awalnya berada pada posisi awal (-10,10) namun kecepatanya berbeda-beda yaitu 0.5, 1, 1.5, 2, 2.5, dan 3.

Lintasan orang merupakan garis lurus tebal yang dimulai dari (0,0) dan lintasan masing-masing dinosaurus dengan berbagai kecepatan adalah lima kurva yang beranjak dari titik (10,-10). Perhatikan bahwa dinosaurus yang kecepatannya 2 belum dapat menangkap Anda hingga detik t=10, namun dinosaurus yang kecepatannya 2.5 bisa.

Ini terinspirasi dari permasalahan berikut di XKCD.

XKCD Webcomic - Substitute

Mungkin lain waktu saya akan bahas soal ini.