Çekilişlerde zugzwang yok

Satrançta hamle kimdeyse avantaj da ondadır. Büyük ustaların oyunlarında kimi zaman bir hamle kaybedenlerin oyundan çekildiği dahi görülür. Öte yandan, nadiren de olsa, hamle sırası kimdeyse o oyuncunun kesinlikle partiyi kaybettiği bazı oyun sonu durumları da vardır. Bunlara literatürde zugzwang denir. Bugünkü postada basit bir çekiliş probleminde hiç zugzwang olmadığını göstereceğiz. Çalışacağımız çekiliş problemi aşağıda.

Soru: Alp ve Burcu içinde $n$ adet kırmızı ve $m$ adet siyah top bulunan bir torbadan sırayla top çekiyorlar. Kırmızı topu ilk çeken oyunu kazanıyor ve eğer siyah top çekilmişse o zaman top tekrar torbaya konuyor. Oyuna Alp başladığına göre Alp'in çekilişi kazanma ihtimali nedir?

Kurguya göre $k \in \mathbb{Z}^{+}$ olmak üzere Alp birinci, üçüncü, beşinci ve genel olarak $(2k-1).$ çekilişleri yaparken Burcu da ikinci, dördüncü, altıncı ve genel olarak $2k.$ çekilişleri yapmaktadır. $A_{2k+1}$ ilk $2k$ çekilişte peşpeşe siyah top çekilirken $(2k+1).$ çekilişte kırmızı top çekildiği durumları temsil etsin. Bu durumlarda Alp çekilişi kazanmaktadır. $P(A_{1})=\frac{n}{n+m}$, $P(A_{3}) = \left(\frac{m}{n+m}\right)^{2} \frac{n}{n+m}$ ve genel olarak $P(A_{2k+1}) = \left(\frac{m}{n+m}\right)^{2k} \frac{n}{n+m}$ olur. Bütün bu ihtimalleri topladığımızda Alp'in çekilişi kazanma ihtimalini de hesaplamış oluruz.

\begin{eqnarray}\nonumber P(\text{Alp}) &:=& \sum_{k=0}^{\infty} P(A_{2k+1}) \\ \nonumber &=& \frac{n}{n+m} \sum_{k=0}^{\infty} \left(\frac{m}{n+m}\right)^{2k} = \frac{n}{n+m} \sum_{k=0}^{\infty} \left(\frac{m^{2}}{(n+m)^{2}}\right)^{k} \\ \nonumber &=& \frac{n}{n+m} \frac{1}{1 - \frac{m^{2}}{(n+m)^{2}}} \\ \nonumber &=& \frac{n+m}{n+2m} \end{eqnarray}

Alp'in kazanma ihtimali için \begin{equation*} P(\text{Alp}) = \frac{n+m}{n+2m} \gt \frac{\frac{n}{2}+m}{n+2m} = \frac{1}{2} \end{equation*} eşitsizliği her zaman geçerli olduğundan, çekilişe başlayan daha şanslıdır.

İşaret: Çekilişin anlamlı olabilmesi için $n \ll m$ olmalıdır. Bu asimptotikte $P(\text{Alp}) \sim 1/2$ olduğundan çekiliş nisbeten daha adil olmaktadır.

Ödev: $n=3$, $m=7$ olsun ama çekilen top torbaya konulmasın. Bu durumda Alp'in kazanma ihtimalini hesaplayınız.

Siklotomik polinomlarla çözülen bir geometri problemi

Soru: Birim çember üzerinde birbirine uzaklığı eşit $n$ nokta seçilsin ve daha sonra bu noktalardan biri sabit tutulup diğer $n-1$ noktaya doğru parçaları çizilsin. Doğru parçalarının uzunlukları çarpımı $n$ olur. İspatlayınız.

Bu problemi Bak ve Newman'ın beraber kaleme aldığı Kompleks Analiz kitabının ilk faslında gördüm. Çözümüne beraber bakalım. Birim çember üzerinde birbirine uzaklığı eşit $n$ nokta denildiğinde aklımıza ilk gelmesi gereken konu 1'in $n.$ dereceden kökleridir. Bu kökler \begin{equation*} z^{n}-1=0 \end{equation*} denklemini sağlar. Bu denklemin köklerinden bir tanesi ve en bariz olanı $1$'dir. Diğerlerini de $\zeta_{j} := \exp(2\pi i j / n)$ formülüyle ifade edebiliriz. Burada $i:=\sqrt{-1}$ ve $j \in \{0,\ldots,n-1\}$. $\zeta_{j}^{n}=1$ olduğundan bu niceliklerin 1'in $n.$ dereceden kökü olduğu barizdir.

Şimdi elimizdeki cebirsel ifadeyi çarpanlarına ayıralım. \begin{equation*} z^{n}-1 = (z-1) \varphi_{n}(z) \ \ \text{ve burada} \ \ \varphi_{n}(z) := z^{n-1} + z^{n-2} + \cdots + z + 1. \end{equation*} Çarpanlara ayırma işlemi sırasında zuhur eden $\varphi_{n}$ polinomlarına cebir literatüründe siklotomik polinomlar denir. Cebirin temel teoremi uyarınca siklotomik polinomları 1'in $n$. dereceden kökleri cinsinden hemen çarpanlarına ayırabiliriz. \begin{equation*} \varphi_{n}(z) = (z-\zeta_{1}) \cdots (z - \zeta_{n-1}) \end{equation*}

Gelelim problemin çözümüne. Genelliği kaybetmeden birim çember üzerinde aldığımız ilk nokta $\zeta_{0}=(1,0)$ noktası olsun. Bu noktadan herhangi bir $\zeta_{j}$ noktasına çizilen doğru parçasının uzunluğu $|\zeta_{0}-\zeta_{j}|=|1-\zeta_{j}|$ olur. Bu uzunlukların çarpımı ise \begin{equation*} |(1-\zeta_{1}) \cdots (1-\zeta_{n-1})| = |\varphi_{n}(1)| = n \end{equation*} kolayca hesaplanır.

Ödev: $|\zeta_{j+1}-\zeta_{j}|$ uzunluğunu hesaplayarak düzgün $n$-genin kenar uzunluğunu $n$ cinsinden ifade ediniz.