Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 2023 => Konuyu başlatan: matematikolimpiyati - Temmuz 03, 2023, 06:11:52 ös
-
$f : \{1,2,...,30\} \to \{1,2,...,30\}$ birebir bir fonksiyon olmak üzere, en fazla kaç tane $1 \leq a \leq 30$ tam sayısı için $f(1)f(2)...f(a)+1$ sayısı $31$ ile tam bölünür?
$\textbf{a)}\ 14 \qquad\textbf{b)}\ 15 \qquad\textbf{c)}\ 16 \qquad\textbf{d)}\ 29 \qquad\textbf{e)}\ 30$
-
Cevap: $\boxed{C}$
Fonksiyonun tanım ve değer kümesinin eleman sayıları eşit olduğundan ve birebir olduğundan, birebir ve örten olmalıdır. $31$ modunda bir ilkel kök alalım, $g$ olsun ($31$ asal sayı olduğundan ilkel kökü vardır hatta tek ilkel kök $3$'tür). $0\leq r_i\leq 30$ için $f(i)\equiv g^{r_i}\pmod{31}$ olsun ($(k,p)=1$ olan her $k$ tamsayısı sabit bir ilkel kökün kuvveti olarak yazılabilir). Ayrıca $g^{\frac{p-1}{2}}\equiv -1\pmod{p}$ olduğundan $g^{15}\equiv -1\pmod{31}$'dir. Yani $$\begin{array}{lcl}f(1)f(2)\cdots f(a)+1\equiv g^{r_1+r_2+\cdots+r_a}-g^{15}\pmod{31} & \iff & g^{r_1+r_2+\cdots+r_a}\equiv g^{15}\pmod{31} \\ & \iff & r_1+r_2+\cdots+r_a\equiv 15\pmod{30} \end{array}$$ olacaktır. Olabildiğince çok $a$ değeri için bunun sağlanmasını istiyoruz. Dolayısıyla bu şartı sağlayan iki $a$ değeri için bunlara $a_1<a_2$ dersek, $r_{a_1+1}+r_{a_1+2}+\cdots+r_{a_2}\equiv 0\pmod{30}$ olmalıdır. Bu $a$ değerlerinin sıklığını arttırmak için ara kısımda kalanı $0$ veya $(k,30-k)$ olarak seçebiliriz. Örneğin $$(r_1,r_2,r_3,r_4,\dots, r_{30})=(15,0,1,29,2,28,3,27,\dots,14,16)$$ olarak seçersek $a=1$ ve her çift $1\leq a\leq 30$ tamsayısı için $r_1+r_2+\cdots+r_{a}\equiv 15\pmod{30}$ olur, böylece $16$ tane $a$ değeri için $31\mid f(1)f(2)\cdots f(a)+1$ olan bir fonksiyon bulmuş oluruz.
Eğer $16$'dan fazla $a$ olabilseydi en az iki tane $r_i$'lerde $0$ kullanmamız gerekecekti, bu da birebirlikle çelişir. Cevap $16$'dır.
Ek olarak fonksiyonun kendisini de verelim, $f(1)\equiv 3^{15}\pmod{31}$, $f(2)=1$, $n\geq 3$ için $n$ tekse $f(n)\equiv 3^{\frac{n-1}{2}}\pmod{31}$ ve $n$ çiftse $f(n)\equiv 3^{31-\frac{n}{2}}\pmod{31}$ olarak seçilebilir.
-
Cevap: $16$.
Genel olarak bir $p$ tek asal sayısı için cevabın $\dfrac{p+1}{2}$ olduğunu gösterelim. $g(a)=f(1) f(2) \ldots f(a)+1$ diyelim. Bir $a$ sayısı için $p \mid g(a)$ ve $p \mid g(a+1)$ olursa $p \mid g(a+1)-g(a)$ ve dolayısıyla $f(a+1) \equiv 1 \pmod p$ olmalı. Yani ardışık tüm ikililere bakarsak, en fazla bir tane ikili için iki sayı birden $p$ 'ye bölünebilir, dolayısıyla en fazla $\dfrac{p+1}{2}$ sayı bu şartı sağlayabilir. Örnek için de $f(1)=p-1, f(2)=1$ ile başlayıp kalan sayıları $f(2k-1) \equiv \dfrac{1}{f(2 k)} \pmod p$ şeklinde gruplayabiliriz. Dolayısıyla $a=1,2,4 \ldots, p-1$ için $p \mid g(a)$ olur.
Kaynak: Tübitak 31. Ulusal Matematik Olimpiyatı Birinci Aşama Sınav Soru ve Çözümleri 2023