Gönderen Konu: Turnuvadaki takım sayısının alabileceği değerlerin belirlenmesi  (Okunma sayısı 3596 defa)

Çevrimdışı Lokman Gökçe

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3.716
  • Karma: +23/-0
  • İstanbul
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. Yazıp bitirdiğim için paylaşım amaçlı burada sunmak faydalı olur bence. 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.
« Son Düzenleme: Temmuz 21, 2022, 01:40:02 ös Gönderen: Lokman Gökçe »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal