Jawaban Teka-teki Jembatan Königsberg
Teka-teki jembatan Königsberg tidak memiliki jawaban. Namun sebelum kamu mulai bersumpah serapah, perhatikan ini: Dalam matematika, kita bukan hanya tertarik pada jawabannya. Ketika suatu teka-teki tidak memiliki jawaban, kita perlu mempertimbangkan dua hal:
- Apakah kita kurang berusaha? Seandainya kita berusaha sedikit lebih keras, atau lebih sabar mencarinya, mungkinkah suatu hari kita akan menemukan jawabannya?
- Atau, apakah permasalahan ini memang tidak memiliki penyelesaian? Jika demikian, berarti usaha pencarian kita akan sia-sia saja.
Pertanyaan ini adalah pertanyaan meta (pertanyaan di atas permasalahannya sendiri). Ini juga merupakan wilayah studi matematika, yang disebut sebagai decidability. Pertanyaan meta ini sendiri memunculkan sebuah permasalahan baru: Bagaimana kita membedakan keduanya?
Pembuktian
Kita dapat mengkategorikan tempat menjadi tiga macam:
- Tempat berangkat
- Tempat tujuan
- Tempat singgah, yaitu tempat yang dilewati
Tempat berangkat pasti memiliki setidaknya sebuah jalur yang terhubung dengannya, yaitu jalur untuk keluar.
Tempat tujuan pasti juga memiliki setidaknya sebuah jalur yang terhubung dengannya, yaitu jalur untuk masuk.
Tempat singgah setidaknya terhubung dengan sepasang jalur. Satu untuk masuk, dan satu untuk keluar.
Dalam permasalahan yang kita bicarakan, setiap tempat dapat dilewati kembali. Yang dilarang untuk dilewati kembali adalah jalurnya, bukan tempatnya. Jadi kita boleh melewati kembali tempat singgah seperti contoh di bawah ini.
Namun karena kita hanya melewatinya, berarti setiap jalur masuk yang terhubung dengan tempat tersebut pastilah berpasangan dengan sebuah jalur keluar tanpa sisa.
Ada kemungkinan jalur pada satu tempat memiliki sisa, yaitu pada tempat berangkat dan tempat tujuan.
Selain kedua tempat tersebut, tidak boleh ada jalur yang tersisa.
Dengan demikian, kita dapat menentukan adanya jalur semacam itu dengan cara:
- Untuk masing-masing tempat, tandai setiap pasang jalur yang terhubung dengannya.
- Jika ada jalur yang tersisa, sisanya harus sepasang.
Berarti sekarang kita tinggal memasangkan jalur masuk dan jalur keluarnya.
Dengan menandai setiap pasangan jalur pada masing-masing tempat, kita bisa mendapatkan jalur sisa pada setiap tempat (berwarna merah). Karena sisanya lebih dari sepasang, berarti ini menyalahi aturan yang diberikan.
Berdasarkan gambar, kita dapat melihat bahwa ada jalur sisa (berwarna merah) yang terhubung dengan A. Demikian juga dengan B, C, dan D. Sementara berdasarkan aturan kita sebelumnya, hanya sepasang (atau dua) tempat yang boleh memiliki jalur sisa.
Dalam teka-teki ini, kita melihat bahwa terdapat jalur yang tidak berpasangan. Kesimpulannya, permasalahan ini tidak mungkin diselesaikan.