Unimodal Permutations Calculation

Merhaba Zekiye, seninle birlikte bu güzel TYT-AYT tarzı küme ve sayma sorusunu adım adım çözelim.

Soruda bizden bu kümenin elemanlarını birer kez kullanarak altı basamaklı bir sayı yazmamız isteniyor. Bu sayı, soldan sağa doğru bir rakama kadar artmalı, o rakamdan sonra ise azalmalıdır.

Bu tür dizilimlere matematikte tepe noktası olan dizilimler denir. Kümemizdeki en büyük eleman altı olduğu için, bu tepe noktası kesinlikle altı olmak zorundadır.

Neden mi? Eğer tepe noktası başka bir sayı olsaydı, örneğin beş olsaydı, altı sayısı bu tepe noktasının ya solunda ya da sağında kalacaktı. Bu durumda artan veya azalan olma kuralı bozulurdu. Dolayısıyla tepe elemanı her zaman en büyük sayı olan altıdır.

Şimdi kuralın detaylarına daha yakından bakalım. Soruda bir milyon iki yüz otuz dört bin beş yüz altmış ve altı yüz elli dört bin üç yüz yirmi bir sayılarının bu kurala uymadığı belirtilmiş.

Bunun anlamı, tepe noktası olan altının en başta veya en sonda yer alamayacağıdır. Yani, altıdan önce en az bir artan kısım ve altıdan sonra en az bir azalan kısım bulunmalıdır.

O halde sayımızı şu şekilde modelleyebiliriz. Altıdan önceki rakamların kümesine A kümesi, altıdan sonraki rakamların kümesine ise B kümesi diyelim.

Bu iki kümenin kesişimi boş küme olmalıdır ve her ikisi de boş kümeden farklı olmalıdır. Çünkü altının solunda da sağında da en az birer eleman bulunmak zorundadır.

Peki, A kümesini seçtiğimizde B kümesi ve sayıların dizilimi nasıl belirlenir? Bunu anlamak çözümün anahtarıdır.

Seçtiğimiz herhangi bir A alt kümesi için, elemanları tek bir şekilde küçükten büyüğe sıralayabiliriz. Kalan elemanlar B kümesini oluşturur ve onlar da tek bir şekilde büyükten küçüğe sıralanır.