n öğrenciden oluşan bir sınıfta her öğrencinin kendine özgü 1 ve n arasında bir öğrenci numarası vardır. Sınıfta her biri 1 ve n arasında farklı bir sayı ile numaralandırılmış n tane sandalye vardır. Öğrenciler sandalyelere numaralarına dikkat etmeden oturmuşlardır. Hangi öğrencinin hangi sandalyeye oturduğu n uzunluklu bir dizi ile gösterilebilir. Örneğin [2, 4, 5, 1, 3] dizisi, 2 numaralı öğrencinin 1 numaralı sandalyeye, 4 numaralı öğrencinin 2 numaralı sandalyeye, 5 numaralı öğrencinin 3 numaralı sandalyeye, 1 numaralı öğrencinin 4 numaralı sandalyeye, 3 numaralı öğrencinin ise 5 numaralı sandalyeye oturduğu durumu göstermektedir.

Öğretmen sınıfa girdiğinde öğrencilerin yanlış sandalyelere oturduklarını fark etmiş ve her öğrencinin, numarası kendi öğrenci numarası ile aynı olan sandalyeye oturmasını istemiştir. Ancak bu işlem gerçekleştirilirken her adımda sadece bir öğrenci ikilisinin sandalyelerini değiştirmesine izin verilmiştir.

Örnek: Başlangıç durumu [2, 4, 5, 1, 3] olsun. 1 ve 2 numaralı öğrenciler sandalyelerini değiştirirse durum [1, 4, 5, 2, 3] olur. Sonra 2 ve 4 numaralı öğrenciler değiştirirse [1, 2, 5, 4, 3] olur. Sonra 3 ve 5 numaralı öğrenciler değiştirirse [1, 2, 3, 4, 5] elde edilir. Böylece toplam 3 adımda bütün öğrenciler doğru yere oturmuş olur ve bu örnekte daha az adımda bunun mümkün olmadığına dikkat ediniz.

n = 10 ve başlangıç durumu [4, 9, 2, 5, 7, 6, 1, 3, 10, 8] olsun. Bütün öğrencilerin doğru sandalyeye oturması için en az kaç adım gerekir?

n = 100 öğrencili bir sınıfta bütün öğrencilerin doğru sandalyeye oturması için en fazla kaç adım gerekebilir?

n = 20 ve başlangıç durumu [4, 8, 12, 15, 20, 3, 6, 1, 17, 9, 2, 19, 5, 18, 7, 16, 10, 13, 11, 14] olsun. Bütün öğrencilerin doğru sandalyeye oturması için en az kaç adım gerekir?