Tübitak Lise 1. Aşama 2022 Soru 04

[matematikolimpiyati]

$n$ adet özdeş top, $30$ kız ve $77$ erkek öğrenciye dağıtılacaktır. Bu dağıtım, her öğrenci en az bir adet, herhangi iki kız öğrenci eşit sayıda ve herhangi iki erkek öğrenci eşit sayıda top alacak biçimde tek bir şekilde yapılabiliyorsa, $n$ en fazla kaç olabilir?

$\textbf{a)}\ 321  \qquad\textbf{b)}\ 963  \qquad\textbf{c)}\ 2695  \qquad\textbf{d)}\ 4620  \qquad\textbf{e)}\ 6930$

[Squidward]

Cevap: $\boxed{D}$

Problem, $K$, kızlara dağıtılan top sayısına; $E$, erkeklere dağıtılan top sayısına denk olmak üzere "$30K+77E=n$ denkleminin pozitif sayılarda tek çözümü vardır, $n$'in alabileceği en büyük tam sayı değeri nedir?" problemine denktir.

Şıklarda "Hiçbiri" gibi bir şık olmadığından test tekniğiyle en büyük şıktan denemeye başlarsak,

$n = 6930$ için $6930$'un $30$'a bölünebildiği açıktır. $30K + 77E = 6930$ ise $E \equiv 0 \pmod{30}$ elde edilir. $6930 = 30 \cdot 231$ olduğu göze alınırsa $(K, E)=(154, 30)$ ve $(77, 60)$ çözümlerinin olduğu görülür.

$n= 4620$ için $4620$'nin $30$'a bölünebildiği açıktır. $30K + 77E = 4620$ ise $E \equiv 0 \pmod{30}$ elde edilir. $4620 = 30 \cdot 140$ olduğu göze alınırsa $(K, E) = (77, 30)$ tek çözümünün olduğu görülür, dolayısıyla cevap $n = 4620$'dir.


Tabii; bu çözüm, sınav dışında tam bir çözüm değil fakat şıklar, şıkların denenmesi için yazılmış gibi.

[geo]

$30K+77E = n$ denkleminde tam sayılarda $(K_1, E_1)$ bir çözüm ise $(K_1-77, E_1+30)$ ve $(K_1+77, E_1-30)$ de çözümdür.
Pozitif tam sayılarda tam olarak bir çözüm olması için $K_1-77 \leq 0$ ve $E_1-30 \leq 0$ olmalı. Bu durumda $\max {K_1} =77$ ve $\max {E_1} =30$ olacaktır.
Bu durumda $n$ en fazla $30\cdot 77 + 77\cdot 30 = 4620$ olabilir. $\bmod 77$ ve $\bmod 30$ da incelediğimizde $n=4620$ için tam olarak bir çözüm olduğu görülebilir.

Ayrıca bkz. Bezout Özdeşliği