Seratus sel

[wu :: forums] Terdapat 100 sel yang membentuk lingkaran, dan dalam keadaan tertutup. Setiap sel diberi nomor 1 sampai 100. Seorang tahanan berlari sebanyak 100 putaran. Pada putaran ke-, ia membuka setiap pintu kelipatan yang tertutup, dan menutup yang terbuka. Berapa pintu yang terbuka setelah 100 putaran?

Solusi
Jika suatu bilangan memiliki faktor, yaitu , , , maka tahanan itu membuka atau menutupnya pada putaran ke , , . Maka setelah 100 putaran, pintu yang nomornya memiliki banyak faktor ganjil akan terbuka, sedangkan yang memiliki faktor genap akan tertutup. Jika suatu bilangan memiliki faktor , maka bilangan itu memiliki faktor lain . Maka setiap bilangan memiliki faktor bilangan genap, kecuali atau , yang mengakibatkan adalah bilangan kuadrat. Jadi, hanya bilangan kuadrat yang memiliki banyak faktor ganjil. Maka, pintu yang terbuka adalah yang bernomor bilangan kuadrat, yaitu 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. Ada 10 pintu yang terbuka.