Turnuvadaki takım sayısının alabileceği değerlerin belirlenmesi

Question

Problem: In a football tournament where $n>2$ teams participate, each team plays a match against each other. The number of matches won and drawn by each team is the same. For example, one team may have won $5$ games and finished $5$ games in a draw, while another team may have won $8$ games and finished $8$ games in a draw. Determine the values that $n$ can take.

Solution (Lokman Gökçe):

Each team plays $n-1$ matches. Let the teams win $a_1, a_2, \dots , a_n$ games and lose $b_1, b_2, \dots , b_n$ games, respectively. $$2a_1 + b_1 = n-1, \quad 2a_2 + b_2 = n-1, \text{ } \dots \text{ } , \quad 2a_n + b_n = n-1 .$$

If we add these equations together, we get

$$\sum_{i=1}^{n} (2a_i + b_i) = n(n-1).$$

Also $$\sum_{i=1}^{n} a_i = \sum_{i=1}^{n} b_i$$ is an invariant for us. Therefore we find that

$$\sum_{i=1}^{n} a_i = \dfrac{n(n-1)}{3} \tag{1}$$

$\bullet$ If $n = 3k + 2$ ($k \in \mathbb Z^+$), $\dfrac{n(n-1)}{3}$ is not a positive integer. Thus, $n$ can not in the form $3k+2$. 

$\bullet$ If $n = 3k + 1$ ($k \in \mathbb Z^+$), we can find a suitable configuration that satisfy all conditions. Let $A_1, A_2, \dots , A_n$ be teams. If team $A_i$ has won against $A_j$, we will show this with $A_i \to A_j$. If their match ends in a draw, we will not draw a line between them. (You can draw dashed lines if you want, but the shape may look a bit complicated.) For the sake of simplicity, I will draw a graph for the case $k=3, n=10$.

       

$$(A_1\to A_2, A_1\to A_3, A_1\to A_4); \quad (A_2\to A_3, A_2\to A_4, A_2\to A_5); \quad \dots \quad ; (A_{10}\to A_1, A_{10}\to A_2, A_{10}\to A_3)$$  

Thus, in this configuration each team team has $3$ wins, $3$ losses, and $3$ draws. Easily we can adapted this configuration to $n = 3k+1$ form. Each team team will have $k$ wins, $k$ losses, and $k$ draws.

$\bullet$ For $n=3$ case, easily we can see that there is a suitable configuration. For the teams $A_1, A_2, A_3$, if $A_1 \to A_2$ then $A_1$ and $A_3$ have a draw game. So, $A_3 \to A_2$. For $n=3k$ and $k\geq 2$,we can find a configuration. $A_n$ loses all matches. Matches between other $n-1$ teams result in $m-1$ wins, $m-1$ losses, $m$ draws. From $(m-1) + (m-1)+ m = n - 2 = 3k - 2$, we get $m=k$. Thus, $n$ can be in the form $3k$. 

Below we see an example graph for the case $k=3, n=9$. In the figure, $A_9$ lost to every other team.

Aslo, $$(A_1\to A_2, A_1 \to A_3); \quad (A_2\to A_3, A_2\to A_4); \quad \dots \quad ; (A_7\to A_8, A_7\to A_1); (A_8\to A_1, A_8\to A_2)$$  

When $n=3k$, $k\geq 2$, $A_n$ will loss to the others. If the indexes $\{ 1, 2, \dots , n-1\}$ in $\pmod {n-1}$, $A_i$ wins to $A_{i+1}, A_{i+2},\dots , A_{i+k-1}$ and $A_i$ loss to $A_{i-1}, A_{i-2}, A_{i-k+1}$. Other matches will end in a draw. This is a suitable configuration for $n=3k$, $k\geq 2$ case.

 

In summary, for $k\geq 1$ integers, if $n = 3k+1$ or $n = 3k$ then there is a suitable configuration. When $n=3k+2$, there is no suitable configuration.

 

 

 

Notlar:
1. Problemi yabancı bir siteye gönderecektim. Çözüm üzerindeki kısmi ilerlemelerimi yazarken, problemin tamamını çözdüm sanıyorum. Site kuralları gereği çözümünü bildiğimiz soruyu göndermemiz uygun olmuyordu. Bu sebeple soruyu yabancı sitede sormaktan vazgeçtim.

2. Lise olimpiyatları düzeyinde bir sorudur. Yazıp bitirdiğim için paylaşım amaçlı burada sunmak faydalı olur. Daha sonra Türkçe çevirisini de paylaşabilirim. Hata veya düzeltme gerektiren kısımlar varsa belirtirseniz sevinirim. Problem farklı çözümlere de açıktır.

3. Problemi, kaynak olarak Refail Alizade'nin Sonlu Matematik isimli kitabından alıp genişlettim. Kitapta $(1)$ denklemine ulaşılması amaçlanan biçimde soru soruluyor. Burada $n$ nin tüm mümkün değerlerini araştırmış olduk.

Comments

Güzel olmuş. Başka konfigürasyonlar da olabilir mi acaba?

---

$n=3k+1,\ (k>0)$ durumunda (şekildeki) konfigürasyon şöyle açıklanabilir (indisler$\mod n$):

Her bir $i$ için; $A_i$ takımı, $A_{i-1},A_{i-2},\ldots A_{i-k}$ takımlarına yenilip, $A_{i+1},A_{i+2},\ldots, A_{i+k}$ takımlarını yener diğerleri ile berabere kalır.