Processing math: 4%


ММО-38, 10-р анги

Монголын математикийн 38-р олимпиад, 10-р анги, 2002 он   

Бодлогын тоо: 6    Хугацаа: 540 мин


1. n ба k (nk) нь өгөгдсөн натурал тоонууд. A1,A2,,An нь A-ын дэд олонлогууд ба эдгээрийн дурын k-ийнх нь нэгдэл A ба k1-ийнх нь A-аас ялгаатай бол min-г ол.

Заавар Бодолт
Заавар.

Бодолт. B_i=\overline{A_i}=A\setminus A_i, i\in[n] гэе. Аливаа X_1,\ldots, X_t олонлогуудын хувьд \bigcup X_i=A\Leftrightarrow \bigcap \overline{X_i}=\varnothing тул бодлогын нөхцөлөөс B_i олонлогуудын аль ч k-1 нь ерөнхий элементтэй, аль ч k нь ерөнхий элементгүй болно.

X\subseteq[n] дэд олонлогийн хувьд S_{X}=\bigcap\limits_{i\in X} B_i гэе. Тэгвэл аливаа k-1 элементтэй X\subseteq[n] олонлогийн хувьд S_X\neq\varnothing, аливаа k элементтэй Y\subseteq[n] олонлогийн хувьд S_Y=\varnothing байна.

X_1\neq X_2 бол S_{X_1}\cap S_{X_2}=\varnothing болохыг харуулъя. Эсрэгээс нь x\in S_{X_1}\cap S_{X_2} гэе. X_1\neq X_2, |X_1|=|X_2|=k-1 тул i\not\in X_1, i\in X_2 байх i\in[n] оршин байна. Y=X_1\cup \{i\} гэвэл |Y|=k ба x\in S_Y\neq\varnothing болж зөрчил үүсч байна.

Иймд \binom{n}{k-1}\le \sum_{\substack{X\subseteq [n],\\ |X|=k-1}} |S_X|=\big|\bigcup_{\substack{X\subseteq [n],\\ |X|=k-1}} S_X\big|\le |A| байна.

Одоо ямар нэг \dbinom{n}{k-1} элементтэй A олонлогийн хувьд бодлогын нөхцөлийг хангах A_1,A_2,\ldots,A_n дэд олонлогууд олдохыг харуулахад хангалттай. A=\{X\colon |X|=n-1, X\subseteq[n]\} ба B_i=\{X\colon i\in X\in A\},\quad A_i=A\setminus B_i нь бодлогын нөхцөлийг хангана.


2. p өгөгдсөн анхны тоо. Анх координатын хавтгайн (0,0) цэг дээр байсан даам өөрийн байрлаж байгаа цэгээс p зайд орших бүхэл координаттай цэг рүү шилжих үйлдлийг хийх замаар (2002,38) цэгт очиж чаддаг p-ийн боломжит бүх утгыг ол.

Заавар Бодолт
Заавар.

Бодолт. p=2 үед очиж чадах нь илэрхий. Иймд бид нөхцөл хангах сондгой анхны p-үүдийг хайя.

Эйлер-Фермагийн теоремоор p=x^2+y^2 байхаар x, y\in\mathbb N олдох зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь p\equiv 1\pmod{4} юм. Мөн p=x^2+y^2\Rightarrow p^2=(x^2-y^2)^2+(2xy)^2 байна.

p=4k+3 үед зөвхөн (x,y)\to(x,y\pm p), (x,y)\to(x\pm,y) шилжилтүүд л боломжтой. Иймд (0,0)\to\dots\to(2002,38) бол p\mid 2002, p\mid 38 байна. Энэ зөвхөн p=2 үед л боломжтой. Гэтэл 2\neq 4k+3 юм.

p=4k+1 үед p^2=a^2+b^2 ба (a,b)=1 байх a, b\in\mathbb Z оршин байна. Иймд (x,y)\to(x+b,y+a)\to(x+b-b,y+a+a)=(x,y+2a)\qquad(1) (x,y)\to(x+a,y-b)\to(x+a-a,y-b-b)=(x,y-2b)\qquad(2) шилжилтүүд боломжтой юм. Нөгөө талаас (a,b)=1 тул au-bv=1 байх u, v\in\mathbb N тоонууд оршин байна. Иймд (x,y)\overset{u\times (1)}{\longrightarrow}(x,y+2a u)\overset{v\times (2)}{\longrightarrow}(x,y+2au-2bv)=(x,y+2) болно. Төстэйгээр (x,y)\to(x+2,y) гэж шилжүүлэх боломжтой тул (2002,38) цэгт очих боломжтой юм.

Хариу: p=2, p=4k+1 хэлбэрийн анхны тоо.


3. AB\neq BC байх ABC гурвалжинд багтсан тойрог AB ба BC талуудыг харгалзан M ба N цэгээр шүргэв. MC ба AN хэрчмүүд багтсан тойргийг S ба Q цэгээр огтлох бол MN, SQ, AC шулуунууд нэг цэгт огтлолцохыг батал.

Заавар Бодолт
Заавар.

Бодолт. SQ\cap AC=L гэж тэмдэглэе. \dfrac{CN}{NB}\cdot\dfrac{BM}{MA}\cdot\dfrac{AL}{LC}=1 болохыг харуулбал Менелайн теоремоор M, N, L гурван цэг нэг шулуун дээр орших тул бодлого бодогдоно.
Багтсан тойрог AC талыг P цэгт шүргэнэ гэе. \triangle NSC\sim\triangle MNC\Rightarrow\dfrac{MN}{NS}=\dfrac{MC}{NC} \triangle AQM\sim\triangle AMN\Rightarrow\dfrac{MN}{MQ}=\dfrac{AN}{AM} болно. Эндээс MN=\dfrac{NS\cdot MC}{NC}=\dfrac{MQ\cdot AN}{AM} буюу \dfrac{AM\cdot NS\cdot MC}{NC\cdot MQ\cdot AN}=1\qquad(*) MC\cap AN=O гэе. Тэгвэл \triangle MOQ\sim\triangle NOS\Rightarrow\dfrac{MQ}{NS}=\dfrac{QO}{OS} болно. Шүргэгч огтлогчийн чанараас \dfrac{AN}{AM}=\dfrac{AP}{AQ},\quad \dfrac{MC}{CN}=\dfrac{CP}{CS} байхыг (*)-д орлуулъя. Тэгвэл \dfrac{AQ}{AP}\cdot\dfrac{PC}{CS}\cdot\dfrac{SO}{OQ}=1\qquad(1) болно. Хэрэв QS\parallel AC байвал MN\parallel AC болох буюу энэ нь AB\neq BC гэдэгт зөрчинө.

Менелайн теоремоор \dfrac{CS}{SO}\cdot\dfrac{OQ}{QA}\cdot\dfrac{AL}{LC}=1\qquad(2) (1), (2) болон CP=CN, AP=AM-аас \dfrac{AL}{LC}\cdot\dfrac{CP}{AP}=1\Rightarrow \dfrac{AL}{LC}\cdot\dfrac{CN}{AM}=1 болох нь гарна. BN=BM учир \dfrac{CN}{NB}\cdot\dfrac{BM}{MA}\cdot\dfrac{AL}{LC}=1 болж батлах зүйл батлагдав.


4. Үржвэр нь яг 13 ялгаатай анхны тоон хуваагчтай байх ялгаатай 131 натурал тоо өгөгджээ. Тэдгээрээс үржвэр нь бүтэн квадрат байх 4 тоог сонгон авч болно гэж батал.

Заавар Бодолт
Заавар.

Бодолт. Зэргүүдийн тэгш сондгой нь чухал тул a=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\dots\cdot p_{13}^{\alpha_{13}}\to\alpha=(\alpha_1,\alpha_2,\ldots,a_{13})\pmod{2} буулгалтаар үүсэх векторуудыг авч үзье. Эдгээр векторуудын дунд нийлбэр нь (0,0,\dots,0)\pmod{2} байх 4 вектор олдвол тэдгээрт харгалзах тоонуудын үржвэр нь бүтэн квадрат байх нь ойлгомжтой.

\alpha+\beta хэлбэрийн нийлбэрүүдийг авч үзье. Нийт C_{131}^2=8515 нийлбэр зохиож болно. Нөгөө талаас ялгаатай векторын тоо 2^{13}=8192 тул Дирихлейн зарчмаар тэнцүү хоёр нийлбэр олдоно. Эдгээр нь \alpha+\beta, \gamma+\delta гэе. Хэрвээ \alpha, \beta, \gamma, \delta векторууд ялгаатай бол \alpha+\beta+\gamma+\delta\equiv(0,0,\dots,0)\pmod{2} тул бидний хайж байгаа тоонууд олдлоо. Хэрвээ \alpha=\gamma бол үлдэх векторуудаас яг ижил аргаар (C_{129}^2>2^{13} тул боломжтой) нийлбэр нь (0,0,\dots,0)\pmod{2} байх ялгаатай 4 дөрвөн вектор, эсвэл \mu=\nu хоёр вектор олж болно. Эхний тохиолдол нь өмнөх тохиолдолтой ижил ба хоёр дахь тохиолдолд \alpha+\gamma+\mu+\nu\equiv(0,0,\dots,0)\pmod{2} тул бодлого бодогдов.


5. a_0,a_1,a_2,\ldots гэсэн эерэг тоонуудын төгсгөлгүй дараалал өгөгдөв. 1+a_n\ge\sqrt[n]{2}a_{n-1} байх n дугаар төгсгөлгүй олон олдохыг батал.

Заавар Бодолт
Заавар.

Бодолт. Эсрэгээс нь n-ийн утгыг төгсгөлөг гэж үзвэл \exists N\forall (n>N): 1+a_n < a_{n-1}\cdot 2^{\frac1n}\qquad(*) үнэн байна. Хялбарчлах үүднээс N=0 гэж үзэж болно.

(*)-оос \begin{align*} 1+a_n&< a_{n-1}\cdot 2^{\frac{1}{n}}\\ 2^{\frac{1}{n}}+a_{n-1}\cdot 2^{\frac{1}{n}}&< a_{n-2}\cdot 2^{\frac{1}{n}+\frac{1}{n-1}}\\ 2^{\frac{1}{n}+\frac{1}{n-1}}+a_{n-2}\cdot 2^{\frac{1}{n}+\frac{1}{n-1}}&< a_{n-3}\cdot 2^{\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}}\\ \dots\dots&\dots\dots \end{align*} гэж гарах ба эдгээрийг нэмбэл 1+\sum_{i=0}^{n-3}2^{\frac{1}{n}+\frac{1}{n-1}+\dots+\frac{1}{n-i}}+a_n < a_1\cdot 2^{\frac{1}{n}+\frac{1}{n-1}+\dots+\frac{1}{2}} ба a_n>0 тул \sum_{i=0}^{n-3}2^{\frac{1}{n}+\frac{1}{n-1}+\dots+\frac{1}{n-i}} < a_1\cdot 2^{\frac{1}{n}+\frac{1}{n-1}+\dots+\frac{1}{2}} буюу \sum_{i=0}^{n-3} 2^{-\left(\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n-i-1}\right)} < a_1\qquad(*) болно. Одоо зүүн гар талын илэрхийлэл n\to+\infty үед +\infty рүү тэмүүлнэ гэж харуулбал +\infty = a_1 болж зөрчил үүсэх тул батлах зүйл маань батлагдана. S_n=\dfrac{1}{2}+\dfrac{1}{3}+\dots+\dfrac{1}{n} гэвэл (*)\Leftrightarrow \sum_{i=0}^{n-3}2^{-S_{n-i-1}} < a_1\Leftrightarrow \sum_{k=4}^{n+1} 2^{-S_k} < a_1 болно. Аливаа n\in\mathbb N-ийн хувьд \ln n+C_1 < S_n < \ln n+C_2 байх C_1, C_2 тоо олдоно гэдгийг ашиглая: 2^{-C_2}\cdot\sum_{i=2}^{n-1}2^{-\ln i}=\sum_{i=0}^{n-3}2^{-\ln (n-i-1)-C_2} < \sum_{i=0}^{n-3} 2^{-S_{n-i-1}} тул 2^{-\ln 2}+2^{-\ln 3}+2^{-\ln 4}+\cdots цуваа сарнина гэдгийг харуулахад хангалттай. Үнэндээ \dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}+\dots=e^{-\ln 2}+e^{-\ln 3}+e^{-\ln 4}+\cdots < 2^{-\ln 2}+2^{-\ln 3}+2^{-\ln 4}+\cdots тул дээрх цуваа сарнина.


6. ABC гурвалжны BC, CA, AB талын дунджууд нь харгалзан A_1, B_1, C_1. C_1A_1 хэрчим дээр \dfrac{C_1K}{KA_1}=\dfrac{BC+AC}{AC+AB} байх K цэгийг, A_1B_1 хэрчим дээр \dfrac{A_1L}{LB_1}=\dfrac{AC+AB}{BC+AB} байх L цэгийг тус тус авав. BK\cap CL=S бол \measuredangle C_1A_1S=\measuredangle B_1A_1S болохыг батал.

Заавар Бодолт
Заавар.

Бодолт.
\measuredangle C_1A_1B-ийн биссектрис A_1P нь S-ийг дайрна гэж харуулъя. Менелайн теоремоор \dfrac{AN}{NB}\cdot\dfrac{BS}{SM}\cdot\dfrac{MC}{CA}=1 ба \dfrac{NB}{AN}=\dfrac{LA_1}{BL}=\dfrac{b+c}{a+c}, \dfrac{CA}{MC}=1+\dfrac{AM}{MC}=1+\dfrac{C_1K}{KA_1}=\dfrac{a+c+2b}{b+c} тул \dfrac{BS}{SM}=\dfrac{b+c}{a+c}\cdot\dfrac{a+c+2b}{b+c}=\dfrac{a+c+2b}{a+c} байна. Одоо BM\cap A_1P=Q гээд \dfrac{BQ}{QM}=\dfrac{a+c+2b}{a+c} гэж харуулахад S\equiv Q болж батлагдана. AL_1\parallel A_1P тул \dfrac{BR}{BQ}=\dfrac{BL_1}{BA_1}=\dfrac{\frac{ac}{b+c}}{\frac{a}{2}}=\dfrac{2c}{b+c}\Rightarrow BR=\dfrac{2c}{b+c}\cdot BQ байна. AM=\dfrac{AM}{AC}\cdot b=\dfrac{C_1K}{C_1A_1}\cdot b=\dfrac{b(a+c)}{a+c+2b} тул биссектрисийн чанараар \dfrac{RM}{BR}=\dfrac{AM}{AB}=\dfrac{b(a+b)}{c(a+c+2b)} болно. Иймд \dfrac{BM}{BR}=\dfrac{RM}{BR}+1=\dfrac{b(a+b)+c(a+c+2b)}{c(a+c+2b)}\Rightarrow \begin{align*} BM&=\dfrac{b(a+b)+c(a+c+2b)}{c(a+c+2b)}\cdot BR\\ &=\dfrac{b(a+b)+c(a+c+2b)}{c(a+c+2b)}\cdot\dfrac{2c}{b+c}\cdot BQ \end{align*} тул \begin{align*} \dfrac{BM}{BQ}&=\dfrac{2(ab+b^2+ac+c^2+2bc)}{(a+c+2b)(b+c)}\\ &=\dfrac{2(b+c)(a+b+c)}{(a+c+2b)(b+c)}\\ &=\dfrac{2(a+b+c)}{a+c+2b}=1+\dfrac{QM}{BQ} \end{align*} болно. Эндээс \dfrac{QM}{BQ}=\dfrac{2(a+b+c)}{a+c+2b}-1=\dfrac{a+c}{a+c+2b} буюу \dfrac{BQ}{QM}=\dfrac{a+c+2b}{a+c} болж батлах зүйл батлагдав.