Монгол Бодлогын Сан
Эх хэлээрээ суралцаж, эх хэлээрээ мэдлэгээ түгээе.
ММО-09, Бодлого №5
Тус бүр нь $2n$-ээс ихгүй $n+1$ ширхэг натурал тоо $a_1,\dots,a_{n+1}$ өгчээ. Эдгээрийн аль нэг нь нөгөөгөө хуваана гэдгийг батал.
Бодлогын төрөл: Уламжлалт
Бодлогыг оруулсан: Балхүүгийн Батбаясгалан
Бодолт
Заавар:
Бодолт: $i\in[n+1]$ бүрийн хувьд $a_i$ тоог $a_i=2^{k_i}\cdot b_i$, $b_i$ - сондгой натурал тоо байхаар цор ганц аргаар бичиж болно. Нөгөө талаас $2n$-ээс хэтрэхгүй нийт $n$ ширхэг сондгой натурал тоо байх тул Дирихлейн зарчмаар $b_i$ тоонууд дотор хоёр ижил тоо бий. $b=b_\ell=b_k$ ба $\ell < k$ гэвэл $$a_\ell=2^{\ell}b, a_k=2^{k}b\Rightarrow a_\ell\mid a_k$$
болж нэг нь нөгөөгөө хуваадаг хоёр тоо олдов.