$n$ bir pozitif tam sayı olsun. Bir Japon üçgeni, $1+2+ \cdots +n$ adet çemberin, eşkenar üçgen şeklinde ve her $i=1,2,...,n$ için $i.$ satırda tam olarak bir tanesi kırmızı olan $i$ tane çember bulunacak şekilde yerleştirilmesiyle oluşmaktadır. Japon üçgenindeki bir ninja yolu, en tepedeki çemberden başlayıp her defasında bulunduğu çemberin hemen altındaki iki çemberden birine giderek en alt satırda biten, $n$ adet çemberden oluşan bir dizidir. Aşağıda, $n=6$ durumunda bir Japon üçgeni ve iki adet kırmızı çember içeren bir ninja yolunun örneği verilmiştir :
Her Japon üçgeninde en az $k$ adet kırmızı çember içeren bir ninja yolu bulunuyorsa, $k$ sayısının alabileceği en büyük değeri $n$ cinsinden belirleyiniz.
Her Japon üçgeninde en az $k$ adet kırmızı çember içeren bir ninja yolu bulunuyorsa, $k$ sayısının alabileceği en büyük değeri $n$ cinsinden belirleyiniz.
Çözüm:
Cevap: En büyük değer $k = \lfloor \log_2 n \rfloor + 1 = \lceil \log_2(n + 1) \rceil$ dir.
1. Adım: Üst sınır için bir örnek durum verelim.
Verilen $n$ için,
\[
N = \left\lfloor \log_2 n \right\rfloor
\quad \Rightarrow \quad 2^N \leq n < 2^{N+1}
\]
Her $a = 0, 1, \dots, N$ için,
\[
i = 2^a + b, \quad \text{(burada } 0 \leq b < 2^a)
\]
satırında $(2b + 1)$-inci çember kırmızı yapılır.
Bu durumda, her $a$ için $2^a \leq i < 2^{a+1}$ aralığındaki satırlarda yalnızca bir kırmızı çember yer alır ve her ninja yolu bu aralıktaki satırların yalnızca birini ziyaret edebilir. Bunu biraz daha açabiliriz. Şekil incelenirse $N+1$ tane kırmızı çember grubu oluşturduğumuz görülür. Açıkça, bir ninja yolu her gruptaki kırmızı çemberlerden en fazla bir tanesinden geçebilir. Dolayısıyla, bu örnek düzenlemeye göre her ninja yolu en fazla $N + 1$ kırmızı çember içerebilir.
Bu, aranan $k$ için bir üst sınır verir:
\[
k \leq N + 1 = \left\lfloor \log_2 n \right\rfloor + 1 = \lceil \log_2(n + 1) \rceil
\]
2. Adım: Alt sınır belirleyelim. Her yerleşimde en az $k$ kırmızı çember içeren bir ninja yolunun varlığını göstereceğiz.
Her $C$ çemberi için, tepe çemberinden $C$'ye kadar giden bir ninja yolunda geçen kırmızı çemberlerin maksimum sayısını $f(C)$ olarak tanımlayalım.
Ayrıca $i$-inci satırdaki tüm $f$ değerlerinin toplamı $T(i)$ ile gösterelim.
Her $i$ için $i$-inci satırdaki maksimum $f$ değerini $v(i)_{\max}$ ile gösterelim.
Dolayısıyla $f$ fonksiyonunun aldığı değerler ile ilgili kurallar şöyledir:
$\bullet$ $C$ kırmızı değilse, $f(C)$ üstteki bir veya iki komşunun $f$ değerlerinin maksimumudur.
$\bullet$ $C$ kırmızıysa, $f(C)$ üstteki maksimum değerin bir fazlasıdır.
Verilen bir kırmızı çember deseni için $f$ değerlerinin hesaplanmasını gösteren bir örnek aşağıdaki gibidir:
Bu tanımlar altında şu temel eşitsizlik sağlanır:
\[
T(i+1) \geq T(i) + v(i)_{\max} + 1.
\]
Çünkü, $v(i)_{\max}$ değerini alan çemberin altındaki iki çember de $v(i)_{\max}$ değerini alacaktır. Ayrıca, $i+1$-inci satırdaki kırmızı renkli çemberden dolayı bir çembere $+1$ eklenmesi de yapılacaktır.
3. Adım: Tümevarım ile $T(2^j) \geq j \cdot 2^j + 1$ eşitsizliğini ispatlayacağız.
İddia: Tüm $j \geq 0$ için
\[
T(2^j) \geq j \cdot 2^j + 1
\]
İspat:
Başlangıç durumu ($j=0$): Tepedeki çember kırmızı renkli olduğundan $T(1) = 1$ ve $0 \cdot 1 + 1 = 1$ olduğundan eşitlik sağlanır.
Tümevarım varsayımı: Bir $j\geq 0$ için, $T(2^j) \geq j \cdot 2^j + 1$ doğru olsun.
Bu durumda $v(2^j)_{\max} \geq j + 1$ olur. Çünkü bu satırda $2^j$ tane çember vardır. Satır toplamı bu değerden büyükse, en az bir çemberin $f$ değeri $j+1$ veya daha fazladır. Bu basitçe, aritmetik ortalaması alınan terimlerden biri, en az ortalamaya eşit veya daha büyük olmalıdır gerçeğinden kaynaklanır.
Eşitsizlik uygulanır:
\[
T(i+1) \geq T(i) + (j + 1) + 1 = T(i) + (j + 2)
\quad \text{(satırlar $i = 2^j, 2^j + 1, \dotsc, 2^{j+1} - 1$)}
\]
Bu artış toplamda $2^j$ kez gerçekleşir:
\[
T(2^{j+1}) \geq T(2^j) + 2^j \cdot (j + 2)
\geq j \cdot 2^j + 1 + 2^j \cdot (j + 2)
= (2j + 2) \cdot 2^j + 1 = (j + 1) \cdot 2^{j+1} + 1
\]
olup tümevarım tamamlanır.
Sonuç olarak, tüm kırmızı yerleşimlerinde $T(2^N) \geq N \cdot 2^N + 1$ olduğu gösterildi. Bu, en az bir ninja yolunun en az $N + 1$ kırmızı çember içerdiğini gösterir.
Üst sınırla birlikte bu alt sınır da aynı değeri verdiğinden $k = \lfloor \log_2 n \rfloor + 1 = \lceil \log_2(n + 1) \rceil$ sonucuna ulaşırız.
Kaynakça: 2023 IMO Shortlist problemleri ve çözümleri resmi kitapçığı.
1. Adım: Üst sınır için bir örnek durum verelim.
Verilen $n$ için,
\[
N = \left\lfloor \log_2 n \right\rfloor
\quad \Rightarrow \quad 2^N \leq n < 2^{N+1}
\]
Her $a = 0, 1, \dots, N$ için,
\[
i = 2^a + b, \quad \text{(burada } 0 \leq b < 2^a)
\]
satırında $(2b + 1)$-inci çember kırmızı yapılır.
Bu durumda, her $a$ için $2^a \leq i < 2^{a+1}$ aralığındaki satırlarda yalnızca bir kırmızı çember yer alır ve her ninja yolu bu aralıktaki satırların yalnızca birini ziyaret edebilir. Bunu biraz daha açabiliriz. Şekil incelenirse $N+1$ tane kırmızı çember grubu oluşturduğumuz görülür. Açıkça, bir ninja yolu her gruptaki kırmızı çemberlerden en fazla bir tanesinden geçebilir. Dolayısıyla, bu örnek düzenlemeye göre her ninja yolu en fazla $N + 1$ kırmızı çember içerebilir.
Bu, aranan $k$ için bir üst sınır verir:
\[
k \leq N + 1 = \left\lfloor \log_2 n \right\rfloor + 1 = \lceil \log_2(n + 1) \rceil
\]
2. Adım: Alt sınır belirleyelim. Her yerleşimde en az $k$ kırmızı çember içeren bir ninja yolunun varlığını göstereceğiz.
Her $C$ çemberi için, tepe çemberinden $C$'ye kadar giden bir ninja yolunda geçen kırmızı çemberlerin maksimum sayısını $f(C)$ olarak tanımlayalım.
Ayrıca $i$-inci satırdaki tüm $f$ değerlerinin toplamı $T(i)$ ile gösterelim.
Her $i$ için $i$-inci satırdaki maksimum $f$ değerini $v(i)_{\max}$ ile gösterelim.
Dolayısıyla $f$ fonksiyonunun aldığı değerler ile ilgili kurallar şöyledir:
$\bullet$ $C$ kırmızı değilse, $f(C)$ üstteki bir veya iki komşunun $f$ değerlerinin maksimumudur.
$\bullet$ $C$ kırmızıysa, $f(C)$ üstteki maksimum değerin bir fazlasıdır.
Verilen bir kırmızı çember deseni için $f$ değerlerinin hesaplanmasını gösteren bir örnek aşağıdaki gibidir:
Bu tanımlar altında şu temel eşitsizlik sağlanır:
\[
T(i+1) \geq T(i) + v(i)_{\max} + 1.
\]
Çünkü, $v(i)_{\max}$ değerini alan çemberin altındaki iki çember de $v(i)_{\max}$ değerini alacaktır. Ayrıca, $i+1$-inci satırdaki kırmızı renkli çemberden dolayı bir çembere $+1$ eklenmesi de yapılacaktır.
3. Adım: Tümevarım ile $T(2^j) \geq j \cdot 2^j + 1$ eşitsizliğini ispatlayacağız.
İddia: Tüm $j \geq 0$ için
\[
T(2^j) \geq j \cdot 2^j + 1
\]
İspat:
Başlangıç durumu ($j=0$): Tepedeki çember kırmızı renkli olduğundan $T(1) = 1$ ve $0 \cdot 1 + 1 = 1$ olduğundan eşitlik sağlanır.
Tümevarım varsayımı: Bir $j\geq 0$ için, $T(2^j) \geq j \cdot 2^j + 1$ doğru olsun.
Bu durumda $v(2^j)_{\max} \geq j + 1$ olur. Çünkü bu satırda $2^j$ tane çember vardır. Satır toplamı bu değerden büyükse, en az bir çemberin $f$ değeri $j+1$ veya daha fazladır. Bu basitçe, aritmetik ortalaması alınan terimlerden biri, en az ortalamaya eşit veya daha büyük olmalıdır gerçeğinden kaynaklanır.
Eşitsizlik uygulanır:
\[
T(i+1) \geq T(i) + (j + 1) + 1 = T(i) + (j + 2)
\quad \text{(satırlar $i = 2^j, 2^j + 1, \dotsc, 2^{j+1} - 1$)}
\]
Bu artış toplamda $2^j$ kez gerçekleşir:
\[
T(2^{j+1}) \geq T(2^j) + 2^j \cdot (j + 2)
\geq j \cdot 2^j + 1 + 2^j \cdot (j + 2)
= (2j + 2) \cdot 2^j + 1 = (j + 1) \cdot 2^{j+1} + 1
\]
olup tümevarım tamamlanır.
Sonuç olarak, tüm kırmızı yerleşimlerinde $T(2^N) \geq N \cdot 2^N + 1$ olduğu gösterildi. Bu, en az bir ninja yolunun en az $N + 1$ kırmızı çember içerdiğini gösterir.
Üst sınırla birlikte bu alt sınır da aynı değeri verdiğinden $k = \lfloor \log_2 n \rfloor + 1 = \lceil \log_2(n + 1) \rceil$ sonucuna ulaşırız.
Kaynakça: 2023 IMO Shortlist problemleri ve çözümleri resmi kitapçığı.