Комбинаторикын хялбар бодлогууд №2 (6/10)

Бодлогууд

Бодлого 1 (AIME 1986)

Тоон олонлогийн элементүүдийн нийлбэрийг уг олонлогийн нийлбэр гэж тодорхойлъё. \(S\) нь аль ч элемент нь 15-аас хэтэрдэггүй эерэг бүхэл тоонуудын олонлог байг. Мөн \(S\)-ийн аль ч хоёр үл огтлолцох дэд олонлогийн нийлбэрүүд нь хоорондоо ялгаатай байв. Тэгвэл эдгээр нөхцөлүүдийг хангах \(S\)-үүдээс хамгийн их нийлбэртэйг нь ол.

Бодлого 2 (China 1994)

\(n \ (n > 3)\) ширхэг хайрцагт нийтдээ дор хаяж дөрвөн чихэр байв. Алхам бүрд хоёр хайрцгийг сонгоод, тус бүрээс нь нэг нэг чихрийг авч гурав дахь хайрцаг руу хийх үйлдэл зөвшөөрөгдсөн бол ямар ч тохиолдолд бүх чихрийг нэг хайрцаг руу хийх боломжтой юу?

Бодлого 3

\(A_1A_2\dots A_{12}\) нь \(O\) төвтэй зөв арван хоёр өнцөгт байг. \(OA_iA_{i+1}, \ 1 \leq i \leq 12 \ (A_{13} = A_1)\) гурвалжнуудыг улаан, хөх, ногоон, эсвэл шар өнгөөр хөрш хоёр дүрс ялгаатай өнгөтэй байхаар будахаар болов. Нийт боломжит будалтын тоог ол.

Бодлого 4

\(2n\) хүн үдэшлэгт оролцов. Хэрвээ үдэшлэг дээрх хүн бүр тэгш тооны найзтай байсан бол тэгш тооны нийтлэг найзтай хоёр хүн олдоно гэж батал.

Бодлого 5 (IMO Shortlist 1996)

\((n - 1) \times (n - 1)\) квадрат \((n - 1)^2\) нэгж нүднүүдэд ердийн байдлаар хуваагдсан байв. Эдгээр нүднүүдийн \(n^2\) оройг улаан эсвэл хөх өнгөөр будахаар болов. Бүх нүд яг хоёр улаан оройтой байх ялгаатай будалтын тоог ол. (Хоёр будалтын хувьд ядаж нэг орой ялгаатай өнгөөр будагдсан байвал уг хоёр будалтыг ялгаатай гэж үзнэ.)

Бодлого 6 (China 1989)

Ширээн дээр \(2001\) зоос байв. Бүх \(i = 1, 2, \dots , 2001\)-ын хувьд, алхам бүрд хэн нэгэн заавал \(i\) ширхэг зоосыг эргүүлж харуулна (\(i\)-ын дараалал ямар ч байж болно). Ямар ч тохиолдолд бүх зоосыг дээшээ эсвэл доошоо харуулж болно гэж батал. Мөн бүх зоосыг дээшээ болон доошоо харуулах боломжтой тохиолдол байхгүй гэж батал.

Бодлого 7 (AIME 1983)

\(\{ 1, 2, \dots, n\}\) болон тус олонлогийн бүх хоосон биш дэд олонлогийн хувьд ээлжлэх нийлбэр-ийг дараах байдлаар тодорхойлъё: Элементүүдийг буурах эрэмбээр бичээд, хамгийн ихээс нь эхлэн дараачийн тоонуудыг нэмэх болон хасахаар ээлжилж тооцоолоход гарсан тоо. Жишээ нь, \(\{ 1, 2, 4, 6, 9\}\)-ын ээлжлэх нийлбэр нь \(9 - 6 + 4 - 2 + 1 = 6\) юм. \(n = 7\) үед бүх дэд олонлогуудын ээлжлэх нийлбэрүүдийн нийлбэрийг ол.

Бодлого 8

\(1998 \times 2002\) шатрын хөлгийн нүд бүр \(0\) эсвэл \(1\)-ийг агуулах ба мөр болон багана бүрд сондгой тооны \(1\) байв. Тэгвэл \(1\)-ийг агуулсан цагаан нүднүүдийн тоо тэгш гэж батал.

Бодлого 9 (AIME 1989)

\(S\) нь \(\{1, 2, 3, \dots, 1989\}\) олонлогийн дэд олонлог ба аль ч хоёр элементийнх нь зөрүү \(4\) эсвэл \(7\) биш байв. Тэгвэл \(S\) хамгийн ихдээ хэдэн элементтэй байж чадах вэ?

Бодлого 10 (St. Petersburg 1988)

Нийт \(119\) оршин суугч \(120\) айлын орон сууцанд амьдарч байв. Хэрвээ ямар нэгэн айлд ядаж \(15\) хүн амьдарч байвал тэр айлыг хэт их хүнтэй гэж үзнэ. Өдөр бүр хэт их хүнтэй айлын хүмүүс хоорондоо маргалдах ба бүгд өөр өөр айл руу нүүцгээдэг байв (тэгж байж тэд бие биеэсээ холдож чадна). Энэ үйл явц хэзээ нэг өдөр зайлшгүй дуусна гэж үнэн үү? Өөрөөр хэлбэл хэдэн өдрийн дараа хэт их хүнтэй айл олдохгүй гэж үнэн үү?