29 Ekim 2018 Pazartesi

Yaşasın, bir Putnam sorusu da ben çözdüm!

Kısaca Putnam namıyla maruf William Lowell Putnam Matematik Müsabakası ABD'de üniversite düzeyindeki öğrencilerin katıldığı bir matematik yarışması. Bu köklü organizasyon özellikle son yıllarda sorularının zorluğu yüzünden çoğu yarışmacının kalem oynatamamasıyla meşhur. Biz faniler eğer kendimizi mutlu hissetmek istersek ara sıra eski Putnamlar'a bakıp bir miktar teselli bulabiliriz. İşte aşağıda o çözülebilir ve benim polinomlarla ilgili olduğu için hoşuma giden bir soru var. Çözümümü de bu postada sizlerle paylaşmak istiyorum.

Soru: $n$ pozitif bir tamsayı, $P$ ise katsayıları gerçel bir polinom olsun. $x^{n} - (1/x^{n}) = P(x-(1/x)) \iff n \equiv 1 \ ({\rm mod} \ 2)$ olduğunu ispatlayınız.
Yirminci William Lowell Putnam Matematik Müsabakası, 21 Kasım 1959, Sabah Oturumu, Soru: 1

Çözüm: Öncelikle $x^{n} - (1/x^{n}) = P(x - (1/x))$ eşitliğinin geçerli olabilmesi için $P$ polimonunun derecesinin tam olarak $n$ olması gerektiğini gözleyelim. Böylece polinomun baş katsayısının da 1 olmak zorunda olduğu tebarüz eder. İspatta takip edeceğimiz strateji ilgili polinomu kurmak olacak. Söz konusu monik polinom en genel haliyle \begin{equation*} P(z) := z^{n} + a_{n-1}z^{n-1} + \cdots + a_{1}z + a_{0} \end{equation*} denklemiyle verilir ve problemin çözümü $a_{0},\ldots,a_{n-1}$ katsayılarının nasıl bulunacağına dair bir algoritma inşa etmekten veyahut böylesi bir algoritmanın bulunamayacağını göstermekten ibarettir.

İlkin $n$ yerine $2n$ koyalım. O zaman $P$ polinomunun önde giden teriminden binom teoremi uyarınca aşağıdaki ifadeler gelecektir. \begin{equation*} \left( x - \frac{1}{x}\right)^{2n} = x^{2n} - 2n x^{2n-2} + \cdots + \frac{1}{x^{2n}} \end{equation*} Farkındaysanız son terimin işareti ($+$) yanlış çıktı! Biz ($-$) olmasını tercih ederdik zira polinomda geri kalan terimlerin dereceleri $2n$'den küçük olduğu için başka bir terimde de $1/x^{2n}$ ifadesini üretip bu yanlış işareti $a_{k}$ katsayılarını seçerek düzeltmek imkansız. Bu yüzden $n$ çift ise teoremde bahsedilen polinomu kuramıyoruz.

$n$ tek olsun. $n=1$ için ilgili polinomun kolaylıkla $P_{1}(z)=z$ formunda kurulabildiğini gözleyiniz. Teoremin $P_{3},\ldots,P_{2n-1}$ için geçerli olduğunu ve bu polinomların mevcut olduklarını varsayalım. Şimdi, öncelikle binom teoremi ve ardından yeniden gruplamayla aşağıdaki manupulasyonları gerçekleştireceğiz. \begin{eqnarray} \nonumber \left( x - \frac{1}{x} \right)^{2n+1} &=& \sum_{j=0}^{2n+1} {2n+1 \choose j} (-1)^{j}x^{2n+1-2j} \\ \nonumber &=& x^{2n+1} - \frac{1}{x^{2n+1}} + \sum_{j=1}^{2n} {2n+1 \choose j} (-1)^{j}x^{2n+1-2j} \\ \nonumber &=& x^{2n+1} - \frac{1}{x^{2n+1}} + \sum_{j=1}^{n} {2n+1 \choose j} (-1)^{j} \left( x^{2(n-j)+1} - \frac{1}{x^{2(n-j)+1}}\right) \end{eqnarray} $\zeta := x - x^{-1}$ tanımlarsak, o zaman yukarıdaki ifade \begin{equation*} x^{2n+1} - \frac{1}{x^{2n+1}} = \zeta^{2n+1} - \sum_{j=1}^{n} {2n+1 \choose j} (-1)^{j} P_{2(n-j)+1} (\zeta) =: P_{2n+1}(\zeta) \end{equation*} şeklinde yeniden düzenlenir ve tümevarım uyarınca ispat tamamlanmış olur. QED

Uygulama: Daha önceden de not ettiğimiz üzere $P_{1}(z)=z$ olduğu barizdir. Yukarıda kurduğumuz algoritma uyarınca \begin{equation*} P_{3}(z) = z^{3} - \sum_{j=1}^{1} {3 \choose j} (-1)^{j} P_{2(1-j)+1}(z) = z^{3} + 3 P_{1}(z) = z^{3} + 3z \end{equation*} olur. Dizideki bir sonraki polinom ise ispatta türettiğimiz formülde $n=2$ koymakla elde edilebilir. \begin{equation*} P_{5}(z) = z^{5} - \sum_{j=1}^{2} {5 \choose j} (-1)^{j}P_{2(2-j)+1}(z) = z^{5} + 5P_{3}(z) - 10P_{1}(z) = z^{5} + 5z^{3} + 5z \end{equation*}

2 yorum:

  1. Hocam post tam olarak okunmuyor? Telefondan dolayı olabilir mi?
    Yazi karakterleri bazı yerlerde anlamsizlasiyor

    YanıtlaSil
    Yanıtlar
    1. Matematiksel karakterleri Javascript ile çıkartıyoruz. Onunla ilgili olabilir. VPN ya da güvenli moda alan bir eklenti kullanıyorsanız bu uygulamalar genellikle ilk iş Javascript'i pasif duruma getirir. Dizüstü bilgisayarımda hem Chrome hem de Firefox ile denedim. Bir sorun yok.

      Sil