Gambar di bawah ini menunjukkan keramik bernomor 1 sampai

32 cara

Pembahasan

Untuk mencari cara seseorang dapat berjalan dari keramik nomor 1 sampai keramik nomor 7 dengan syarat nomor keramik yang dilewati harus lebih besar dari nomor keramik sebelumnya, kita dapat memikirkan ini sebagai masalah kombinasi atau jalur. 

Bayangkan setiap keramik sebagai sebuah titik. Seseorang harus bergerak dari titik 1 ke titik 7, hanya bergerak maju (ke nomor yang lebih besar). Ini berarti kita perlu memilih langkah-langkah di antara keramik yang ada. 

Urutan keramik adalah 1, 2, 3, 4, 5, 6, 7. Untuk bergerak dari 1 ke 7, kita harus melewati beberapa keramik di antaranya. Ini seperti masalah memilih subset dari keramik yang akan dikunjungi, di mana urutan sudah ditentukan (menaik). 

Cara lain untuk memahaminya adalah sebagai berikut: Dari keramik 1, kita bisa melangkah ke 2, 3, 4, 5, 6, atau 7. Jika kita melangkah ke 2, maka dari 2 kita bisa melangkah ke 3, 4, 5, 6, atau 7, dan seterusnya. 

Ini adalah masalah menghitung jumlah jalur unik dalam graf yang berarah asiklik (DAG), di mana setiap simpul terhubung ke simpul dengan nomor yang lebih besar. 

Misalkan N(k) adalah jumlah cara untuk mencapai keramik nomor k.
N(1) = 1 (kita mulai di sini)
N(2) = N(1) = 1 (hanya bisa dari 1)
N(3) = N(1) + N(2) = 1 + 1 = 2 (dari 1 atau dari 2)
N(4) = N(1) + N(2) + N(3) = 1 + 1 + 2 = 4 (dari 1, 2, atau 3)
N(5) = N(1) + N(2) + N(3) + N(4) = 1 + 1 + 2 + 4 = 8 (dari 1, 2, 3, atau 4)
N(6) = N(1) + N(2) + N(3) + N(4) + N(5) = 1 + 1 + 2 + 4 + 8 = 16 (dari 1, 2, 3, 4, atau 5)
N(7) = N(1) + N(2) + N(3) + N(4) + N(5) + N(6) = 1 + 1 + 2 + 4 + 8 + 16 = 32 (dari 1, 2, 3, 4, 5, atau 6)

Ini adalah pola barisan geometri 2^(n-1) di mana n adalah nomor keramik. Jadi, untuk keramik ke-7, jumlah cara adalah 2^(7-1) = 2^6 = 64. 

Namun, ada cara yang lebih sederhana untuk memahaminya. Setiap langkah yang kita ambil adalah sebuah keputusan: apakah kita akan mengunjungi keramik berikutnya atau melompatinya. 

Ini sama dengan memilih subset dari keramik {2, 3, 4, 5, 6} untuk dikunjungi sebelum mencapai 7, setelah dari 1. 

Mari kita pikirkan ini sebagai membuat keputusan di setiap keramik dari 1 hingga 6: apakah kita akan melompat ke keramik 7 dari sini, atau kita akan mengunjungi keramik berikutnya? 

Alternatifnya, ini adalah masalah menghitung subkumpulan dari {2, 3, 4, 5, 6} untuk dikunjungi. Jika kita mengunjungi subset tertentu, kita akan berjalan dari 1 ke elemen terkecil dalam subset, lalu ke elemen berikutnya dalam urutan, dan terakhir ke 7. 

Misalnya:
1 -> 7 (subset kosong dari {2,3,4,5,6})
1 -> 2 -> 7
1 -> 3 -> 7
1 -> 2 -> 3 -> 7

Jumlah total subset dari himpunan dengan n elemen adalah 2^n. Himpunan {2, 3, 4, 5, 6} memiliki 5 elemen. Jadi, jumlah subset adalah 2^5 = 32. 

Setiap subset ini, bersama dengan 1 dan 7, mendefinisikan sebuah jalur yang valid. 

Contoh:
Subset {2, 4} dari {2, 3, 4, 5, 6} mendefinisikan jalur 1 -> 2 -> 4 -> 7.
Subset {} mendefinisikan jalur 1 -> 7.
Subset {2, 3, 4, 5, 6} mendefinisikan jalur 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Jadi, ada 32 cara seseorang dapat berjalan dari keramik nomor 1 sampai keramik nomor 7 dengan syarat nomor keramik yang akan dilewati harus lebih besar dari nomor keramik sebelumnya.