Тренировъчни задачи, 28МОМ Хавана, Куба

[krassi_holmz]

Това са задачи давани за подготовка на националния отбор за международната олимпиада в Куба през 1987г.

Пламен Пенчев - Комбинаторика. Редици. Аритметика.
1. Нека n е естествено число. Разжлеждаме множеството от всички n - торки [tex](a_1,a_2,...,a_n)[/tex] от цели числа, за които:
1)[tex]0\leq a_1 \leq ... \leq a_n \leq n[/tex]
2) [tex]a_1+a_2+...+a_n \equiv 0 (\mbox{mod } n)[/tex]
Да се докаже, че всяко от числата 0, 1, 2, ..., n-1 се среща еднакъв брой пъти в тези n-торки.

2. (Ramsey) Нека S е произволно множество с N елемента. С [tex]\{S,r\}[/tex] ще отбелязваме множеството от всички r - подмножества на S, като [tex]\{S,r\}[/tex] е разбито на два произволни, непресичаши се класа [tex]\alpha[/tex] и [tex]\beta[/tex] , а p, q и r [tex]p\geq r,q\geq r\geq 1[/tex] са произволни естествени числа. Тогава съществува число n(p,q,r), такова че, ако [tex]N\geq n(p,q,r)[/tex] , то или съществува подмножество [tex]A \sub S[/tex] с p елемента, за които [tex]\{A,r\}\sub \alpha[/tex] , или съществува подмножество [tex]B\sub S[/tex] с q елемента и [tex]\{B,r\} \sub \beta[/tex].

3. Дадено е естествено число p. Да се докаже, че съществува естествено число k, такова, че от произволни k точки в ръвнината, никои три от които не лежат на една права, може да се изберат p, които са върхове на изпъкнал p-ъгълник.

4. Дадено е множества М, състоящо се от m точки в равнината. Да се докаже, че за всяко естествено число k, съществува естествено число n(k) такова, че при [tex]m\geq n(k)[/tex] от точките на M може да се изберат k триъгълника, имащи ъгъл >120 градуса.

5. (Ив. Проданов) Равнината е разбита на четири множества [tex]A_1, A_2,A_3,A_4[/tex], за всяко от които съществуват пет транслации, такива, че образите на [tex]A_i i=1,2,3,4[/tex] при петте транслации нямат обща точка. Да се докаже, че дадените множества не покриват равнината.

6. Дадено е множеството M={1,2,...,k}. От [tex]M^n[/tex] се избират две подмножества P и Q, такива, че за всеки две n-торки [tex]\alpha \in P[/tex] и [tex]\beta \in Q , \alpha = (a_1,a_2,...,a_n), \beta = (b_1,b_2,...,b_n)[/tex] , съществува естествено число i, за което [tex]a_i = b_i[/tex] . Да се докаже, че или [tex]|P|\leq k^{n-1}[/tex], или [tex]|Q|\leq k^{n-1}[/tex].

7. Съществува ли естествено число n, такова, че всяко рационално число xe(0,1) може да се представи като сума на n реципрочни на естествени числа?

9. Дадена е редицата [tex]x_1=x_2=0,x_3=2,x_{n+1} = x_{n-2}+2x_{n-1}[/tex]. Да се докаже, че за всяко естествено число m съществуват два съседни члена на редицата, различни от 0, които се делят на m.

19. Да се докаже, че минималният брой диагонали, които могат да се разположат изцяло в един n-ъгълник M е равен на n-3.
20. Какъв най-голям брой върхове има неизпъкнал n-ъгълник, в който не може да се прекара нито един диагонал, разположен изцяло в М. [/tex]

[Реклама]

[martosss]

я кажи за 19-та задача какво значи да разположиш един диагонал изцяло в един п-ъгълник? Впрочем след М трябва да има запетая на същата задача

П.П.

[krassi_holmz]

[Who_cares123456]