Tübitak Lise 1. Aşama 2004 Soru 03

[geo]

Elemanlarının hepsi $102$ den küçük olan ve herhangi iki elemanının toplamını içermeyen bir pozitif tam sayı kümesinin en çok kaç elemanı olabilir?

$
\textbf{a)}\ 49
\qquad\textbf{b)}\ 50
\qquad\textbf{c)}\ 51
\qquad\textbf{d)}\ 54
\qquad\textbf{e)}\ 62
$

[t-temiz]

$51+52=103$ olduğundan eğer $51,52, \ldots,100,101$ sayılarını alırsak elde edilen en küçük toplam , en büyük elemandan büyük olacağından koşulu sağlar. Bu kümeye $50$ elemanını ekleyemeyiz ; çünkü $50+51=101$ olur ki $101$ kümenin elemanıdır. Başka bir ifadeyle eğer $50$ kümede olursa $101$ olamaz . Sonuç olarak eleman sayısı en fazla $101-51+1=51$ olur. Cevap $C$.

[Lokman Gökçe]

Yukarıda verilen çözüm, $51$ sayı seçilerek koşulların sağlanabileceğini gösteren bir örnektir. Eksiksiz bir çözüm için, $52$ tane tam sayı nasıl seçilirse seçilsin, mutlaka ikisinin toplamı bir diğerini veren üç sayı bulunacağı da ispat edilmelidir. Müsait bir vakitte bu kısmı da eklemeye çalışalım.

[geo]

Yanıt: $\boxed C$

Kümede hiç tek sayı yoksa, $\{2, 4, \ldots , 100\}$, en fazla $50$ eleman seçilebilir.
Kümede en az bir tek sayı olsun ve bunların en büyüğü $2k+1$ olsun.
$\{1,2,\ldots,  101\}$ kümesini $A = \{1,2,\ldots, 2k\}$, $B = \{2k+1\}$, $C=\{2k+2, \ldots, 2\cdot 50 +1\}$ şeklinde üç kümeye ayıralım.
$|A|=2k$, $|B|=1$, $|C|=100-2k$.
$2k+1$ seçtiğimiz kümede yer aldığı için, $C$ den sadece çift sayılar seçilebilir.
$A$ kümesini $k$ ayrık kümeye $A_1=\{1, 2k\}$, $A_2=\{2, 2k-1\}$, $\ldots$, $A_k=\{k, k+1\}$ şeklinde ayırırsak her kümeden en fazla $1$ eleman seçilebilir.
Bu durumda seçilecek küme en fazla $\dfrac {2k}2 + 1+ \dfrac{100-2k}{2}=k+1+50-k=51$ elemanlı olabilir.

Ayrıca istenen koşulan sahip $51$ elemanlı örnek bir küme vardır: $\{51, 52, 53, \dots, 101\}$.

[geo]

Aşağıdaki çözüm Google Gemini 3 Pro modeline ait birkaç cevabın birleştirilmesi ile oluşturulmuştur.

Bu problem, matematikte "toplamı içermeyen kümeler" (sum-free sets) olarak bilinen konuya girer. Amacımız, $\{1, 2, 3, \dots, 101\}$ kümesi içinden, herhangi iki elemanının toplamı yine kümenin içinde olmayan en geniş alt kümeyi bulmaktır.

Bu tür bir kümenin eleman sayısının en fazla kaç olabileceğini bulmak için iki etkili yöntem (strateji) vardır.

1. Strateji: Büyük Sayıları Seçmek (Üst Yarı Yöntemi)
Kümeye sayı doğrusunun en sonundaki (en büyük) sayıları alırsak, bu sayıların toplamı evrensel kümemizin ($101$) dışına taşacaktır.

• Kümenin en küçük elemanı $n$ olsun.
• Bu kümeden seçilecek en küçük iki sayının toplamı (kendisiyle toplamı dahil) en az $n + n = 2n$ olacaktır.
• Bu toplamın, kümenin en büyük elemanı olan $101$'den büyük olması gerekir ki küme içinde yer almasın. $$2n > 101$$ $$n > 50.5$$
• Bu durumda $n$ en az $51$ olabilir.

Kümeyi oluşturalım: $$A = \{51, 52, 53, \dots, 101\}$$

Bu kümedeki herhangi iki sayıyı toplarsak (en küçük toplam $51+51=102$), sonuç $101$'den büyük olacağı için kümenin içinde yer alamaz.

Eleman Sayısı:
Terim Sayısı = (Son Terim - İlk Terim) + 1. $$101 - 51 + 1 = 51$$
2. Strateji: Tek Sayıları Seçmek
Eğer kümemizi sadece tek sayılardan oluşturursak: $$B = \{1, 3, 5, \dots, 101\}$$
Herhangi iki tek sayının toplamı bir çift sayıdır. Kümemizde hiç çift sayı bulunmadığı için, toplamların hiçbiri kümede yer almaz.
Eleman Sayısı: $$\frac{101 - 1}{2} + 1 = 51$$

Sonuç: Her iki stratejiyle de ulaşılabilen maksimum eleman sayısı $51$'dir.

Şimdi de, Güvercin Yuvası İlkesi mantığına dayanan zarif bir "çelişki ile ispat" yapalım.

Varsayalım ki bu kümenin (adına $A$ diyelim) eleman sayısı $k$ olsun. Biz bu kümenin $k=52$ elemanlı olup olamayacağını test edeceğiz.

Adım 1: Kümeyi ve En Büyük Elemanı Tanımlayalım
Kümemizin elemanlarını küçükten büyüğe sıralayalım:
$$A = \{a_1, a_2, a_3, \dots, a_k\}$$
Burada $a_k$, kümenin en büyük elemanıdır ve soruda verilen sınıra göre $a_k \le 101$ olmak zorundadır.

Adım 2: "Farklar Kümesi" Oluşturalım
Şimdi, matematiksel bir hile yapalım. Kümenin en büyük elemanı olan $a_k$'dan, kendisi hariç diğer tüm elemanları çıkararak yeni bir $B$ kümesi oluşturalım:
$$B = \{a_k - a_1,\ a_k - a_2,\ \dots,\ a_k - a_{k-1}\}$$

Bu $B$ kümesinin özellikleri şunlardır:

• $B$ kümesinin eleman sayısı, $A$'nınkinden tam 1 eksiktir ($k-1$ tane).
• $B$'deki tüm sayılar pozitiftir.

Adım 3: Kritik Çakışma Noktası
Şimdi asıl soru şu: $A$ kümesi ile $B$ kümesinin ortak bir elemanı olabilir mi?

Eğer ortak bir elemanları olsaydı (diyelim ki bu sayı $x$ olsun);

• $x$, $A$ kümesinin içinde olurdu ($x \in A$).
• $x$, $B$ kümesinin de içinde olduğu için $x = a_k - a_i$ şeklinde yazılabilirdi (burada $a_i$, $A$ kümesinden bir sayı).

Bu denklemi düzenlersek:
$$x = a_k - a_i \implies x + a_i = a_k$$

Bu şu anlama gelir: $A$ kümesinden iki sayının ($x$ ve $a_i$) toplamı, yine $A$ kümesindeki başka bir sayıya ($a_k$) eşittir.
Fakat biz en başta kümenin "toplam içermeyen" bir küme olduğunu kabul etmiştik. Dolayısıyla $A$ ve $B$ kümelerinin hiçbir ortak elemanı olamaz.

Adım 4: Sonuç (Güvercin Yuvası)
Ortak elemanları yoksa, bu iki kümedeki toplam sayı adedi, evrensel sınırımızı ($a_k$) geçemez.

• $A$ kümesindeki eleman sayısı: $k$
• $B$ kümesindeki eleman sayısı: $k-1$
• Toplam farklı pozitif tamsayı adedi: $2k - 1$

Bu sayıların hepsi $a_k$'dan küçük veya eşittir (çünkü hepsi pozitif tamsayılardır ve en büyüğü $a_k$'dır). O halde:
$$2k - 1 \le a_k$$

Biz $a_k$'nın en fazla $101$ olabileceğini biliyoruz ($a_k \le 101$). Eşitsizliği birleştirelim:
$$2k - 1 \le 101$$
$$2k \le 102$$
$$k \le 51$$

Sonuç: Matematiksel olarak ispatladık ki, bu şartları sağlayan bir kümenin eleman sayısı ($k$) $51$'i asla geçemez. Yani $52$ elemanlı bir küme oluşturmak imkansızdır.

[Lokman Gökçe]

$B$ farklar kümesi oluşturarak yapılan bir çözüm Refail Alizade'nin Sonlu Matematik kitabında yer alıyordu ama daha kısa ve estetik biçimde ifade edilmişti. O çözümü de buraya eklemeye çalışalım. Yapay zeka bazen çözümü çok uzatarak anlatıyor böyle.