САЩ - задачи от олимпиади

1. В една група от n момчета и n момичета могат да бъдат сключвани бракове. За всяко момиче или момче може да има няколко подходящи партньори за брак. Да се докаже, че всички могат да сключат брак с подходящ партньор тогава и само тогава, когато за всяко естествено k ≤ n всяка група от k момчета има общо поне k подходящи партньори.

2. Дадена е безкрайна редица от естествени числа
            a₁, a₂, ..., a_n,...,
която удовлетворява следните условия:
      a₀ ≤ a₁ ≤ a₀ + 20,   a₁ ≤ a₂ ≤ a₁ + 20, ...
Да се докаже, че безкрайната редица дасетична дроб 0,а₀а₁a₂..., получена с последователно записване на числата a₀, a₁, a₂.... едно след друго след десетичната запетая, е ирационално число.

3. Разглеждаме множеството от единични кръгиве, всеки два от които нямат обща вътрешна точка и са разположени в ивицата между две дадени успоредни прави. Ще казваме, че кръговете образуват k-облак, ако всяка права, която пресича ивицата, пресича поне k от кръговете. Да се докаже, че всяка ивица, съдържаща 2-облак, има ширина, по-голяма или равна на 2 + √3.

4. Редицата a₁, a₂, ..., a_n,..., от естествени числа е дефинирана рекурентно с равенствата a₁ = 2 и a_n+1 = a_n² - a_n + 1. Първите няколко члена на редицата са a₁ = 2, a₂ = 3, a₃ = 7, a₄ = 43, a₅ = 1807. Да се докаже, че числата a₁, a₂, ..., a_n,... са две по две взаимно прости.

5. Губернаторът на Усконсин има градина с форма на кръг с радиус R. Той иска да засади в нея екзотични дървета. За да представляват те красива гледка, разстоянието между всеки два от тях не трябва да бъде по-малко от R. Какъв е максималният брой дървета, които може да засади губернаторът, и как трябва да бъдат разположени?

6. Какъв може да бъде броя на върховете на изпъкнал многоъгълник, който може да бъде разрязан на квадрати и равностранни триъгълници с една и съща дължина на страната?

7. Да се намери такова 10-цифрено число d = d₀d₁...d₉, че броят на нулите в записа му да е равен на d₀, броят на единиците на d₁, ..., броят на деветките да е равен на d₉.

8. Да се определи видът на триъгълник, който може да бъде разрязан на три еднакви триъгълника.
Отговор: Има три възможности за общия връх на трите триъгълника:
1) Той е вътре в триъгълника - тогава триъгълника е равностранен;
2) Той е върху страна на триъгълника - тогава триъгълника е правоъгълен;
3) Той съвпада с някой от върховете на триъгълника - невъзможно.

9. Даден е триъгълник АВС е обединение на едно крайно множество F от триъгълници. Ако два различни триъгълника от F имат обща точка, тяхното сечение е или общ връх, или обща страна. Всеки от върховете на триъгълниците от фамилията F е оцветен с един от цветовете син, ервен, жълт. Върхът А е червен, В е син, а С е жълт. Всеки връх V на триъгълника F, който лежи на страната АВ е или червен, или син; ако V е връх върху ВС, той е или син, или жълт; и ако V е върху АС, то той е или жълт, или червен. Да се докаже, че ако това правило е спазено и за останалите триъгълници от F, то броят на триъгълниците в F, които имат по един червен, син и жълт връх е нечетен.

10. Нека L е множеството от n отсечки, с всеки три от които може да се построи триъгълник. Една двойка отсечки от L ще наричаме изключителна, ако едната е повече от два пъти по-дълга от другата. Какъв може да бъде максималният брой изключителни двойки в L?

11. Аз си намислих две различни естествени числа и казах на Па и Сам за това. На сам казайх сумата на тези числа, а на Пам - произведението им. След това чух следния диалог:
Пам: Аз не мога да определя числата.
Сам: Сумата им е по-малка от 25.
Пам: Сега аз знам кои са числата.
Сам: Сега аз също знам кои са числата.
Кои са намислените от мен числа?
Отговор: 5 и 10.

12. Нека F_n означава n-тия член от редицата на Фибуначи. (F₁ = 1, F₂ = 1 и F_n+2 = F_n+1 + F_n за n = 1, 2,...).
а) Да се докаже, че
        F₁ + F₂ + ... +F_k = F_k+2 - 1.
б) Да се намери и докаже подобна формула за сумата
            F₁² + F₂² + ... + F_k².

13. Да се докаже, че за всяка степен 2^m на числото 2 има кратно (т.е. число от вида .2^m), в десетичното представяне на което не участва цифрата 0.

14. Нека S е такова множество от 101 различни естествени числа, че средното аритметично на всеки 10 от тях е естествено число. Да се докаже, че в S има елемент, който е по-голям от 1000.

15. Колко са целочислените решения на системата
            |x + y + z = 1
            ||x| + |y| + |z| = 1 000 000?
Колко ще бъдат тези решения, ако второте уравнение се замени с уравнението |x| + |y| + |z| = 1000001?

16. Две точки Р и Q лежат във вътрешността на правилния тетраедър ABCD. Да се докаже, че PAQ < 60°.

17. Дадени са три различни цели числа a, b, и c и нека Р е полином с цели коефициенти. Да се докаже, че не е възможно да са в сила едновеменно равенствата P(a) = b, P(b) = c и P(c) = a.

18. а) Всяко поле от шахматната дъска с размери 4х7 е оцветено или в бяло, или в черно. Да се докаже, че за всеки начин на оцветяване на дъската има правоъгълник, образуван от полетата на шахматната дъска, чиито четири ъглови полета са от един и същи цвят.
б) Да се посочи черно бяло оцветяване на шахматната дъска с размери 4х6, в което ъгловите полета на всеки такъв правоъгълник не са от един и същи цвят.

19. Да се намерят всички целочислени решения на уравнението
            a² + b² + c² = a²b².
Отговор: a = b = c = 0.

20. Да се намери максималният обем на правоъгълен тетраедър PABC (т.е. APB = BPC = CPA = 90°), ако сумата на всичките му ръбове е равна на фиксирано число S.
Отговор: $V_{max} = \frac{S^3}{162(7 + 5 \sqrt{2})}$