IMO 1990 Grafik Teorisi Problemi
Bu yüzden IMO 1990 P2 için bu çözümü gördüm:
Problem 2: n≥3'ü varsayalım ve S bir daire üzerinde 2n − 1 farklı nokta olsun. Tam olarak k S noktasının siyah renkte olduğunu varsayalım. En az bir çift siyah nokta varsa, S renginin bir rengi "iyi" olarak adlandırılır, öyle ki, çift arasındaki yaylardan birinin iç kısmı tam olarak n tane S noktası içerir. "İyi" ol.
Çözüm: Köşeleri noktaları temsil eden ve tanımladıkları yaylardan birinin iç kısmı tam olarak n köşeye sahipse, iki köşe arasında bir kenar olan bir G grafiğini düşünün. K köşelerini renklendirdiğimizde, iki bitişik köşenin renklendiğini göstermek istiyoruz. Her bir tepe noktasının derecesi 2 olduğundan, Alıştırma 4.1.4, G'nin ayrık döngülerin birleşimi olduğunu gösterir. Köşeleri 1'den 2n - 1'e kadar numaralandırırsak, o zaman 1'in n + 2'ye ve n + 2'nin tepe 4 olan 2n + 3'e bitişik olduğuna dikkat edin. Dolayısıyla 1 ve 4 aynı döngüdedir. 2n - 1, 3'e bölünemiyorsa, G yalnızca bir döngüden oluşur, dolayısıyla k = n açıkça istenen sayıdır. 2n − 1 3'e bölünebiliyorsa, grafik 2n − 1 3 uzunluğunda üç ayrık döngüden oluşur. Böylece, ardışık köşeleri renklendirmeden bir döngünün en fazla 2n − 1 3 −1 2 = n ecutive 2 3 köşesini renklendirebiliriz. Böylece k = 3 · ((n - 2) / 3) + 1 = n - 1 bu durumda istediğimiz sayıdır.
Neden her köşenin DEGREE 2'ye sahip olacağını söylediğini anlamıyorum, birisi bunu bana açıklayabilir mi?
Yanıtlar
Derece, her bir tepe noktasının birbirine bağlanan kenarlara sahip olduğu diğer köşelerin sayısıdır. Bu durumda, birbirine bağlı iki köşe, daire boyunca her yönde n + 1 nokta sayılarak bulunur.