Математикийн батлах бодлого, теоремуудын бүтцийг ажиглавал " $A$ гэсэн өгөгдөл, нөхцөлөөс $B$ гэсэн дүгнэлт мөрдөн гарна" гэсэн логикийн импликац хэлбэртэй байдаг. Өөрөө хэлбэл

"$A$ бол $B$ байна" $\leftrightarrow$ "$A\Rightarrow B"$

хэлбэртэй. Жишээлбэл Пифагорын теоремыг авч үзье.

Теорем. (Пифагор) Тэгш өнцөгт гурвалжны катетууд $a, b$ урттай, гипотнуз нь $c$ урттай бол $$c^2=a^2+b^2$$ тэнцэтгэл биелнэ.

Энэ теоремын нөхцөл нь: $A$ = "$a,\ b$ катетууд, $c$ гипотнууз бүхий тэгш өнцөгт гурвалжин".

Теоремын дүгнэлт нь: $B$ = "$c^2=a^2+n^2$ гэсэн тэнцэтгэл" болж Пифагорын теорем $"A\Rightarrow B"$ = "$A$ гэдгээс $B$ мөрдөн гарна" гэж томьёологдоно.

Элементар логик буюу хэллэгийн алгебрт $A\Rightarrow B$ ба $\overline{B}\Rightarrow\overline{A}$ гэсэн логик томьёонуудын үнэний утгын хүснэгт адил. Өөрөөр хэлбэл $$\begin{array}{|cc|c|cc|c|} \hline A&B&A\Rightarrow B&\overline{B}&\overline{A} &\overline{B}\Rightarrow\overline{A}\\ \hline 0& 0&{1}&1& 1&{1}\\ \hline 0& 1&{1}&0& 1&{1}\\ \hline 1& 0&{0}&1& 0&{0}\\ \hline 1& 1&{1}&0& 0&{1}\\ \hline \end{array}$$ $A\Rightarrow B$ ба $\overline{B}\Rightarrow\overline{A}$ томьёонууд тэнцүү байдгийг бид мэднэ. Энд $\overline{X}$-ээр $X$ хэллэгийн үгүйсгэлийг тэмдэглэнэ.

Тэгэхээр, $A$ нөхцөлөөс $B$ дүгнэлт мөрдөн гарах нь үнэн гэдгийг батлах нь, $B$-ийн үгүйсгэлээс $A$-ийн үгүйсгэл мөрдөн гарах эсвэл бидний сайн мэддэг, математикт аль хэзээний нотлогдсон үнэн дүгнэлтийн үгүйсгэл мөрдөн гарахыг батлахтай логик утгаараа эквивалент юм. Баталгааны энэ аргыг "Эсэргээс нь батлах" гэнэ. Хамгийн анх Евклид өөрийн алдарт Elements гэсэн номондоо анхны тоонууд төгсгөлгүй олон бий гэдгийг батлахдаа эсэргээс нь батлах аргыг ашигласан гэдэг.

Бодлого 1. (Евклид[1]-ийн теорем) Анхны тоонууд төгсгөлгүй олон.

Баталгаа. Эсрэгээс нь төгсгөлөг тооны анхны тоо оршин байдаг тэдгээр нь $$p_1=2, p_2=3, p_3=5, p_4=7, ... , p_n$$ гэж үзье. Эдгээр анхны тоонуудыг ашиглан $$N=p_1\cdot{p_2}\cdot ... \cdot{p_n}+1$$ гэсэн тоо зохиоё. $N$ нь $p_1,...,p_n$-үүдээс өөр тул анхны тоо биш байх ёстой. Тиймээс, $N$-ийг хуваадаг $p$ гэсэн анхны тоо олдох ба $(p, N-1)=1$ байх ёстой. Өөрөөр хэлбэл $$(p,p_1\cdot{p_2}\cdot\cdot\cdot{p_n})=1$$ болж $p$ тоо $p_1, p_2, ...\ , p_n$ тоонуудтай харилцан анхны. Эндээс $$p\notin\{{p_1, p_2, ...\ , p_n}\}$$ болж зөрчилд хүрнэ. Зөрчил юунаас үүсэв? Мэдээж анхны тоонууд төгсгөлөг тоотой гэж үзсэнээс үүссэн.

Бодлого 2. Арван хүүхэд нийт $155$ ширхэг мөөг түүв.

• Аль нэг дөрвөн хүүхэд дор хаяж $64$ мөөг түүсэн гэдгийг батал.
• Хүүхдүүд ялгаатай тооны төөг түүсэн бол аль нэг дөрвөн хүүхэд дор хаяж $74$ мөөг түүсэн гэдгийг батал.

Бодолт. Хүүхдүүдийн түүсэн мөөгний тоог $a_1\ge{a_2} ... \ge{a_9}\ge{a_{10}}$ гэж үзье. Эсэргээс нь $$a_1+...+a_4< 64=4\cdot{16}$$ гэж үзье. Тэгвэл $a_4\le15$ байх ёстой. Иймд $$a_5+a_6+...+a_{10}\le{6\cdot15=90}$$ байх бөгөөд хүүхдүүдийн түүсэн нийт мөөг $64+90=154$ буюу $155$-аас цөөн болж зөрчил үүснэ. $(b)$ Хүүүхдүүдийн түүсэн мөөгийг $a_1>a_2> ... >a_9>a_{10}$ гэж үзье. Эсэргээс нь $$a_1+a_2+a_3+a_4< 74$$ $$74=20+19+18+17$$ гэж үзье. Тэгвэл $a_4\le{16}$ байх ёстой. Иймд $$a_5+a_6+a_7+a_8+a_9+a_{10}\le$$$$\le15+14+13+12+11+10=75$$ байх бөгөөд хүүхдүүдийн түүсэн нийт мөөг $74+75=149$-өөс цөөн болж зөрчил үүснэ.

Бодлого 3. Тойрог дээр $1$-ээс $100$ хүртлэх натурал тоонуудыг ямар нэг эрэмбээр бичжээ. Аль ч зэрэгцээ хоёр тооны ихээс багыг нь хассан ялгавар $30$-аас багагүй, $50$-аас ихгүй байж болох уу?

Бодолт. Тойрог дээр $1$-ээс $100$ хүртлэх тоонуудыг бодлогын нөхцөл биелсэн байхаар бичиж болдог гэе.

$26$-аас $75$ хүртлэх тоонуудыг "дундах" тоо бусдыг нь "захын" тоо гэж нэрлэе. Тэгвэл хоёр "захын" тоо зэрэгцэж бичигдсэн байж болохгүй. Учир нь Тэдгээрийн ялгаварын абсолют хэмжигдэхүүн эсвэл $25$-аас бага эсвэл $50$-аас их юм. "Захын" тоо нийт $25+25=50$ ширхэг бий. Иймд "дундах" тоо ба захын тоо ээлжлэн (сөөлжлөн) бичигдсэн байх ёстой. Гэвч $26$ гэсэн "дундах" тооны хажууд $76$ гэсэн ганц захын тоо л бичигдэж болно. Зөрчил!

Бодлого 4. "$2$ нүүдэлтэй шатар" гэж тоглогч бүр өөрийн ээлжиндээ дараалан $2$ удаа нүүх дүрэмтэй шатрын тоглолтыг нэрлэе. Тэгвэл $2$ нүүдэлтэй шатрын тоглоомд эхэлж нүүсэн шатарчин хожигдохгүй тоглож болно гэж батал.

Баталгаа. Эсрэгээс нь сүүлд нүүсэн шатарчинд хожих стратеги $S$ байдаг гэж үзье. (Энэ нь эхэлж нүүсэн шатарчин яаж ч тоглосон түүний нүүдлээс үл хамааран сүүлд нүүсэн шатарчин хожигдохгүйгээр өрөгөө өндөрлөх нүүдлүүдийн дараалал байгаа гэсэн үг юм.) Тэгвэл эхний шатарчин мориороо нэг нүүгээд, дараа нь морио буцааж анх байсан нүдэнд нь байрлуулая. Ингэхэд 2-р шатарчин эхэлж нүүх ёстой тоглоом болох ба эхний шатарчин хойшид $S$ стратегийг баримтлан тогловол хожигдохгүй болж зөрчил!

Бодлого 5. $n>3$ натурал тоо болог. Самбарт $(n-1)!$-аас бага $n$ ширхэг ялгаатай натурал тоонууд бичигдсэн байв. Энх эдгээр тоонуудын аль ч хоёрыг авч ихийг нь багад нь хуваахад гарах ноогдворыг (бүрэн биш ноогдвор) дэвтэртээ тэмдэглэнэ. Тэгвэл Энхийн бичсэн тоонууд дотор хоорондоо тэнцүү хоёд тоо байгаа гэж батал. (Жишээлбэл Энх $100$ ба $7$ тооныг сонгон авахад $100=7\cdot14+2$ учраас тэрээр $14$-ийг бичнэ.)

Баталгаа. Эсрэгээс нь Энхийн дэвтэртээ тэмдэглэсэн тоонууд ялгаатай гэж үзье. $$a_1< a_2< ... < a_n$$ байх $n$ ширхэг тоо самбарт бичигдсэн байг. $a_{j+1}$-ийг $a_j$-д хуваахад гарах бүрэн биш ноогдвор $q_j$ ($j=1, 2, ...\ , n-1$) болог. Тэгвэл $$a_{j+1}\ge{q_j}\cdot{a_j}$$ тэнцэтгэл биш биелэнэ. $q_1,\ q_2, ...,\ q_{n-1}$ ялгаатай натурал тоонууд тул $$q_1\cdot{q_2}\cdot ... \cdot{q_{n-1}}\ge(n-1)!$$ байна. Нөгөө талаас $$\dfrac{a_n}{a_1}=\dfrac{a_n}{a_{n-1}}\cdot\dfrac{a_{n-1}}{a_{n-2}}\cdot ... \cdot\dfrac{a_2}{a_1}\ge$$ $$\ge{q_1}\cdot{q_2}\cdot ... \cdot{q_{n-1}}\ge(n-1)!$$ буюу $$a_n\ge(n-1)!\cdot{a_1}$$ болж $a_n< (n-1)!$ гэж өгсөнд зөрчинө.

Бодлого 6. (М. Баасай. УМО-49 IV даваа) Сургууль дээр $18$ дугуйлан хичээлэлдэг бөгөөд сургуулийн сурагчид эдгээр дугуйлангуудад сонирхол сонирхлоороо суралцдаг. Дугуйлан бүр $10$ сурагчтай ба аль ч $11$ дугуйланг авахад (бүгд ялгаатай байх албагүй) тэдгээрт зэрэг суралцдаг сурагч олддог байв. Тэгвэл бүх дугуйланд суралцдаг "супер сурагч" олдоно гэж батал.

Баталгаа. Дугуйлангуудын олонлог $D=\{{D_1, D_2, ... , D_{18}}\}$ болог. Өгсөн нөхцөлөөс $$|D_1|=|D_2|= ... =|D_{18}|=10$$ юм. Түүнчлэн $j_1\ge{j_2}\ge ... \ge{j_{11}}$ ба $\forall{j_1, j_2, ...,\ j_{11}}\in{\{1, 2, ...\ , 18\}}$ хувьд $$D_{j_1}\cap{D_{j_2}}\cap ... \cap{D_{j_{11}}}\ne{\emptyset}$$ гэж өгөгдсөн. Эсрэгээс нь $D_1\cap{D_2}\cap ... \cap{D_{18}}=\emptyset$ гэж үзье. $D_1=\{x_1, x_2, ... , x_{10}\}$ дугуйланг сонирхвол $$x_j\notin{D_1\cap{D_2}\cap ... \cap{D_{18}}},\ j=\overline{1,10}$$ гэдгээс $x_j$-г агуулдаггүй $D_{(x_j)}$ гэсэн дугуйлан заавал олдоно. Энд $(x_j)\in{\{1, 2, ... , 10\}}$ юм. Тэгвэл $D_1\cap{D_{x_1}}\cap{D_{x_2}}\cap ... \cap{D_{x_{10}}}=\emptyset$ байна (Учир нь $\forall{x_j}\in{D_1}$ хувьд $x_j\notin{D_{(x_j)}}$). Энэ нь өгөгдөл нөхцөлд (аль ч 11 дугуйланг (бүгд ялгаатай байх албагүй) авахад огтлолцол нь хоосон биш гэдэгт) зөчинө. $\blacktriangleleft$ Жич. Энэ бодлогыг ерөнхий тохиолдолд $F=\{E_1, E_2, ... , E_s\}$ нь $X$ олонлогийн $r$ элементтэй дэд олонлогуудын бүл бөгөөд $F$-ийн аль ч $r+1$ элемент хоосон биш огтлолцдог бол $F$-ийн бүх элементүүдийн огтлолцол хоосон биш байна гэж томьёолж болно.

Бодлого 7. $P(x)=a_n\cdot{x^n}+a_{n-1}\cdot{x^{n-1}}+ ... +a_0$ гэсэн бүхэл коэффициенттэй дурын олон гишүүнтийн хувьд $P(0), P(1), P(2), ... $ дарааллын бүх гишүүн анхны тоо байж болохгүйг батал. (Энд $\deg P(x)=n\ge1.$)

Энэ бодлого нь товчхондоо сөрөг биш бүхэл тоонууд дээрх утгууд нь бүгд анхны тоо байх бүхэл коэффициенттэй олон гишүүнт олдохгүй гэдгийг батлахтай адил юм. Анх энэ бодлогыг аугаа их Леонард Эйлер[2] эсрэгээс нь батлах арга ашиглан баталсан байна.

Баталгаа. Эсрэгээс нь $\forall{k}\in{\mathbb{Z}}^+=\{0, 1, 2, ... \}$ тооны хувьд $P(k)$ анхны тоо байдаг $P(x)$ олон гишүүнт олддог гэж үзье. $P(0)=p,\ p$ анхны тоо болог. Эндээс $a_0=p$ ба аливаа $k\ge1$ натурал тооны хувьд

$$P(kp)=a_n\cdot(kp)^n+a_{n-1}\cdot(kp)^{n-1}+ ... +a_1\cdot(kp)+p=$$ $$=p\cdot(a_n\cdot{k^n}\cdot p^{n-1}+ ... +a_1\cdot{k}+1)$$

$$P(kp)=a_n\cdot(kp)^n+a_{n-1}\cdot(kp)^{n-1}+ ... +a_1\cdot(kp)+p=$$ $$=p\cdot(a_n\cdot{k^n}\cdot p^{n-1}+ ... +a_1\cdot{k}+1)$$

анхны тоо байх ёстой. Иймд

$$a_n\cdot{k^n}\cdot{p^{n-1}}+a_{n-1}\cdot{k^{n-1}}\cdot{p^{n-2}}+ ... +1=1$$

$$a_n\cdot{k^n}\cdot{p^{n-1}}+a_{n-1}\cdot{k^{n-1}}\cdot{p^{n-2}}+ ... +1=1$$

байхаас аргагүй. Өөрөөр хэлбэл $P(kp)=p,\ \forall{k}\in{\mathbb{N}}$ болно. Олон гишүүнт хувьсагчийн төгсгөлгүй олон утгууд дээр тэгцүү утгатай байвал тогтмол тоо байхаас өөр аргагүй гэдгийг хялбархан харж болно. (Энэ чанар зарим олон гишүүнтийн функционал тэгшитгэл бодоход түгээмэл хэрэглэгддэг.) Өөрөөр хэлбэл $$P(x_1)=P(x_2)= ...$$ байвал $P(x)=C$-const байна. Иймд манай олон гишүүнт $P(x)\equiv{p},\ \forall{x}\in{\mathbb{R}}$ болж $n=\deg P(x)\ge1$ гэдэгт зөрчинө.

Бодлого 8. (Долоо хоногийн бодлогууд-4) $f:\mathbb{Z}\rightarrow\{1, 2, 3\}$ ба $x, y\in{\mathbb{Z}},\ |x-y|\in{\{2, 3, 5\}}$ байх $x, y$-ийн хувьд $f(x)\neq{f(y)}$ байх $f$-функц олдохгүйг батал.

Баталгаа. Эсрэгээс нь тийм $f$ функц оршин байдаг гэж үзэе. $f(0)=a$ ба $f(5)=b$ болог. $a, b\in{\{1, 2, 3\}},\ a\ne{b}$. Тэгвэл $|5-2|=3, |2-0|=2$ гэдгээс $f(2)\ne{a, b}$ буюу $f(2)=C\ne{a;b}$ болно. Эцэст нь $|3-0|=3,\ |3-5|=2$ гэдгээс $f(3)=C$ байхаас өөр аргагүй. Иймд $f(2)=f(3)=C$ болох ба эндээс аливаа $x\in{\mathbb{Z}}$-ийн хувьд $f(x+2)=f(x+3)$ болж $f$ нь $\mathbb{Z}$ дээр тогтмол функц болоход хүрнэ. Энэ нь өгөгдсөн нөхцөлд зөрчинө. Иймд бодлогын нөхцөл хангах $f$ функц олдохгүй. Жич. Энэ бодлогыг өөрөөр: Бүхэл тоо бүрийг улаан, хөх, ногоон өнгийн аль нэгнээр, $|x-y|\in{\{2, 3, 5\}}$ байх аливаа $x, y$ бүхэл тоо бүр ялгаатай өнгөтэй байхаар будаж болох уу? гэж томьёолж болно.

1. $60$ сурагчийн аль ч $10$ сурагч дотор нэг ангийн $3$ сурагч олддог бол эдгээр $60$ сурагч дотор нэг ангийн $15$ сурагч байгаа гэж батал.
2. $1$гр, $2$гр,..., $100$гр жинтэй $100$ ширхэг туухайг ялгаатай $10$ хэсэгт хуваажээ. Тэгвэл аль хүнд жинтэй хэсэгт нь цөөхөн туухай байсан байж болох уу? (Өөрөөр хэлбэл харгалзан $a$ ба $b$ жинтэй дурын $2$ хэсгийн хувьд $a< b$ бол $a$ жинтэй хэсгийн туухайны тоо, $b$ жинтэй хэсгийн туухайны тооноос их байна.) 
3. Хавтгайн тэгш өнцөгт координатын системд зөв гурвалжны оройн цэгүүд болж чадах, бүхэл координаттай $3$ цэг олдох уу?
4. $a, b\in{\mathbb{Z}}$ ба аливаа $m, n$ натурал тоонуудын хувьд $a\cdot{m^2}+b\cdot{n^2}$ бүтэн квадрат бол $a\cdot{b}=0$ гэж батал.
5. Шинэ жилээр $10$ найз бие биедээ баярын мэндчилгээ дэвшүүлжээ. Аль ч хүн $5$ найздаа мэндчилгээ дэвшүүлсэн бол бие биедээ мэндчилгээ дэвшүүлсэн $2$ хүн олдоно гэж батал.
6. Кубын оройнууд дээр $1,2, ... ,8$ тоонуудыг дурын аргаар бичжээ. Төгсгөлийн цэгүүд дээр нь бичигдсэн тоонууд $3$-аас багагүй зөрөөтэй байх ирмэг олдоно гэж батал.
7. $\sqrt{2}+\sqrt{3}+\sqrt{5}$ -иррационал тоо гэж батал.
8. Дэс дараалсан $9$ бүхэл тоог, хэсэг бүрийн тоонуудынх нь үржэрүүд тэнцүү байхаар $2$ хэсэгт хувааж болохгүйг батал.
9. $a, b$ харилцан анхны натурал тоонууд бол $a, a+b, a+2b, ... $ арифметик прогрессд хос хосоороо харилцан анхны төгсгөлгүй олон гишүүн олдоно гэж батал.
10. Огторгуйн цэг бүрийг улаан, ногоон, хөх өнгийн аль нэгнээр буджээ. Дараах нөцлийг хангах нэг $C$ өнгө олдоно гэж батал. Үүнд $\forall{d}\in{\mathbb{R}^+}$-эерэг бодит тоонуудын олонлог авахад хоорондох зай нь $d$-тэй тэнцүү байдаг $C$ өнгөтэй $2$ цэг олдоно.
11. $5\mbox{м}^2$ талбайтай гэрт тус бүр $1\mbox{м}^2$ талбайтай $9$ ширхэг хивс дэлгэжээ. Тэгвэл давхцал хэсгийнх нь талбай $\dfrac{1}{9}$-ээс багагүй байх $2$ хивс олдоно гэж батал.
12. $f:\mathbb{N}\rightarrow\mathbb{N},\ f$-эрс өсдөг (өөрөөр хэлбэл $m, n\in{\mathbb{N},\ m< n}$ бол $f(m)< f(n)$) бөгөөд $\forall{m, n}\in{\mathbb{N}}$ хувьд $f(mn)=f(m)\cdot{f(n)}$ ба $f(2)=3$ байх $f$ функц олдохгүй гэж батал.