Tübitak Lise 1. Aşama 2024 Soru 28

[matematikolimpiyati]

$(x_1,...,x_{32})$ $32$-lisi $(1,2,...,32)$'nin bir permütasyonu olmak üzere, her $i=1,...,32$ için $y_i= \max \{x_1,x_2,...,x_i \}$ olsun. Tam olarak $2$ tane $i$ indisi için $y_i=x_i$ olmasını sağlayan $(x_1,x_2,...,x_{32})$ permütasyonlarının sayısının $29$ ile bölümünden kalan kaçtır?

$\textbf{a)}\ 0  \qquad\textbf{b)}\ 4  \qquad\textbf{c)}\ 9  \qquad\textbf{d)}\ 18  \qquad\textbf{e)}\ 27$

[geo]

Yanıt: $\boxed E$

Bir permütasyonda soldan sağa ilerlediğimizde en büyük eleman $k$ kez değişmişse bu permütasyona $k$-maksimal diyelim.
$n$ farklı sayının permütasyonları arasından $k$-maximal permütasyonların sayısını $P(n, k)$ ile gösterelim.
Soruda bizden $P(32,2)$ yi bulmamız bekleniyor.

$2,\dots, n$ ye ait permütasyonlara $1$ sayısını ekleyerek $2-$maksimal permütasyonlar üretmeye çalışalım.

• $2,\dots, n$ ye ait $k-$maksimal bir permütasyonu ele alalım.  Bu permütasyonun başına $1$ eklediğimizde permütasyon $(k+1)-$maksimal olur.
  
• $1.$, $2.$, $\dots$, $(n-1).$ terim sonrasına $1$ eklediğimizde yeni permütasyon yine $k-$maksimaldır.
  

O halde $2-$maksimal permütasyonların sayısı için $P(n, 2)=(n-1)P(n-1,2) + P(n-1,1)$ yazılabilir.

$P(n, 1)=(n-1)!$ olduğu kolayca görülebilir. ($n$ başta olmalı, diğer elemanların sırası önemsiz.)

Özyineli (recursive) denklemimizi birkaç kez çalıştıralım.

$P(32,2)=31P(31,2)+30! \equiv 2P(31,2) \pmod {29}$

$P(31,2)=30P(30,2)+29! \equiv P(30,2)  \pmod {29}$

$P(30,2)=29P(29,2)+28! \equiv 28! \pmod{29}$ olduğu için

$P(32,2) \equiv 2P(31,2) \equiv 2P(30,2) \equiv 2\cdot 28!\pmod {29}$ elde ederiz.

Wilson Teoremine göre $28! \equiv -1 \pmod {29}$ olduğu için $P(32,2)\equiv 2\cdot 28 ! \equiv -2 \equiv 27 \pmod {29}$ elde ederiz.

[Lokman Gökçe]

Yanıt: $\boxed{E}$

Çözüm [Lokman Gökçe]:
$y_1 = \max \{x_1\} = x_1$ dir. O halde bir başka $i>1$ için daha $y_i = x_i$ olmasını sağlamalıyız. Çözümün daha kolay anlaşılabilmesi için, genelleme yapmamıza izin verecek birkaç özel durumu inceleyeceğiz:


$\bullet$ $y_4 = x_4$ olsun. Bu durumda $y_2 = \max \{x_1, x_2\} \neq x_2 $, $y_3 = \max \{x_1, x_2, x_3\} \neq x_3 $ olmalıdır. Bu eşitsizliklerden $x_2 < x_1<x_4$ olur. Ayrıca $x_3<x_1$ veya $x_3 < x_2$ olmalıdır. Bu bize, $x_2$ ile $x_3$ ün kendi arasında yer değiştirebilecek değerlere sahip olduğunu gösteriyor. Yine $m\geq 5$ için $y_m \neq x_m$ olmalıdır. Bu ise $x_m < x_4$ olması anlamına gelir. Yani $x_4=32$ olup en büyük elemandır. $x_5, x_6, \dots , x_{32}$ sayılarının da kendi arasında yer değiştirebileceğini anlıyoruz. $y_4 = 32$ olan permütasyonların sayısı $\dbinom{31}{3}\cdot 2!\cdot 28!$ dir. Çünkü $31$ sayı arasından $3$ sayı seçiyoruz, bunların en büyüğü $x_1$ oluyor. Kalan $2$ tanesi $x_2$ ve $x_3$ olup $2!$ yolla belirleniyor.


$\bullet$ Son durum olan $y_{32}= x_{32} = 32$ durumuna bakalım. Bu durumda, $y_1 = x_1 = 31$ olup diğer $30$ sayı $30!$ yolla seçilebilir.


Genel olarak, $n\geq 1$ ve $y_{n+1} = x_{n+1} = 32$ olduğunda $1\leq i \leq n$ için $x_i$ sayılarının seçimini $\dbinom{31}{n}$ yolla yaparız. Bunların en büyüğü $x_1$ olmalıdır. Diğer $n-1$ sayının sıralanışı $(n-1)!$ yolla olur. $i>n+1$ için geriye kalan $31-n$ tane $x_i$ sayılarının sıralanışı da $(31-n)!$ yolla olur. $1\leq n \leq 31$ için bunların toplamına $S$ dersek
$$ S = \sum_{n=1}^{31} \dbinom{31}{n}\cdot (n-1)! \cdot (31-n)!$$
olur. $ \dbinom{31}{n} = \dfrac{31!}{n!\cdot (31-n)!}$ dir. Düzenlersek,
$$  S= \sum_{n=1}^{31} \dfrac{31!}{n} $$
elde ederiz. $n \neq 29$ için $ \dfrac{31!}{n} \equiv 0 \pmod{29}$ dur. O halde $S \equiv \dfrac{31!}{29} \pmod{29}$ elde ederiz. Wilson teoreminden, $28! \equiv -1 \pmod{29}$ olduğu kullanılırsa,
$$ S \equiv 31\cdot 30\cdot 28!\pmod{29} \equiv 2\cdot 1\cdot (-1) \pmod{29} \equiv 27 \pmod{29}$$
sonucuna ulaşılır.


Not: Bu çözüm bize, herhangi bir $m\geq 2$ pozitif tam sayısı için, istenen özellikteki $m$ uzunluğundaki permütasyonların sayısının açık denklem olarak,
$$ S= \sum_{n=1}^{m-1} \dfrac{(m-1)!}{n}$$ olduğunu da göstermektedir.