Tübitak Lise 2. Aşama 2023 Soru 5

[geo]

$23$ gerçel sayıdan oluşan bir kümenin, boş olmayan ve elemanlarının çarpımı rasyonel sayı olan alt kümelerinin sayısı tam olarak $2422$ olabilir mi?

[Metin Can Aydemir]

Bu tarz sorularda genelde soruyu çözebilmek için cevabı tahmin etmek gerekir. Eğer yanlış tahmin üzerine çözüm elde edilmeye çalışılırsa, süre yetişmeyecek ve büyük olasılıkla o sorudan puan alınamayacaktır. $2422$ sayısının özel bir anlamı olmamasından dolayı cevabın evet olacağını tahmin edebiliriz çünkü $2023$ veya $2023^{2022}$ gibi sayılar verilseydi, çözümün sayıdan bağımsız olabileceği sonucuna varabilirdik. Ancak $2422$ sayısı belli ki özel bir inşa yönteminin sonucunda çıktığı için sorulmuş. Böyle bir kümeyi varsayarak, nasıl inşa edebileceğimize bakalım.

Kümenin elemanlarını $i=0,1,\dots,22$ için $2^{\frac{2^i}{n}}$ olarak seçersek elemanları çarpımının rasyonel olması için kullanılan terimlerin üslerinin toplamının tamsayı olması gerekir. Yani $$n\mid 2^{a_1}+2^{a_2}+\cdots 2^{a_k}$$ şeklinde olmalıdır. $n$ sayısının herhangi bir katının $2$'nin farklı kuvvetlerinin toplamı olarak tek şekilde yazılabileceğini biliyoruz. Dolayısıyla $$n,2n,3n,\dots,2422n$$ sayılarını $1,2,2^2,\dots, 2^{22}$ sayılarını kullanarak elde edebilmeli ancak $2423$'ü elde edememeliyiz. $2^m$'ye kadar olan $2$'nin kuvvetleri kullanılarak sadece $2^m-1$'e kadar olan tüm sayıları elde edebiliriz. Dolayısıyla $$2422n\leq 2^{23}-1<2423n\implies \frac{2^{23}-1}{2423}<n\leq \frac{2^{23}-1}{2422}$$ olacak şekilde bir $n$ varsa, bu $n$ için yukarıdaki formatta seçtiğimiz küme istenilen şartı sağlayacaktır. Bu aralıkta $n=3463$ sayısı olduğundan, böyle bir küme vardır.

Kaynak: Tübitak Lise 2. Aşama Resmi Çözümler 2023

Not 1: Son kısımdaki $n$'nin varlığının gösterilmesi yeterlidir. Dolayısıyla böyle bir $n$'yi elle hesaplamak yerine, ki sayılar bence bunu yapmak için çok da büyük değil, sınırlarının arasındaki farkın $1$'den büyük olduğu gösterilebilir. Çünkü $b-a>1$ ise $(a,b)$ aralığında kesin bir tamsayı vardır. Resmi çözümde de bu şekilde çözüm tamamlanmıştır.

Not 2: AoPS gibi forumlarda istenileni sağlayan farklı formattaki bazı kümeler de bulunmuş. O kümelerin neden o şekilde seçilmesi gerektiğine dair açıklamalarla birlikte burada farklı çözüm olarak paylaşabiliriz.

[geo]

Metin Can Aydemir'in bahsettiği AoPS forumundaki çözümlerden biri sınavın birincisi Barış Koyuncu'ya ait. Barış Koyuncu, derincesi Youtube kanalında kendisini çözüme götüren yöntemi detaylıca anlatıyor.

Barış Koyuncu, ilgili kümelerden birini $\{e, 2e, 3e, \dots, 12e, e^{-7}, 2e^{-7}, e^{-8}, e^{-10}, 2e^{-10}, \ldots, 5e^{-10}, e^{-11}, e^{-12}, e^{-31}\}$ olarak örneklendiriyor.
O çözümünün biraz daha genelini (Barış Koyuncu'nun AoPS'taki çözümününden esinlenerek) Metin Can Aydemir ile birlikte şöyle yaptık:

Öncelikle kümede hiç rasyonel sayı olmaması gerektiğini gözlemleyelim. $a\in\mathbb{Q}$ sayısı bu kümenin içerisinde ise $a$'nın olmadığı, çarpımı rasyonel olan altkümelere, $a$ eklendiğinde yine çarpımı rasyonel olacaktır. Eğer $a\neq 0$ ise kalan $22$ reel sayıdan kaç tane altküme elde edebiliyorsak, $a$'yı ekleyerek bir o kadar alt küme daha elde edebilirdik. Bunların dışında $a$'nın tek başına olduğu kümeyi de düşünürsek, alt küme sayısı tek sayı olacaktır, $2422$ olamaz. Eğer $a=0$ ise $a$'yı içeren her altkümenin elemanları çarpımı rasyonel olacaktır. Bu da en az $2^{22}$ tane altküme demektir. Bu da istenileni sağlamaz.

Dolayısıyla hiçbir rasyonel sayı içermeyen bir küme oluşturmalıyız. Çarpımlarının rasyonel olmasından dolayı sayıları $\alpha$ transcental sayısı ve $a,k\in\mathbb{Z}$ için $a\cdot \alpha^k$ formatında seçmeyi düşünebiliriz. Burada $\alpha$'yı rastgele bir irrasyonel seçmemizin sebebi $\alpha^k$'nın irrasyonel kalmasını istememizdir. Örneğin $\alpha=\sqrt{2}$ seçersek $\alpha^2$ rasyonel olacaktır. $a$'nın da elemanları farklı yapmak dışında bir kullanımı yoktur çünkü çarpıma herhangi ekstra bir şey katmayacak ancak elemanları birbirinden farklı seçebilmemizi sağlayacaktır. $23$ irrasyonel için üslere $k_1,k_2,\dots,k_{23}$ diyelim. $k_i$'lerin farklı olması gerekmez ama $0$'dan farklı olmalıdır.

Bu elemanların çarpımının rasyonel sayı olması demek, üslerinin toplamının $0$ olması demektir. Dolayısıyla $(k_1,k_2,\dots,k_{23})$ tamsayı $23$-lüsünün tam olarak $2422$ tane alt dizisinin elemanları toplamının $0$ olmasını istiyoruz. Bunun için de $k_i$'lerden pozitif olanlar ile negatif olanları birbirlerini nötrleyecek şekilde seçmeliyiz. İki işaret için de sayıları rastgele seçersek, $2422$'yi hesaplamak karmaşıklaşacağından tüm pozitifleri $+1$ seçebiliriz. Böylelikle, $-K$'yı nötrlemek demek $K$ tane $+1$'den seçmek demek olacak.

$k =\lfloor (n+1)/2 \rfloor$ olmak üzere; $N$ tane $1$, $x_0$ tane $-k$, $x_1$ tane $-k-1$, $\ldots$, $x_{n-k}$ tane $-n$ sayısından oluşan sayı dizisini ele alalım.
Toplamları $0$ olacak şekilde bu dizinin alt dizisini seçmek istersek; sadece $1$ adet negatif sayı, bu negatif sayı neyse bir o kadar da $1$ sayısı seçmemiz gerekir.
$x_0 + x_1 + \dots + x_{n-k} \leq 23 - n$ olmak üzere; bu şekilde dağılımların sayısı için $\displaystyle \sum_{i=0}^{n-k}\binom{n}{k + i}\binom{x_i}{1} = 2422$ olmalı.

Örneğin, $n=11$ için $\binom{11}{6} = 462$, $\binom{11}{7} = 330$, $\binom{11}{8} = 165$, $\binom{11}{9} = 55$, $\binom{11}{10} = 11$, $\binom{11}{11} = 1$  eşitliklerini kullanarak $462 \cdot 5 + 55 \cdot 2 + 1 \cdot 2 = 2422$ elde ederiz.

Bu durumda $20$ elemanlı $\{e, 2e, \dots, 11e, e^{-6}, 2e^{-6}, \dots, 5e^{-6}, e^{-9}, 2e^{-9}, e^{-11}, 2e^{-11}\}$ kümesinin tam olarak $2422$ altkümesi için elemanlar çarpımında $e$ nin üssü $0$ a eşit olacaktır. (Geri kalan $3$ elemanı $e^{-12}, e^{-13}, e^{-14}$ şeklinde seçebiliriz.)

Barış Koyuncu'nun örneğini bizim çözümümüzdeki yaklaşımla verirsek:
$n=12$, $\binom{12}{7} \cdot 2 + \binom{12}{8} \cdot 1 + \binom{12}{10} \cdot 5 + \binom{12}{11} \cdot 1 + \binom{12}{12} \cdot 1$  $= 792\cdot 2 + 495 \cdot 1 + 66 \cdot 5 + 12 \cdot 1 + 1\cdot 1 = 2422 $, dolayısıyla aradığımız küme $\{e, 2e, \dots, 12e, e^{-7}, 2e^{-7}, e^{-8}, e^{-10}, 2e^{-10}, \dots, 5e^{-10}, e^{-11}, e^{-12}\}$ olacaktır. (Geri kalan $1$ elemanı $e^{-13}$ şeklinde seçebiliriz.)

Bilgisayar yardımıyla, bu yaklaşımdaki tüm çözümleri bulabiliriz.

$n=10$ için:

$\begin{array}{c|c|c|c|c|c}
\binom{10}{5} = 252 & \binom{10}{6} = 210 & \binom{10}{7} = 120 & \binom{10}{8} = 45 & \binom{10}{9} = 10 & \binom{10}{10} = 1 \\
\hline 6 & 2 & 4 & & 1 & \\
\hline 8 & & 3 & 1 & & 1
\end{array}$

$n=11$ için:

$\begin{array}{c|c|c|c|c|c}
\binom{11}{6} = 462 & \binom{11}{7} = 330 & \binom{11}{8} = 165 & \binom{11}{9} = 55 & \binom{11}{10} = 11 & \binom{11}{11} = 1 \\
\hline  &6  &2  &2  &  &2 \\
\hline  &7  &  &2  &  &2 \\
\hline  2&2  &5  &  &1  &2 \\
\hline  2&3  &3  &  &1  &2 \\
\hline  2& 4 &  &3  &1  &2 \\
\hline  2& 4 & 1 &  & 1 &2 \\
\hline  3& 3 &  &  & 4 & 2\\
\hline  4&  & 3 & 1 & 2 & 2\\
\hline  4&  1&  1&  1& 2 & 2\\
\hline  5&  &  &2  &  &2
\end{array}$

$n=12$ için:

$\begin{array}{c|c|c|c|c|c|c}
\binom{12}{6} = 924 & \binom{12}{7} = 792 & \binom{12}{8} = 495 & \binom{12}{9} = 220 & \binom{12}{10} = 66 & \binom{12}{11} = 12 & \binom{12}{12} = 1 \\
\hline  &  & 4& 1 & 3 & 2 & \\
\hline  &  & 4& 2 &  &  & 2 \\
\hline  & 1&  & 7 & 1& 2 & \\
\hline  & 1& 2 & 2 & 3 & & 2 \\
\hline  & 1& 3&  & 2 & 1 & 1 \\
\hline  & 2& 1&  & 5 & 1 & 1 \\
\hline 1 &  & 2 & 1 & 4 & 2 & \\
\hline 1 &  & 2 & 2& 1&  & 2 \\
\hline 1 &  & 3 &  &  & 1 & 1 \\
\hline 1 & 1&  & 2 & 4 &  & 2 \\
\hline 1& 1& 1&  & 3& 1& 1 \\
\hline 2&  &  & 1 & 5 & 2 &  \\
\hline 2&  &  & 2 & 2 & & 2 \\
\hline 2&  & 1&  & 1& 1& 1
\end{array}$

Üsler toplamının sıfır yapıldığı bu yaklaşım, literatürde subset sum olarak geçiyor.
Geeks For Geeks sitesinde yer alan kod örneklerini,

var arr = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -6, -6, -6, -6, -6, -9, -9, -11, -11]

şeklinde çalıştırdığımızda, boş küme de sayıldığı için $2423$ elde ediyoruz. Bir nevi çözümde bulduğumuz değerlerin doğrulaması yapılmış oldu.

[geo]

AoPS forumundaki çözümlerden biri resmi çözümdeki yaklaşıma ait bir örnek barındırıyor.


$A = \left \{2^{\frac{2^{10}}{n}}, 2^{\frac{2^{9}}{n}}, \ldots, 2^{\frac{2^{0}}{n}} \right \}$, $B = \left \{2\cdot 2^{\frac{2^{10}}{n}}, 2\cdot 2^{\frac{2^9}{n}}, \ldots, 2\cdot 2^{\frac{2^{0}}{n}} \right \}$, $C = \left \{ 3\cdot 2^{\frac{2^k}{n}}  \right \}$ ve $S = A \cup B \cup C = \left \{ 2^{\frac{2^0}{n}}, 2^{\frac{2^1}{n}}, \ldots, 2^{\frac{2^{10}}{n}}, 2\cdot 2^{\frac{2^0}{n}}, 2\cdot 2^{\frac{2^1}{n}}, \ldots, 2\cdot 2^{\frac{2^{10}}{n}}, 3\cdot 2^{\frac{2^k}{n}} \right \} $ kümelerini ele alalım.

$S$ kümesinin herhangi bir altkümesini ele aldığımızda, $A$ kümesinin elemanlarından hangilerinin bu alt kümede var olup olmadığını büyükten küçüğe sıralı bir listede $1$ ve $0$ kullanarak ifade ettiğimizde $11$ basamaklı $$ (00000000000)_2, (00000000001)_2, \dots , (11111111111)_2 $$ sayılarından birini elde edeceğiz. Bu sayıya $a$ diyelim.

Benzer şekilde $b$ ve $c$ sayılarını tanımlayalım. $0\leq a \leq 2047$, $0\leq b \leq 2047$ ve $c = 0$ veya $c = 2^k$ olacaktır.
$S$ nin herhangi bir altkümesini aldığımızda elemanların çarpımının rasyonel olması için $2^{\frac an} \cdot 2^{\frac bn} \cdot 2^{\frac cn} = 2^{\frac {a+b+c}n}$ ifadesinin rasyonel olması gerekir.
$a+b+c = n$ denkleminin çözüm sayısı $2422$ olacak şekilde $n$ ve $k$ sayıları bulabilirsek soruyu çözmüş olacağız.
$a+b = m$ denkleminin çözüm sayısı; $(2047, m - 2047)$, $(2046, m - 2046)$, $\ldots$, $(m-2047, 2047)$ çiftlerinin sayısı $2047 - (m-2047) + 1 = 4095 - m$ dir.

$c=0$ iken $m=n$ ve dolayısıyla $4095 - n$ çözüm gelecektir.
$c=2^k$ iken $m = n - 2^k$ ve dolayısıyla $4095 - n + 2^k$ çözüm gelir.
Bu durumda toplamda $8190 - 2n + 2^k = 2422$ çözüm gelmesi gerekir. $k=1$ için $n = 2885$ olacaktır.

O halde $S = \left \{ 2^{\frac{2^0}{2885}}, 2^{\frac{2^1}{2885}}, \ldots, 2^{\frac{2^{10}}{2885}}, 2\cdot 2^{\frac{2^0}{2885}}, 2\cdot 2^{\frac{2^1}{2885}}, \ldots, 2\cdot 2^{\frac{2^{10}}{2885}}, 3\cdot 2^{\frac{2^1}{2885}} \right \} $ kümesi aradığımız kümelerden biridir.