Son İletiler

Sayfa: [1] 2 3 ... 10
1
Kombinatorik / Dama Tahtası Problemi 1999 - USAMO (ABD Mat. Olimpiyatı)
« Son İleti Gönderen: Lokman Gökçe Bugün, 02:47:41 öö »
Problem[1999-USAMO]: $n \times n$ dama tahtasına bazı dama taşları aşağıdaki kurallara göre yerleştirilecektir:

$(a)$ Dama taşı içermeyen her kare, dama taşı olan bir kareyle ortak bir kenara sahiptir.

$(b)$ Dama taşları içeren herhangi iki kare çifti verildiğinde; verilen karelerle başlayan ve biten, dama taşları içeren bir kareler dizisi vardır ve bu dizinin her iki ardışık karesi bir ortak kenara sahiptir.

Tahtada en az $\dfrac{n^{2}-2}{3}$ dama taşı olduğunu kanıtlayınız.





Bazı Anekdotlar ve Bilgiler:

$\color{blue}\bullet $ Problem ABD'de lise öğrencilerine sorulmuş olsa da, çözüm yöntemi olarak çizge teorisi içerdiği için lisans düzeyi olarak etiketlemeyi daha uygun gördüm.

$\color{blue}\bullet $ İlk önce klasik kombinatorik yöntemlerle problemi çözmeyi denedim ama genel bir çözüm bulmayı başaramadım. "Çözüm Öncesi Motivasyonu" başlığı altında ilk çözüm girişimlerimi paylaşacağım.

$\color{blue}\bullet $ Matematikte bilmediğim bazı özel konulara uğraşmama sebep olan bazı problemler olmuştur. Temel bir bilgi  sahibi olduğum çizge teorisine daha fazla yüklenmem için beni motive şey de bu problem oldu. Benim için zihinsel açıdan köşe taşı olan sorulardan biridir. Şimdi düşündüm de, benim için köşe taşı olmuş olan bu tür özel problemler için bir liste oluşturmak iyi olabilir. Üzerinde çok düşündüğümüz bir konuyu daha derinlemesine öğrenebiliyoruz. Bunları sunarken de dinleyicilere güzel biçimde anlatabilme fırsatı oluyor. Daha önce yapılmış çözümlerden faydalanarak, problemin titiz bir çözümünü hazırlamaya çalıştım. Biraz daha düşünmek için kendime de süre tanıyacağım ve çözümü bir süre sonra paylaşacağım.



Çözüm Öncesi Motivasyonu: 

$n \in \{2, 3 , 4, 5, 6 \}$ durumlarını inceleyelim.
$
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ   \\ \hline
\text{ } & \circ  \\ \hline
\end{array}
\quad
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \text{ } \\ \hline
\textbf{} & \circ & \text{ } \\ \hline
\end{array}
\quad
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ & \circ & \text{ }  \\ \hline
\text{ } & \circ & \circ & \text{ }  \\ \hline
\text{ } & \circ & \circ & \text{ }  \\ \hline
\text{ } & \circ & \circ & \text{ }  \\ \hline
\end{array}
\quad
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \circ    & \circ & \text{ } \\ \hline
\end{array}
\quad
\begin{array}{|c|c|c|c|c|c|}
\hline
\text{ } & \circ & \text{ } & \circ & \circ    & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \circ    & \circ & \text{ } & \circ \\ \hline
\end{array}
$

Şimdi de $n$ yi çift/tek sayı yönünden inceleyelim.

$\bullet $ $n=5$ için olan tablodaki durumu genelleştirelim. $n\geq 5$ ve $n$ bir tek sayı ise, en az $ n\cdot \dfrac{n-1}{2} + \left(  \dfrac{n-1}{2} - 1\right) = \dfrac{n^2 - 3}{2}$ tane dama taşı kullanılır. 
$\bullet $ $n=6$ için olan tablodaki durumu genelleştirelim. $n\geq 6$ ve $n$ bir çift sayı ise, en az $ n\cdot \dfrac{n}{2} + \left(  \dfrac{n}{2} - 1\right) = \dfrac{n^2 + n - 2}{2}$ dama taşı kullanılır. Bu durumda, $\dfrac{n^2 + n - 2}{2} \geq \dfrac{n^2 - 3}{2} $ olur.

Bunlar sezgisel çizimlerdir. Bağlantılı bir grafik oluşturmamız gerektiğine dikkat edilmelidir. Çizge teorisinin fikirleri kullanılarak kesin bir kanıt yapılabilir. Örneğin, yukarıdaki analizimiz aşağıdaki şekli kapsamamaktadır.

$$
\begin{array}{|c|c|c|c|c|c|}
\hline
\circ    & \circ    & \circ    & \circ    & \circ & \text{ } \\ \hline
\circ    & \text{ } & \circ    & \text{ } & \circ & \text{ } \\ \hline
\color{red}\bullet    & \text{?} & \text{ } & \text{ } & \circ & \text{ } \\ \hline
\text{?} & \color{red}\bullet    & \text{ } & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ    & \text{ } & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ    & \circ    & \circ    & \circ & \text{ } \\ \hline
\end{array}
$$

Öte yandan, çözümümüzü geliştirebiliriz. Kırmızı ile gösterdiğimiz çapraz konumlu damalara dikkat edelim. Yanında soru işareti olan hücreler boştur. Damalarımızın birbiriyle bağlantılı olması gerektiğinden; çapraz konumlu kırmızı dama taşları, düzenlememizde sadece bir kez görünebilir. Yani, minimum sayıda dama taşı kullanarak oluşturduğumuz bir konfigürasyonun farklı kısımlarında çapraz konumlu kırmızı damalar oluşursa, bağlantılılık özelliği kaybedilecektir. Kırmızı damalar, bağlantılı damaların başlangıç ve bitiş noktaları olarak düşünülebilir. Yukarıdaki çizdiğimiz $6\times 6$ türündeki tahtada ekstra damalara ihtiyacımız yok. Minimum sayıda dama taşı kullanıldığında döngü oluşmadığını gözlemliyoruz. Ayrıca, şekilde ağaç çizgesinin oluşutuğunu da gözlemliyoruz.

Bu gözlemler çizge teorisine geçiş yapmamız için yeterince motivasyon sağlıyor.
2
Üniversite Hazırlık Cebir / Ynt: En büyük değer
« Son İleti Gönderen: Lokman Gökçe Bugün, 01:21:22 öö »

Yanıt: $\boxed{930}$

 
$a$ ve $b$ nin pozitif tam sayı değerlerini olabildiğince küçük seçersek $c$ yi büyütmüş oluruz. Simetriden dolayı, genelliği bozmaksızın $a\leq b \leq c$ kabul edebiliriz. $a=1$ denklemi sağlamaz. $a=2$ alırsak $\dfrac{1}{b} + \dfrac{1}{c} = \dfrac{8}{15} - \dfrac{1}{2} = \dfrac{1}{30}$ olur. $b>30$ olmalıdır. $b=31$ verirsek $\dfrac{1}{c} = \dfrac{1}{30} - \dfrac{1}{31} = \dfrac{1}{930}$ olup $c_\max=930$ elde edilir.
3
Kombinatorik / Ağaç Çizgenin Kenar Sayısı
« Son İleti Gönderen: Lokman Gökçe Bugün, 01:20:17 öö »
Problem: $n\geq 1$ köşeli (noktalı) bir ağaç çizgenin $n-1$ kenarı vardır, kanıtlayınız.


Not: Bağlantılı olup döngü içermeyen çizgelere ağaç denir. Ağaç çizge ile ilgili buraya bakılabilir.
4
Üniversite Hazırlık Cebir / En büyük değer
« Son İleti Gönderen: alpercay Dün, 05:40:19 ös »
$a, b, c$ sayma sayıları için $$1/a+1/b+1/c=8/15$$ ise $c$ sayısının en büyük değeri kaçtır?
5
Kombinatorik / Ynt: Tek Sayıda Köşesi Olan m-düzenli Çizgeler
« Son İleti Gönderen: Lokman Gökçe Dün, 04:29:02 ös »
Çözüm: $n=2k+1$ tek tam sayı olsun ($k\geq 1$). İndislerdeki toplama çıkarma işlemleri modülo $n$ üzerinde olmak üzere, çizgenin köşeleri $A_1A_2\dots A_n$ düzgün çokgeninin köşeleri olsun.

$m=2t$ ($t\geq 1$) çift tek sayı iken  $A_i$ köşesini kendinden önceki ilk $t$ tane köşeye, kendinden sonraki ilk $t$ tane köşeye birleştiririz. Yani $A_i$ noktasını, $\{ A_{i-1}, A_{i-2}, \dots, A_{i-t}, A_{i+1}, A_{i+2}, \dots, A_{i+t} \}$ noktalarıyla birleştirerek $\deg(A_i)= 2t = m$ elde ederiz. Böylece, verilen aralıktaki her $m$ çift sayısı için uygun konfigürasyon bulunmuş olur.
$n=11$ ve $m=6$ için örnek çizim aşağıdadır.

6
Kombinatorik / Ynt: Çift Sayıda Köşesi Olan m-düzenli Çizgeler
« Son İleti Gönderen: Lokman Gökçe Dün, 04:23:55 ös »
Çözüm: $n=2k$ çift tam sayı olsun ($k\geq 2$). İndislerdeki toplama çıkarma işlemleri modülo $n$ üzerinde olmak üzere, çizgenin köşeleri $A_1A_2\dots A_n$ düzgün çokgeninin köşeleri olsun.

$\color{blue}\bullet$ $m=2t$ ($t\geq 1$) çift tek sayı iken  $A_i$ köşesini kendinden önceki ilk $t$ tane köşeye, kendinden sonraki ilk $t$ tane köşeye birleştiririz. Yani $A_i$ noktasını, $\{ A_{i-1}, A_{i-2}, \dots, A_{i-t}, A_{i+1}, A_{i+2}, \dots, A_{i+t} \}$ noktalarıyla birleştirerek $\deg(A_i)= 2t = m$ elde ederiz. Böylece, verilen aralıktaki her $m$ çift sayısı için uygun konfigürasyon bulunmuş olur.
$n=10$ ve $m=4$ için örnek çizim aşağıdadır.

$\color{blue}\bullet$ $m=2t+1$ ($t\geq 1$) tek sayı iken  $A_i$ köşesini kendinden önceki ilk $t$ tane köşeye, kendinden sonraki ilk $t$ tane köşeye birleştiririz. Ayrıca $n$ çift sayı olduğundan, düzgün $n$-gen de her köşenin merkeze göre simetrisi bir başka köşedir. $A_i$ noktasının merkeze göre simetrisi $A_{i+k}$ dir. $A_i$ noktasını $A_{i+k}$ noktasına da birleştirelim. Yani $A_i$ noktasını, $\{ A_{i-1}, A_{i-2}, \dots, A_{i-t},  A_{i+1}, A_{i+2}, \dots, A_{i+t} \} \cup \{ A_{i+k}\}$ noktalarıyla birleştirerek $\deg(A_i)= 2t +1= m$ elde ederiz. Böylece, verilen aralıktaki her $m$ tek sayısı için uygun konfigürasyon bulunmuş olur.
$n=10$ ve $m=5$ için örnek çizim aşağıdadır.

7
Kombinatorik / Ynt: Ülkedeki Şehirlerin Sayısı
« Son İleti Gönderen: Lokman Gökçe Dün, 04:19:37 ös »
Yanıt: $\boxed{43}$


Çözüm: Şehirleri $A_1, A_2, \dots, A_n$ noktalarıyla gösterelim. Eğer iki şehir arasında doğrudan bir yol varsa, bu iki noktayı birleştirelim. $n$ için bir alt sınır ve bir üst sınır bulmamız gerekmektedir. Akla gelebilecek basit bir alt sınır $n\geq 18$ olabilir. Çünkü, her bir noktanın derecesi en az $17$ ise, o nokta başka $17$ noktaya daha bağlıdır. Böylece $n\geq 17+1 = 18$ yazılabilir.

Fakat bu sınırı daha da geliştirebiliriz. $n$ köşeli bir tam çizge düşünelim. Yani herhangi iki şehir arasında daima bir yol olması durumuna bakıyoruz. Toplam $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ tane yol (tam çizgenin kenar sayısı) vardır. Böylece $\dfrac{n(n-1)}{2} \geq 190$ olup $n\geq 20$ elde edilir. $n=18$ ve $n=19$ durumlarında uygun konfigürasyonun varlığını/yokluğunu araştırma zahmetinden kurtulduk. $n=18$ ve $n=19$ için çözüm yoktur.

Peki, $n=20$ için çözüm var mıdır? sorusuna da hemen cevap verelim. $n=20$ iken çizgemiz, bir tam çizge olursa ancak bu durumda yol sayısı (çizgenin kenar sayısı) $|E|=190$ olabilmektedir. Fakat bu halde de tüm köşeler için derece $19$ olur. Yani derecesi $17$ olan köşe yoktur. $n=20$ olamaz.

Şimdi $n=21,22,23, 24 \dots $ değerlerini incelemeden önce, $n$ için bir üst sınır araştıralım. El sıkışma teoremine göre, tüm noktaların dereceleri toplamı $2|E| = 2\cdot 190 = 380 $ dir. Her köşe için derece en az $17$ verildiğinden, $380 = 2|E| \geq 17\cdot n $ olup $n\leq 22$ elde edilir. 

$\color{red}\bullet $ $n=21$ için örnek çizge araştıralım. Noktaların (şehirlerin) dereceleri $ 17, 18, 19, 20 $ olabilir. Bu derecelere sahip noktaların sayısı sırasıyla $a, b, c, d$ olsun. $a \geq 1$ olmak üzere

\begin{equation*}
\left.
\begin{split}
  17a+18b+19c +20d & = & 380 \\
  a+b+c+d & = & 21
\end{split}
\text{ } \right\}
\end{equation*} 

denklem sistemi için negatif olmayan tam sayılarda bir çözüm bulmalıyız. Bir çok pozitif tam sayı çözüm vardır, biz $(a,b,c,d) = (12, 1, 2, 6)$ çözümünü örnekleyelim. (Soruyu hazırlarken pozitif tam sayı çözüm olduğunu söylemek yeterli olur diye düşünmüştüm, şimdi aynı fikirde değilim. Gerçek bir örnek bulmak zorundayız ve bu da soruyu biraz daha zorlaştırıyor. Soru, 1. aşama sınavı sorularının zorluk düzeyinin üstündedir.) Önce $A_1, A_2, \dots ,A_{21}$ noktalarını kullanarak bir $K_{21}$ tam çizgesi oluşturalım. $21\cdot 20/2 = 210 $ tane kenar oluşur. Her bir köşenin derecesi $20$ dir. Şimdi kenarlardan bazılarını köşe dereceleri $17$ nin altına düşmeyecek şekilde kaldıralım.

$A_1$ in bağlı olduğu $\{ A_{19}, A_{20}, A_{21} \}$ köşeleri ile aralarındaki kenarları kaldıralım.

$A_2$ nin bağlı olduğu $\{ A_{19}, A_{20}, A_{21} \}$ köşeleri ile aralarındaki kenarları kaldıralım.

$A_3$ ün bağlı olduğu $\{ A_{19}, A_{20}, A_{21} \}$ köşeleri ile aralarındaki kenarları kaldıralım. Böylece $\deg(A_1) = \deg(A_2)  = \deg(A_3) = \deg(A_{19}) = \deg(A_{20}) = \deg(A_{21}) = 17$ olur. Mevcut kenar sayısı $210 - 3\cdot 3 = 201$ dir. Devam edelim.

Benzer şekilde $\{ A_{4}, A_{5}, A_{6} \}$ grubu ile $\{ A_{16}, A_{17}, A_{18} \}$ grubu arasındaki kenarları kaldıralım. Böylece $\deg(A_4) = \deg(A_5)  = \deg(A_6) = \deg(A_{16}) = \deg(A_{17}) = \deg(A_{18}) = 17$ olur. Mevcut kenar sayısı $201 - 3\cdot 3 = 192$ dir. Devam edelim.

$A_7$ nin bağlı olduğu $\{ A_{14}, A_{15} \}$ köşeleri ile aralarındaki kenarları kaldıralım. $\deg(A_7) = 18$, $\deg(A_{14}) = \deg(A_{15}) = 19$ olur. Dokunmadığımız köşeler için $\deg(A_8) = \deg(A_9)  = \deg(A_{10}) = \deg(A_{11}) = \deg(A_{12}) = \deg(A_{13}) = 20$ dir. Mevcut kenar sayısı $192 - 2 = 190$ dır. Örnek bir konfigürasyon bulundu.

$\color{red}\bullet $ $n=22$ için örnek çizge araştıralım. Noktaların (şehirlerin) dereceleri $ 17, 18, 19, 20, 21 $ olabilir. Bu derecelere sahip noktaların sayısı sırasıyla $a, b, c, d, e$ olsun. $a \geq 1$ olmak üzere

\begin{equation*}
\left.
\begin{split}
  17a+18b+19c +20d + 21e& = & 380 \\
  a+b+c+d +e & = & 22
\end{split}
\text{ } \right\}
\end{equation*} 

denklem sistemi için negatif olmayan tam sayılarda bir çözüm bulmalıyız. Daha da önemlisi, bu çözüme uygun bir çizge konfigürasyonu bulmalıyız. Önce $K_{22}$ tam çizgesini çizelim. Her bir köşenin derecesi $21$ dir. $22\cdot 21/2 = 231$ kenar vardır. Bunlardan bazılarını silerek $190$ a kadar ineceğiz. Fakat her bir köşe derecesinin de $17$ nin altına düşmesine izin vermemeliyiz. Benzer adımları kullanalım.

$\{ A_{1}, A_{2}, A_{3}, A_{4} \}$ grubu ile $\{ A_{19}, A_{20}, A_{21}, A_{22} \}$ grubu arasındaki kenarları silelim. $4\cdot 4 = 16$ kenar silinir. Bu $8$ noktanın derecesi $17$ ye düşer. $231 - 16 = 215$ kenar kalır.

$\{ A_{5}, A_{6}, A_{7}, A_{8} \}$ grubu ile $\{ A_{15}, A_{16}, A_{17}, A_{18} \}$ grubu arasındaki kenarları silelim. $4\cdot 4 = 16$ kenar silinir. Bu $8$ noktanın derecesi de $17$ ye düşer. $215 - 16 = 199 $ kenar kalır.

$\{ A_{9}, A_{10}, A_{11} \}$ grubu ile $\{ A_{12}, A_{13}, A_{14} \}$ grubu arasındaki kenarları silelim. $3\cdot 3 = 9$ kenar silinir. Bu $6$ noktanın derecesi $18$ e düşer. $199 - 9 = 190 $ kenar kalır. 

$n=22$ iken $(a,b,c,d,e) = (16, 6, 0, 0, 0)$ çözümüne karşılık bir konfigürasyon bulmuş olduk.

Öte yandan $n=22$ çift sayı iken $0\leq m < n$ aralığındaki her $m$ tam sayısı için $m$-düzenli çizge bulabildiğimizi Çift Sayıda Köşesi Olan m-düzenli Çizgeler başlığında göstermiştik. $m=17$ için $22$ köşeli $17$-düzenli çizgede $22\cdot 17/2 = 187$ kenar vardır. $190 - 187 = 3$ kenar daha eklersek örnek bulmuş olacağız. Örneğin $A_1$ köşesini alalım ve bunun bağlı olmadığı $22-17-1 = 4$ köşe vardır. $A_1$ i bunlardan üçüne bağlarsak bir başka örnek durum elde etmiş oluruz.

Sonuç olarak, $n\in \{21, 22\} $ şeklinde iki değer vardır. Bunların toplamı ise $21+22 = \boxed{43}$ olur.



8
Problem: Her $n\geq 1$ tek tam sayısı ve $0\leq m < n$ aralığındaki her $m$ çift tam sayısı için $n$ köşeli bir $m$-düzenli çizgenin varlığını kanıtlayınız.


Notlar:
$\color{blue}\bullet $ $n$ köşeli bir $m$-düzenli çizge, köşelerin her birinin derecesinin aynı $m$ sayısına eşit olduğu çizgelerdir.

$\color{blue}\bullet $ $m$ ve $n$ tek sayı iken $n$ köşeli $m$-düzenli çizge yoktur. Çünkü çizgenin toplam derecesi $m\cdot n$ bir tek sayıdır ve Leonard Euler'in El Sıkışma Teoremi ne göre, çizgenin toplam derecesi çift sayı olmalıdır. Çelişki.

$\color{blue}\bullet $ $m=0$ durumunda çizgeye hiç kenar çizmiyoruz demektir. $n>m\geq 2$ problemi çözülmelidir.

$\color{blue}\bullet$ $n$ için çift sayı durumu incelenmişti. Bunlarla beraber düşünülürse, $n$ köşeli $m$-düzenli çizgeler ile ilgili olarak $(m,n)$ ikililerinin alabileceği tüm değerleri belirlemiş oluyoruz.
9
Problem: Her $n\geq 2$ çift tam sayısı ve $0\leq m < n$ aralığındaki her $m$ tam sayısı için $n$ köşeli (noktalı) bir $m$-düzenli çizgenin varlığını kanıtlayınız.



Notlar:
$\color{blue}\bullet $ $n$ köşeli bir $m$-düzenli çizge, köşelerin her birinin derecesinin aynı $m$ sayısına eşit olduğu çizgelerdir.

$\color{blue}\bullet $ $m=0$ durumunda çizgeye hiç kenar çizmiyoruz demektir. $m = 1$ durumunda $n$ tane noktayı ikişerli olarak gruplandırırsak $\dfrac{n}{2}$ tane grup olur. Her grubun
iki noktasını kendi içinde birleştirerek $\dfrac{n}{2}$ tane kenar elde ederiz. Her noktanın derecesinin $m=1$ olduğu gösterilmiş olur. $n>m\geq 2$ için problem çözülmelidir.
10
$12)$ $\phi(n)=\frac{n}{4}$ olsun. $4\mid n$ ve $n\geq 4$ olduğu barizdir. $n$'yi asal çarpanlarına ayırırsak $n=2^ap_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ dersek $a\geq 2$'dir ve $11.$ sorunun çözümüne benzer şekilde $$\prod_{p\mid n} \left(1-\frac{1}{p}\right)=\left(1-\frac{1}{2}\right)\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_k}\right)=\frac{1}{4}$$ $$\implies \frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots \frac{p_k-1}{p_k}=\frac{1}{2}$$ olur. Eşitliğinin sol tarafında payda tek sayı olduğundan herhangi bir sadeleştirme işlemi sonucunda $\frac{1}{2}$ elde edilemez. Böyle bir $n$ yoktur.
Sayfa: [1] 2 3 ... 10

SimplePortal 2.3.3 © 2008-2010, SimplePortal