k adet n-gen

[ahmedsyldz]

k adet konveks n-gen bir düzlemi en fazla kaç bölgeye ayırabilir? (Örneğin 2 adet üçgen bir düzlemi en fazla 8 bölgeye ayırabilir.)

[alpercay]

Öncelikle $2$ adet $k$-gen için düşünürsek bu  $k$-genlerin her bir kenarının diğer $k$-genin her bir kenarını en çok $2$ noktada kestiğini (konveks çokgenin iç bölgesine girerken ve çıkarken) gözlemleyebiliriz. Buna göre toplam kesişme noktası sayısı $2k$ olmalıdır. Şimdi $n$ tane $k$-gen alırsak toplam kesişme noktası sayısı $2k\cdot C(n,2)=kn(n-1)$ olur. Bu kesişme noktaları, oluşan düzlemsel graf için yeni köşe noktaları anlamına gelir. Yani başlangıçta toplamda $nk$ köşe varken çokgenlerin kesiştirilmeleri sonucunda toplam köşe sayısı $V=nk+kn(n-1)$ olur. Burada önemli bir gözlem de her bir kesim noktasının grafa $2$ yeni kenar daha eklediğini görmek. Bu durumda başlangıçta $nk$ kenar varken son durumdaki kenar sayısı $E=nk+2\cdot kn(n-1)$ olmalı. Şimdi Euler formülünü çalıştırırsak oluşan bölge sayısı $$V-E+F=2$$  $$nk+kn(n-1)-nk-2kn(n-1)+F=2$$   $$F=2+kn(n-1)=2+2k\cdot C(n,2)$$ olarak bulunur.

Not: Çözüm n adet k-gen için verildi. Soruda k adet n gen için sorulmuş; sonradan farkettim. Bu durumda yanıt $F=2+nk(k-1)$ olur.

[ahmedsyldz]

Başka bir çözüm:
Öncelikle hiçbir kenarı çakışık olmayan iki konveks $n$-gen birbiriyle en fazla $2n$ noktada kesişebilir (Her kenarın karşısında bir köşenin bulunduğu durum). Şimdi $k$ adet $n$-gen ile bir düzlemin en fazla kaç bölgeye ayrılabileceğini veren bir $F(n, k)$ fonksiyonu oluşturalım.
$F(n, m)$'i bildiğimizi varsayıp $F(n, m+1)$'i inceleyelim. $m+1.$ $n$-gen kendinden önceki $n$-genlerin hepsini en fazla $2nm$ noktada kesebilir ve kestiği her noktadan sonra geçtiği bölgeyi ikiye ayıracağından 1 adet bölge artışı olur. Yani:
$F(n, m+1) = F(n, m) + 2nm$ olur ve
$F(n, 2) - F(n, 1) = 2n.1$
$F(n, 3) - F(n, 2) = 2n.2$
$\vdots$
$F(n,k) - F(n, k-1) = 2n.(k-1)$
Teleskobik toplamından ($F(n, 1) = 2$ olduğundan) $F(n, k) = nk(k-1) + 2$ gelir.