Хотын олимпиадад дэвшигдсэн нэгэн бодлогын бодолтууд
Огноо: 2018-03-29,
Нийтэлсэн: Балхүүгийн Батбаясгалан
Нийтэлсэн: Балхүүгийн Батбаясгалан
Бодлого. $[n]=\{1,2,\dots,n\}$ олонлогийн ялгаатай хуваалтын тоог $A_n$ гэе. Жишээлбэл $n=3$ үед $$1|2|3\quad 12|3\quad 13|2\quad 1|23\quad 123$$ гэсэн 5 ялгаатай хуваалт байгаа тул $A_3=5$ юм. Түүнчлэн нэг хэсэгт дараалсан 2 тоо ороогүй байх $[n]$ олонлогийн ялгаатай хуваалтын тоог $B_n$ гэе. $n\ge 1$ үед $A_{n}=B_{n+1}$ болохыг батал.
Миний өөрийн бодолт. $n\ge 1$ гэе. $A(n, k)$ нь $[n]$ олонлогийг хоосон биш яг $k$ ширхэг олонлогт хуваах хуваалтын тоо байг. Тэгвэл $$x^n=\sum_{j=1}^n A(n, j)x(x−1)\dots (x−j+ 1)$$ байдаг. $B(n, k)$ нь $[n]$ олонлогийг хуваалтын аль ч хэсэгт нь дараалсан 2 тоо ороогүй байхаар хоосон биш яг $k$ ширхэг олонлогт хуваах хуваалтын тоо байг. $$F_x=\{f:[n+1]\to[x+1]\mid\forall j\colon f(j)\neq f(j+ 1)\}$$ гэвэл $$|F_x|= (x+ 1)x^n=\sum_{j=2}^{n+1}B(n+ 1, j)(x+ 1)x\dots (x+ 1−j+ 1)$$ байх тул $$x^n=\sum_{j=1}^n B(n+ 1, j+ 1)x(x−1)\dots (x−j+ 1)$$ байна. Иймд $A(n, k) =B(n+ 1, k+ 1)$ байна. Эцэст нь $A_n=\sum_{k\ge 1}A(n, k)$, $B_{n+1}=\sum_{k\ge 1}B(n+ 1, k)$ ба $B(n+ 1,1) = 0$ тул $A_n=B_{n+1}$ байна.
УБ хотын аварга багш Б. Ганбатын бодолт. Бодолтын санаа нь $A_{n+1}$ ба $B_{n+1}$ тоонуудыг $A_k, k=1\dots {n}$ тоонуудаар илэрхийлэх юм.
$[n+1]$ олонлогийн $\{n+1\}$ элемент дангаараа орсон хуваалтын тоо нь $A_{n}$. $S_i$ нь $n+1$ тоо $i$-тоотой нэг хэсэгт орсон хуваалтууд бол $$|\bigcup\limits_{i=1}^{n} S_i|=\sum|S_i|-\sum|S_iS_j|+\sum|S_iS_jS_k|-\cdots$$ ба $i_1,i_2,\dots,i_k,n$ тоонууд нэг хэсэгт орсон хуваалтуудыг тоолохдоо эдгээр тоонуудыг нэг мэтээр сэтгэн тоолж болох тул $$|S_{i_1}S_{i_2}\dots S_{i_k}|=A_{n-k}$$ байна. Иймд $$A_{n+1}=A_{n}+nA_{n-1}-C_{n}^2A_{n-2}+C_{n}^3A_{n-2}-\cdots$$ буюу $$A_{n}=A_{n+1}-nA_{n-1}+C_{n}^2A_{n-2}-C_{n}^3A_{n-3}+\cdots$$ Одоо $M_i$-аар $[n+1]$ олонлогийн $i,i+1$ тоонууд нэг хэсэгт орсон хуваалтын тоог тэмдэглэвэл ядаж нэг дараалсан тоонууд нэг хэсэгт орсон байх $[n+1]$ олонлогийн хуваалтын тоо нь $$|\bigcup\limits_{i=1}^{n} M_i|=\sum|M_i|-\sum|M_iM_j|+\sum|M_iM_jM_k|-\cdots$$ Дараалсан $\ell$ тоог нэг гэж үзэх бүрд тоонуудын тоо $\ell-1$-ээр цөөрч байна гэж үзэж болох тул $$|M_{i_1}M_{i_2}\dots M_{i_k}|=A_{n-k}$$ Иймд $$|\bigcup\limits_{i=1}^{n} M_i|=nA_{n-1}-C_{n}^2A_{n-2}+C_{n}^3A_{n-3}-\cdots$$ Нөгөө талаас $$B_{n+1}=A_{n+1}-|\bigcup\limits_{i=1}^{n} M_i|=A_{n+1}-nA_{n-1}+C_{n}^2A_{n-2}-C_{n}^3A_{n-3}+\cdots$$ тул $A_n=B_{n+1}$ болох нь батлагдлаа.
Улсын дархан аварга Б. Ганбилэгийн бодолт. Гол санаа нь миний бодолтынхтой адил $A(n, k) =B(n+ 1, k+ 1)$ гэж баталсан. Үүний тулд $$A(n,k)=A(n-1,k-1)+kA(n-1,k),$$ $$B(n+1,k+1)=B(n,k)+kB(n,k+1)$$ рекуррент харьцаануудыг ашиглая.
Үнэндээ нь $A(n,k)$ нь Стерлингийн II төрлийн тоо тул $A(n,k)=A(n-1,k-1)+kA(n-1,k)$ рекуррент харьцаа биелнэ.
$[n+1]$ олонлогийн дараалсан хоёр тоо нэг хэсэгт ороогүй $k+1$ хэсэгтэй хуваалтууд нь $n+1$ тоо ганцаараа нэг хэсэгт орсон бол $B(n,k)$, өөр ямар нэг тоонуудтай хамт орсон бол $k$ тоо орсон хэсэгт нэмэгдэхгүй тул $kB(n,k+1)$ байна.
Түүнчлэн $n=1$ үед $A(1,k)=B(2,k+1)$ тул индукцээр $A(n,k)=B(n+1,k+1)$ болно.
Энэ бодлогыг ММО-53-ийн сүүлийн даваанд зориулж зохиосон бөгөөд интернэтээр хайлт хийсний эцэст нэг төрлийн сонгодог бодлого болохыг нь олж мэдсэн юм. Сонгодог бодолт нь Ганбилэг багшийнхтай ижилхэн байсан.
Мөн энэ бодлогыг Сант сургуулийн багш Урангоо бодсон боловч зарим нэг тодорхойлолтыг буруу өгсөн зэргээс болж оноогоо хасуулсан болно.
Энэ нийтлэлийг 9601 удаа уншсан.
Уншигчдын сэтгэгдэл
Nymtogtokh Toochin 2018-04-09 14:01
woow