Riset

Yang ditayangkan di sini merupakan problem riset, yang bila terpecahkan bisa ditulis menjadi paper, untuk dikirimkan ke jurnal matematika.

Pengubinan Bidang dengan Persegi*

Melanjutkan artikel sebelumnya tentang pengubinan dengan persegi, ada paper menarik karangan Frederick V. Henle dan James M. Henle tentang pengubinan bidang dengan persegi berbeda ukuran, yang dipublikasikan di American Mathematical Monthly edisi Januari 2008. Yang dimaksud dengan bidang di sini adalah bidang R2 yang tak terbatas. Seperti pada pengubinan persegi dengan persegi, di sini kita juga berbicara tentang persegi-persegi yang memiliki panjang sisi bilangan asli.

Andaikan kita boleh menawar sedikit persyaratan ‘berbeda ukuran’, maka kita dapat melakukan pengubinan bidang dengan menggunakan persegi-persegi bersisi bilangan Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, …, sebagai berikut:

pengubinan-fibonacci

Pengubinan dengan Persegi Bersisi Bilangan Fibonacci [Sumber gambar: AMM, Jan 2008]

Nah, selanjutnya, bila sisi setiap persegi pada pengubinan di atas kita perbesar 120 kali, lalu kita lakukan pengubinan dengan menggunakan 24 persegi berbeda ukuran pada salah satu persegi bersisi 120 (seperti yang telah dibahas dalam artikel sebelumnya), maka kita telah melakukan pengubinan bidang dengan persegi berbeda ukuran.

Namun, Frederick dan James Henle tidak berhenti di situ. Mereka beranjak lebih jauh, dengan membahas pengubinan bidang dengan menggunakan semua persegi bersisi 1, 2, 3, 4, 5, 6, 7, …, tanpa ada yang terlewat. Bila Anda penasaran, sila baca papernya di sini. Dalam paper ini, ada beberapa problem riset yang kemungkinan besar belum terpecahkan hingga hari ini, misalnya: dapatkah kita melakukan pengubinan satu kuadran bidang dengan persegi?

*

Bandung, 22-10-2016

Batu Bata Euler dan Balok Sempurna*

Suatu Tripel Pythagoras memberikan suatu segitiga siku-siku dengan sisi-sisi bilangan bulat positif atau bilangan asli. Nah, serupa dengan itu, adakah balok dengan panjang ketiga rusuknya bilangan asli dan panjang ketiga diagonal sisinya juga bilangan asli?

Balok demikian dikenal sebagai Batu Bata Euler. Bila a, b, dan c menyatakan panjang rusuk-rusuk suatu Batu Bata Euler, maka a, b, dan c merupakan solusi sistem persamaan Diophantine:

a2 + b2 = d2

a2 + c2 = e2

b2 + c2 = f2

dengan d, e, dan f menyatakan panjang para diagonal sisinya. Jika u, v, dan w adalah Tripel Pythagoras (yang memenuhi u2 + v2 = w2), maka solusi sistem persamaan Diophantine di atas adalah

a = u|4v2 – w2|, b = v|4u2 – w2|, dan c = 4uvw

yang memberikan diagonal sisi

d = w3, e = u(4v2 + w2), dan f = v(4u2 + w2).

Sebagai contoh, untuk u = 4, v = 3, dan w = 5, kita peroleh

a = 44, b = 117, dan c = 240,

dengan

d = 125, e = 244, dan f = 267.

Terkait dengan Batu Bata Euler, ada problem mencari balok sempurna, yaitu Batu Bata Euler yang memiliki panjang diagonal ruang bilangan asli. Jadi, selain tiga persamaan Diophantine di atas, ada persamaan keempat, yaitu

a2 + b2 + c2 = g2.

Hingga hari ini, belum ada solusi yang ditemukan. Problem Balok Sempurna, yang juga dikenal sebagai Problem Batu Bata Bilangan Bulat, merupakan problem terbuka; apakah mempunyai solusi atau tidak, kita tidak tahu.

balok-sempurna

Balok Sempurna

Dengan bantuan komputer, telah diperiksa bahwa balok dengan panjang rusuk ≤ 1010 tidak dapat menjadi balok sempurna. Jadi, kalau Anda hendak mencarinya, Anda harus memeriksa balok dengan panjang rusuk > 1010.

*

Bandung, 26-09-2016

 

The 5n + 1 vs 5n + 3 Problem*

(Artikel ini sengaja saya tulis dalam bahasa Inggris, supaya dapat dibaca pula oleh mereka yang tidak bisa berbahasa Indonesia.)

We have discussed the 5n + 1 problem which has similar behavior to the 3n + 1 problem. Out of curiosity, I investigated what happens if we do 5n + 3 instead of 5n + 1, using a computer program made by Mr. Bee.

It turns out that some sequences ‘converge’ to 1 (as in the 5n + 1 problem), but some escape to infinity and the others are trapped in a loop. For examples, for n1 = 25, the sequence converges to 1; for n1 = 5, 7, 11, 13, 17, 19, 23, 29, 31, 35, 37, 41, 47, or 49 (and many others), the sequences run off to infinity; and for n1 = 43, 53, or 61 (and many others), the sequences are trapped in a loop. Below is the sequence obtained for n1 = 43.

Table1 5n+1 vs 5n+3

My curiosity went further. Knowing the behavior of the sequences in the 5n + 3 problem, I would like to find out what happens if we do 5n + 1 and 5n + 3 alternately, every time we hit a number which is not divisible by 2 or 3. For example, for n1 = 5, the sequence converges to 1. The same also occurs for n1 = 43. However, if we start with n1 = 23, then we end up with a loop, as in the following table (and the next one).

Table 2b 5n+1 vs 5n+3

Note that at Step 17, when we get 11, we do 5n + 3 and get n18 = 58 and n19 = 29. Next, we do 5n + 1 and get the following sequence (just add the step by 18), where we eventually go back to the previous Step 3.

Table 3b 5n+1 vs 5n+3

It is interesting to observe what happens if we change the order of 5n + 1 and 5n +3 operations. For example, if we start with n1 = 11, with 5n + 1 operation first, then we will get a sequence which is convergent to 1; but if we apply 5n + 3 operation first, then we will get a loop.

Table 4b 5n+1 vs 5n+3

Some loops are long, for example for n1 = 179, with 5n + 3 operation first.

Table 5a 5n+1 vs 5n+3 Table 5b 5n+1 vs 5n+3

The 5n + 1 vs 5n + 3 problem seems to have interesting behavior to investigate further. One question really bothers me: is there a sequence that runs off to infinity? If not, then the 5n + 3 operations seem to never win against the 5n + 1 operations; they always lose to or tie with the 5n + 1 operations. Is it really the case?

*

Bandung, 05-09-2016

Problem 5n + 1 Versi Kedua*

Problem 5n + 1 yang telah diperkenalkan sebelumnya mungkin memang bukan problem yang sekelas dengan Problem 3n + 1. Sebagaimana telah diungkap dalam artikel sebelumnya, Problem 5n + 1 memiliki karakteristik yang berbeda dari Problem 3n + 1. Namun, kita mungkin telah melewatkan sesuatu yang penting: mengapa kita hanya memeriksa apakah n genap (atau habis dibagi 2), sebelum kita menghitung 5n + 1.

Kita semua tahu bahwa 2, 3, dan 5, merupakan tiga bilangan prima pertama. Terkait dengan fakta ini, bagaimana bila kita menghitung 5n + 1 setelah kita memastikan bahwa n tidak habis dibagi 2 ataupun 3. Persisnya, mulai dengan suatu bilangan asli n, kita lakukan langkah-langkah berikut secara iteratif:

  • Jika n = 1, hentikan iterasi;
  • Jika n habis dibagi 2, bagilah n dengan 2;
  • Jika n kabis dibagi 3, bagilah n dengan 3;
  • Jika n tidak habis dibagi 2 ataupun 3, kalikan n dengan 5 dan tambahkan 1.
diagram-alir 5n+1

Diagram Alir 5n + 1 Versi Kedua

Berikut adalah beberapa contoh barisan bilangan yang diperoleh untuk beberapa bilangan n berbeda yang dipilih pada iterasi pertama. (Bilangan yang dicetak tebal merupakan bilangan prima, yang penting untuk diperhatikan.)

a. 5, 26, 13, 66, 33, 11, 56, 28, 14, 7, 36, 18, 9, 3, 1.

b. 17, 86, 43, 216, 108, 54, 27, 9, 3, 1.

c. 19, 96, 48, 24, 12, 6, 3, 1.

d. 23, 116, 58, 29, 146, 73, 366, 183, 61, 306, 153, 51, 17, …, 1 (seperti pada b).

e. 25, 126, 63, 21, 7, …, 1 (seperti pada a).

f. 31, 156, 78, 39, 13, …, 1 (seperti pada a).

g. 35, 176, 88, 44, 22, 11, …, 1 (seperti pada a).

h. 37, 186, 93, 31, …, 1 (seperti pada f).

i. 41, 206, 103, 516, 258, 129, 43, …, 1 (seperti pada b).

j. 47, 236, 118, 59, 296, 148, 74, 37, …, 1 (seperti pada h).

Saya belum tahu apakah setiap barisan bilangan yang diperoleh pada “Problem 5n + 1 versi kedua” ini akan berhenti di bilangan 1, seperti pada Problem 3n + 1, atau ada barisan bilangan yang siklik atau divergen, seperti pada Problem 5n + 1 versi pertama. Barangkali ada yang tertarik untuk menelitinya?

*

Bandung, 28-07-2016

Problem 3n + 1*

Mari kita bermain dengan bilangan asli. Pilih suatu bilangan asli, sebutlah n. Bila n > 1, kita lakukan operasi berikut:

  • Jika n ganjil, kalikan n dengan 3 dan tambahkan 1;
  • Jika n genap, bagilah n dengan 2.

Lakukan operasi di atas secara iteratif terhadap bilangan yang dihasilkan. Iterasi dihentikan bila kita peroleh bilangan 1.

diagram-alir 3n+1

Diagram Alir 3n + 1

Sebagai contoh, misalkan saya memilih n = 3 pada awalnya. Maka, bilangan-bilangan yang akan saya peroleh berikutnya adalah: 10, 5, 16, 8, 4, 2, 1, dan iterasi pun berhenti. Contoh lainnya, bila saya memilih n = 7 pada awalnya, maka bilangan-bilangan berikutnya adalah: 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, dan iterasi pun berhenti.

Sila Anda bermain dengan beberapa bilangan n lainnya, dan amati apa yang terjadi. Barisan bilangan yang Anda peroleh pada akhirnya berhenti di 1, ya kan?

Menurut Lothar Collatz (1910-1990), berapa pun bilangan asli n yang kita pilih pada awalnya, barisan bilangan yang diperoleh pada akhirnya akan berhenti di 1.

Tetapi, pernyataan di atas hanya merupakan suatu konjektur, yang dikenal sebagai Konjektur Collatz atau Konjektur 3n + 1, dan problem pembuktiannya (atau penyangkalannya) dikenal sebagai Problem 3n + 1. Hingga saat ini, belum ada orang yang berhasil memecahkan Problem 3n + 1. Mungkin Anda mau mencobanya?

*

Bandung, 21-07-2016

Graf dan Komplemennya

Graf adalah himpunan sejumlah titik (vertices) dan sisi (edges). Sebagai contoh, gambar berikut menyatakan sebuah graf dengan 5 titik dan 5 sisi:

graf pentagon

Dalam kehidupan sehari-hari, graf ini mungkin menyatakan hubungan pertemanan di antara 5 orang. Orang pertama berteman dengan orang kedua dan kelima, tetapi orang kedua tidak berteman dengan orang kelima, dan seterusnya.

Graf dengan 5 titik disebut sebagai graf berorde 5. Pada graf berorde 5, ada 10 sisi yang mungkin menghubungkan satu titik dengan titik lainnya. Graf berorde 5 dengan 10 sisi, seperti tampak di bawah ini, merupakan graf lengkap.

graf komplelen-2

Nah, diberikan sebuah graf, kita dapat mengamati graf komplemen-nya, yaitu graf yang bila ‘digabungkan’ dengan graf semula akan menjadi graf lengkap. Sebagai contoh, kedua graf berikut merupakan komplemen satu terhadap yang lainnya:

graf komplemen-1

Perhatikan bahwa kedua graf berorde 5 di atas ‘serupa’ atau isomorfik satu terhadap yang lainnya, karena

graf komplemen-3

Dengan perkataan lain, graf berorde 5 yang berwarna biru isomorfik dengan graf komplemennya yang berwarna merah.

Dari pengamatan awal ini, kita mempunyai problem riset yang menarik, yaitu menentukan semua graf yang isomorfik dengan graf komplemennya. Dengan hitung-hitungan sederhana, kita peroleh bahwa suatu graf akan isomorfik dengan graf komplemennya hanya jika graf tersebut memiliki orde 4k atau 4k + 1.

Jika Anda tertarik dengan problem ini, mulailah bekerja dengan graf orde 4, 5, 8, dan 9, terlebih dahulu. Tentukan semua graf berorde 4, 5, 8, dan 9, yang serupa dengan graf komplemennya. Bila Anda beruntung, Anda mungkin akan menemukan ide bagaimana mencari graf berorde lebih tinggi yang isomorfik dengan graf komplemennya.

*

Bandung, 20-05-2016

Problem 4/n*

Masih ingat “Teka-Teki Pembagian Warisan“? Dalam teka-teki tersebut ada penguraian pecahan 17/18 = ½ + 1/3 + 1/9. Pecahan 17/18 merupakan pecahan komposit, sedangkan pecahan-pecahan ½, 1/3, dan 1/9 merupakan pecahan satuan — yakni pecahan yang berbentuk 1/n, dengan n merupakan bilangan asli (termasuk 1 = 1/1). Orang Mesir Kuno sudah akrab dengan pecahan satuan, dan cenderung menyatakan pecahan komposit sebagai jumlah dari beberapa pecahan satuan.

Pada tahun 1948, Paul Erdos dan Ernst G. Straus mengemukakan sebuah konjektur (dugaan) bahwa untuk setiap n ≥ 3, bentuk 4/n dapat dinyatakan sebagai jumlah dari tiga pecahan satuan berbeda. Sebagai contoh, untuk n = 3 dan 4, kita mempunyai 4/3 = 1 + ¼ + 1/12 dan 4/4 = 1/2 + 1/3 + 1/6.

Kadang terdapat lebih daripada satu cara untuk menguraikan bentuk 4/n, seperti misalnya untuk n = 5, kita mempunyai 4/5 = ½ + ¼ + 1/20 = ½ + 1/5 + 1/10. Anda dapat mencoba menguraikan 4/6 sebagai jumlah dari tiga pecahan satuan berbeda, dengan dua cara berbeda!

Hingga saat ini, konjektur ini masih merupakan open problem (belum terbukti, apakah benar atau salah). Hasil parsial telah diperoleh, misalnya untuk n = 4k (kelipatan 4), n = 4k + 2, dan n = 4k + 3. Sebagai contoh, untuk n = 4k + 2 (dengan k > 1), kita mempunyai

Problem 4 per n

Nah, yang belum berhasil dibuktikan adalah kasus n = 4k + 1. Untuk k ganjil, tulis k = 2m + 1, bentuk 4/(8m + 5) dapat diuraikan sebagai jumlah dari tiga pecahan satuan berbeda (sila coba!). Jadi, yang tersisa adalah kasus n = 4k + 1 dengan k genap, yang setara dengan kasus n = 8m + 1. Bila Anda dapat membuktikannya, Anda akan terkenal di dunia!

Tentu saja Anda dapat juga berusaha menyangkal konjektur ini. Walau demikian, dengan bantuan komputer, konjektur ini telah diperiksa kebenarannya hingga n = 1014. Jadi, bila Anda hendak mencari contoh penyangkal, Anda harus menjajaki nilai n > 1014.

Sila tengok Erdos-Straus Conjecture bila Anda tertarik untuk menjajal problem 4/n ini. Kabar-kabari saya bila Anda berhasil membuktikan konjektur ini.

*

Bandung, 21-04-2016