Tetangga yang Buruk
TANTANGAN
Ada sekelompok orang yang tidak dapat tinggal bersebelahan di rumah-rumah di sepanjang jalan. Jika ada 10 rumah, ada berapa banyak cara sebagian dari orang-orang ini dapat tinggal di rumah-rumah tersebut sehingga tidak ada dua rumah yang bersebelahan yang dihuni oleh orang-orang ini? Anggaplah semua rumah kosong sebagai salah satu kemungkinannya.

EKSPLORASI
Ada berapa banyak cara jika terdapat 15 rumah? Temukan pola yang akan membantu Anda menghitung dengan cepat berapa banyak cara berbeda untuk jumlah rumah yang lebih besar.
Catatan
TANTANGAN & EKSPLORASI
Seperti halnya banyak teka-teki lainnya, cara terbaik untuk mempelajarinya adalah dengan mengerjakan contoh-contoh sederhana dan mencari pola. Gunakan E untuk kosong dan B untuk tetangga yang buruk.
- 1 rumah – 2 jalan: Timur atau Selatan
- 2 rumah – 3 cara: EE, BE, EB
- 3 rumah – 5 cara: EEE, BEE, EBE, EEB, BEB
- 4 rumah – 8 cara: EEEE, BEEE, EBEE, EEBE, EEEB, BEBE, BEEB, EBEB
Sepertinya angka-angka tersebut adalah deret Fibonacci. Mari kita cari alasan yang tepat mengapa demikian.
Untuk mencari jumlah cara mengisi n rumah, mulailah dengan huruf E atau B.
- Jika Anda memulai dengan huruf E, maka n-1 rumah berikutnya dapat diisi dengan mengabaikan rumah pertama tersebut.
- Jika Anda mulai dengan huruf B, maka rumah berikutnya haruslah huruf E. Setelah kedua rumah tersebut, n-2 rumah berikutnya dapat diisi dengan mengabaikan dua rumah pertama.
Oleh karena itu, jumlah cara mengisi n rumah sama dengan jumlah cara mengisi n-1 rumah ditambah jumlah cara mengisi n-2 rumah. Ini persis aturan untuk menghitung Bilangan Fibonacci. Karena kita mulai dengan 2 dan 3, aturan tersebut akan memaksa angka-angka selanjutnya menjadi sama.
Angka-angkanya akan menjadi: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 untuk sepuluh angka pertama.