Tübitak Lise 2. Aşama 2022 Soru 6

[matematikolimpiyati]

$2022$ öğrencinin bulunduğu bir okulda tatil boyunca her gün ya müze gezisi ya da doğa gezisi düzenleniyor. Hiçbir öğrenci aynı tür geziye ikinci kez katılmıyor ve tüm gezilere farklı sayıda öğrenci katılıyor. İki geziye beraber katılan iki öğrenci bulunmadığına göre, toplam gezi sayısının alabileceği en büyük değeri bulunuz.

[AtakanCİCEK]

Çözüm:İbrahim Atakan Çiçek
Her geziye farklı sayıda öğrenci katıldığına göre, geziler $s_1 < s_2 < \dots < s_T$ şeklinde sıralanabilir ve toplam öğrenci sayımı:
  $$
  \sum_{i=1}^{T} s_i = \frac{T(T+1)}{2}
  $$

- Her öğrenci en fazla ''bir doğa'' ve ''bir müze'' gezisine katılabilir yani  toplam en fazla $2 \cdot 2022 = 4044$ katılım olur.
 $$
  \frac{T(T+1)}{2} \le 4044
  \Rightarrow T \le 88
  $$
  Ayrıca, iki geziye birlikte katılan iki öğrenci olmadığından,  herhangi iki gezi arasında ''kesişimde en fazla $1$ öğrenci'' olabilir.

Diğer taraftan, iki geziye birlikte katılan iki öğrenci olmadığından, bu çift katılım sayısı bir doğa ve bir müze gezisi arasında tanımlanabilir ve tüm bu çift katılımlar bir iki parçalı grafikteki kenarlar olarak modellenebilir. Tüm gezileri ''doğa'' ve ''müze'' olmak üzere iki parçaya ayıralım.  Gezi sayısı $T = M + D$ olmak üzere, $M$ doğa ve $D$ müze gezisi olsun. Her öğrenci en fazla bir doğa ve bir müze gezisine katılabileceğinden, çift gezi yapan her öğrenci doğrudan bir ''kenar'' ile temsil edilebilir; kenar, bir doğa ve bir müze gezisini bağlar. Dolayısıyla bu sistemde oluşan iki parçalı grafikteki kenar sayısı:
$$
E = \sum_{i=1}^{T} s_i - N = \frac{T(T+1)}{2} - 2022
$$
Ve bu kenar sayısı aynı zamanda $E \le M \cdot D \le \left\lfloor \frac{T^2}{4} \right\rfloor$ çünkü iki parçalı grafikte en fazla bu kadar kenar olabilir.
[/b]
Ayrıca, kapasite sınırlaması şu koşulu doğurur:
$$
E = \frac{T(T+1)}{2} - 2022 \le \left\lfloor \frac{T^2}{4} \right\rfloor
$$
Bu eşitsizlik, $T = 80$ için bozulur. Bu da şu anlama gelir:
$$
T \le 79
$$
 Şimdi ise manuel olarak ilk sağlayan değeri bulmalıyız. Şimdi geçerli ilk $T$ değerimizi bulmaya çalışalım. $T=79$  u test edelim.  Geziler $t_1, t_2, …, t_{79}$   (öğrenci sayıları tam $1,2,…,79$) olsun ve en büyük $49$ geziyi seçelim. Varsayalım bu en büyük $49$  $t_{31}, t_{31}, …, t_{79}$ olsun. Toplam katılım
$$
31 + 32 + \cdots + 79 \;=\; 2695
$$
Çifte sayılan öğrenciler
$$
2695 - 2022 = 673
$$ ve bu ortaklıklar iki parçalı graf oluşturur, en fazla $24$ doğa ve $25$ müze bize maksimum kenar sayısını
$$
24 \times 25 = 600
$$ verir. Ancak $673 > 600$ ve bu da bize çelişki verir. Bu yüzden $T = 79$ da olamaz.

$T=78$ i test edelim.  Geziler: $t_1, t_2, …, t_{78}$   (öğrenci sayıları tam $1,2,…,78$) olsun ve en büyük $49$ geziyi seçelim. Varsayalım bu en büyük $49$  $t_{30}, t_{31}, …, t_{78}$ olsun. Toplam katılım
$$
30 + 31 + \cdots + 78 \;=\; 2646
$$

Bunlar arasında çifte sayılan öğrenciler
$$
2646 - 2022 = 624
$$
 Bu ortaklıklar iki parçalı graf oluşturur, en fazla $24$ doğa ve $25$ müze bize maksimum kenar uzunluğunu
$$
24 \times 25 = 600
$$ verir. Ancak lazım olan $624 > 600$ olduğundan çelişki verir. Dolayısıyla $T = 78$ olamaz.

Yukarıdaki eşitsizliklerden artık $T=77$ seçimi için yeterli kenar sayısı olacağı tahmin edilebilir. Bu nedenle $T = 77$ için geçerli bir yerleştirme örneği verelim. Müze gezilerimiz $M_{51}, M_{52}, …, M_{77}$ olsun. ($27$ adet) Doğa gezileri ise $D_1, D_2, …, D_{50}$ (50 adet) olsun.
Toplam gezi sayısı
$$
27 + 50 = 77
$$ Toplam kapasite
$$\sum_{k=51}^{77} k \;+\; \sum_{j=1}^{50} j
\;=\;
1728 \;+\; 1275
\;=\; 3003
$$
Çifte sayım ihtiyacı $$3003 - 2022 = 981$$ olur. Kenar planı yapalım. Her $D_j$ gezisi için  $j - 1$ ortak öğrenci Her $M_k$ gezisi için  $k - 51$ ortak öğrenci. Buradan kenar sayıları
$$
\sum_{j=1}^{50} (j - 1) \;=\; 1225,
\qquad
\sum_{k=51}^{77} (k - 51) \;=\; 351,
\qquad
1225 + 351 = 1576 > 981
$$ Yani kenar kapasitesi yeterli ve ortak öğrenciler uygun şekilde dağıtılır, kalan boşluklar tekil öğrencilerle tamamlanır. Tüm koşullar sağlandığı için maximum $T$ ancak
$$
\boxed{T_{\max} = 77}
$$ ile mümkündür.

[geo]

Cevap: $77$.

Öncelikle koşulları sağlayan $77$ günlük bir gezi programı örneği verelim. $26 \cdot 71=2002$ ögrenci alınıp bunların $26 \cdot 51=1326$ sı $A$ sınıfına konulsun ve her birine
$$
A=\left\{(i, j): i, j \in \mathbb{Z}_{+}, \quad i+j \leq 52\right\}
$$
kümesinden farklı birer ikili verilsin, kalan $26 \cdot 26=676$ sı ise $B$ sınıfına konulsun ve her birine
$$
B=\left\{(i, j): i, j \in \mathbb{Z}_{+}, \quad i \leq 26, j \leq 26\right\}
$$
kümesinden farklı birer ikili verilsin. Sonra $1 \leq k \leq 77$ olmak üzere $k$-nci günde

$(i)$ $k \leq 51$ ise $A$ sınıfından $i=52-k$ koşulunu sağlayan $k$ öğrenci müze gezisine gitsin,
$(ii)$ $k \geq 52$ ise $A$ ve $B$ sınıflarından $j=78-k$ koşulunu sağlayan toplam $k$ öğrenci doğa gezisine gitsin.

Şimdi de koşulları sağlayan $n$ günlük bir gezi programı için $n \leq 77$ olduğunu gösterelim. En kalabalık $52$ gezi grubu $M_{1}, M_{2}, \ldots, M_{k}, D_{k+1}, \ldots, D_{52}$ olsun ( $M_{i}$ ler müze gezisi gruplarını, $D_{i}$ ler ise doğa gezisi gruplarını göstersin). Koşullardan dolayı $\left|M_{i} \cap D_{j}\right| \leq 1$ dir ve $i \neq j$ için $\left|M_{i} \cap M_{j}\right|=0$ ve $\left|D_{i} \cap D_{j}\right|=0$ dır. O halde
$$
\begin{gathered}
\sum\left|M_{i}\right|+\sum\left|D_{i}\right|= \\
\left|M_{1} \cup \ldots \cup M_{k} \cup D_{k+1} \cup \ldots \cup D_{52}\right|+\sum\left|M_{i} \cap D_{j}\right| \leq \\
2022+k(52-k) \leq 2698<26 \cdot 104
\end{gathered}
$$
tür. Öte yandan tüm gezi gruplarında farklı sayıda öğrenci bulunduğundan
$$
\sum\left|M_{i}\right|+\sum\left|D_{i}\right| \geq n+(n-1)+\ldots+(n-51)=(2 n-51) \cdot 26
$$
dır. Dolayısıyla $2 n-51<104$ olup $n \leq 77$ dir.

Not 1: Çözümde $n \leq 77$ nin ispatlandığı kısımda en kalabalık $52$ gruba bakmak yerine herhengi bir $46 \leq m \leq 58$ sayısı için en kalabalık $l$ gruba bakmak da aynı sonuca ulaştırır.

Not 2: Soruda $2022$ yerine herhangi bir $m$ sayısı olursa cevap $n(n+1) \leq 3 m$ koşulunu sağlayan en büyük $n$ tam sayı değeri olur.

Kaynak: Tübitak 30. Ulusal Matematik Olimpiyatı İkinci Aşama Sınavı Çözümleri