Terdapat N kota dengan N nama berbeda. Setiap kota memiliki populasi penduduk masing-masing. Pemerintah negara tersebut pusing karena terdapat terlalu banyak kota. Pemerintah tersebut berencana menggabungkan kota-kota tersebut hingga hanya tersisa satu kota. Caranya begini. Selama masih ada 2 kota atau lebih, pemerintah memilih 2 kota sesuka dia, kemudian menggabungkan kedua kota tersebut. Nama kota yang baru tersebut ialah nama salah satu kota dari kedua kota asalnya yang memiliki jumlah penduduk lebih banyak. Apabila jumlah penduduknya sama, namanya boleh yang mana saja.
Tugas Anda pada soal ini ialah menghitung ada berapa nama kota berbeda dari kota terakhir yang mungkin terjadi dengan asumsi pemerintahnya memilih kedua kota tersebut secara acak?
-
Misalkan N = 8, dan jumlah penduduk masing-masing kota adalah 2, 50, 24, 21, 1, 9, 15, dan 5 orang. Setelah seluruh kota berhasil digabung menjadi 1 kota, ada berapa nama kota berbeda dari kota yang mungkin? {tuliskan dalam bentuk angka}
-
Misalkan N = 100, dan tiap kota diberi nomor 1 sampai 100. Jumlah penduduk di kota i adalah i*i. Ada berapa nama kota berbeda dari kota yang mungkin? {tuliskan dalam bentuk angka}
-
Jika diurutkan dari yang terkecil, jumlah penduduk masing-masing kota adalah:
1, 2, 5, 9, 15, 21, 24, 50.
Nama kota yang baru adalah nama salah satu kota yang memiliki jumlah penduduk lebih banyak atau sama dengan satunya. Jadi dipastikan bahwa nama kota terakhir bisa berdasarkan kota dengan 50 penduduk. Untuk kota yang di sebelah kirinya dapat menjadi nama yang baru jika penjumlahan penduduk dengan yang terbaris di kirinya. Semua kota memenuhi kecuali 1, 2 dan 5. Dengan demikian total kemungkinan nama kota adalah 5. -
Dengan cara yang sama:
1, 4, 9, 16, 25, 36,…
Jika diperhatikan, hanya kota dengan jumlah penduduk 1, 4 dan 9 saja yang tidak memungkinkan untuk menjadi nama terakhir, sedangkan kota 4 bisa karena kota tersebut bisa digabungkan dengan kota sebelah kirinya begitu seterusnya sampai penggabungan terakhir.Dengan demikian terdapat 97 kemungkinan nama kota.
