Зимний «Головастик» - 2016

Зимний «Головастик» - 2016

9-10 класс, бесконечность и периодичность

1. Имеется бесконечное количество карточек, на каждой из которых написано какое-то натуральное число. Известно, что для любого натурального числа n существуют ровно n карточек, на которых написаны делители этого числа. Доказать, что любое натуральное число встречается хотя бы на одной карточке.

2. Обозначим p(x) количество простых чисел, не превосходящих x. Конечно или бесконечно множество натуральных n, для которых n делится на p(√x)?

3. В бесконечной последовательности цифр между каждыми двумя последовательными цифрами можно вставить от 1 до k любых цифр. При каком наименьшем k можно такими операциями превратить любую последовательность в периодическую?

4. Можно ли в клетки бесконечного клетчатого листа выписать натуральные числа (каждое ровно по одному разу) так, чтобы любые два числа в одной строке и в одной строчке были взаимно простыми?

5. Можно ли в клетки бесконечного клетчатого листа выписать натуральные числа (каждое ровно по одному разу) так, чтобы сумма чисел в любом прямоугольнике 1Ч2004 делилась на 20042+1?

6. В бесконечном десятичном разложении числа a встречаются все цифры. Пусть v(n) – количество различных цифровых отрезков длины n, встречающихся в этом разложении. Докажите, что если при некотором n справедливо неравенство v(n) < n + 9, то число a – рационально.

7. По кругу стоит несколько коробочек. Каждая из них может быть пустой или содержать один или несколько шариков. Сначала из какой-то коробочки берутся все шарики и раскладываются по одному по часовой стрелке, начиная со следующей коробочки. На следующем ходу раскладывают шарики из той коробочки, в которую попал последний шарик на предыдущем ходу, и т. д. Докажите, что в какой-то момент повторится начальное расположение шариков.

8. В таблице 2015Ч2015 закрашены некоторые клетки. На первом шаге в каждую закрашенную клетку поставлено число, равное количеству закрашенных клеток, расположенных не ниже и не правее данной. На каждом следующем шаге в каждую закрашенную клетку пишется число, равное сумме чисел на предыдущем шаге в закрашенных клетках, которые не ниже и не правее. Докажите. Что обязательно встретится момент, когда все числа станут нечетными.

9. Два бога по очереди выписывают цифры бесконечной десятичной дроби. Первый своим ходом приписывает в хвост любое конечное число цифр, второй – одну. Если в итоге получится периодическая дробь, выигрывает первый, иначе – второй. Кто выиграет при наилучшей игре сторон?

10.  а) На бесконечной в обе стороны ленте записан текст на русском языке.  Известно, что в этом тексте число различных кусков из 15 символов равно числу различных кусков из 16 символов. Докажите,  что на ленте записан "периодический" текст.

Б) В бесконечной последовательности букв, имеющей период 11, есть два одинаковых 10-буквенных слова. Доказать, что их начала удалены друг от друга на расстояние, кратное 11

9-10 класс, немного алгебры

11. Сумма положительных чисел a, b и c равна 3. Докажите, что .

12. Назовем натуральное число неинтересным, если оно представляется в виде при натуральных a и b. Назовём натуральное число бесполезным, если оно не является количеством делителей никакого неинтересного числа. Найдите все бесполезные числа.

13. Для натуральных чисел a, b, c, d верно . Докажите, что число a2+b2+c2+d2 — составное.

14. Положительные рациональные числа a и b таковы, что a3+4a2b = 4a2+b4. Докажите, что число — квадрат рационального числа.

15. Докажите, что для любого натурального n верно

16. Докажите, что если для некоторых a, b, c, x, y, z , то x=y=z или a=b=c.

17. Пусть a, b, c – положительные числа, сумма которых равна 1. Докажите неравенство:

18. Сумма чисел a1, a2, a3, каждое из которых больше единицы, равна S, причем для каждого i = 1, 2, 3. Докажите, что .

19. . Рассматриваются всевозможные квадратичные функции такие, что a < b и для всех x. Какое наименьшее значение может принимать выражение

20. Докажите, что если 0<a<1 и 0<b<1, то

9-10 класс, задачи на непрерывность

1. Числовая функция f такова, что для любых x и y выполняется равенство f(x + y) = f(x) + f(y) + 80xy. Найдите f(1), если f(0,25) = 2.

2. Пусть f: A→A непрерывна, а g: A→A, h: A→A  разрывны. Обязательно ли непрерывна или разрывны следующие функции f(g), g(f), g(h)?

3.  Пусть f: (a, b)→(a, b) и g: (a, b)→(a, b) непрерывны и их значения совпадают во всех рациональных точках интервала (a, b). Докажите, что их значения совпадают и во всех точках интервала (a, b).

4. Можно ли утверждать, что квадрат разрывной функции – функция разрывная?

5. Пусть f – непрерывная функция, определенная на отрезке [0;1] такая, что f(0)=f(1)=0. Докажите, что на отрезке [0;1] найдутся две точки на расстоянии 0,1, в которых функция f(x) принимает равные значения.

6. Существует ли непрерывная функция, принимающая каждое действительное значение ровно 3 раза? .

7. Для каких б существует функция f : , отличная от константы, такая, что  f(б(x+y))=f(x)+f(y)?

8. Докажите, что на графике функции y=x3 можно отметить такую точку A, а на графике функции y=x3+|x|+1 - такую точку B, что расстояние AB не превышает 1/100.

9. О функции f(x), заданной на всей вещественной прямой, известно, что при любом a>1 функция f(x)+f(ax) непрерывна на всей прямой. Докажите, что f(x) также непрерывна на всей прямой.

10. Функция f(x) определена на всей прямой и обладает следующим свойством: для любого отрезка [a, b]  и для любого c, заключенного между значениями f(a) и f(b), уравнение f(x)=c имеет конечное, большее нуля количество корней на отрезке [a, b]. Верно ли, что f(x) непрерывна на этом отрезке?

9-10 класс, задачи на непрерывность-2

21. Функция F задана на всей вещественной оси, причём для любого x имеет место равенство: F(x+1)F(x)+F(x+1)+1=0. Докажите, что функция F не может быть непрерывной.

22. Пусть f(x) и g(x) – непрерывные функции, удовлетворяющие тождеству f(g(x))≡g(f(x)) на всей числовой оси. Доказать, что если уравнение f(x)=g(x) не имеет действительных решений, то их не имеет и уравнение f(f(x))=g(g(x)

23. Пусть f(x) – некоторый многочлен, про который известно, что уравнение f(x)=x не имеет корней. Докажите, что тогда и уравнение f(f(x))=x не имеет корней. Верно ли это для произвольной непрерывной функции?

24. Найти все непрерывные функции f: , f(f(f(x))) ≡ .

25. Известно, что область определения функции f(x) – отрезок [–1, 1], и f(f(x)) = – x при всех x, а ее график является объединением конечного числа точек и интервалов. Нарисовать график такой функции f(x). б) Можно ли это сделать, если область определения функции – интервал (–1, 1)? Вся числовая ось?

26.Найдите все непрерывные функции из ℝ в ℝ, удовлетворяющие соотношениям: f(x) = f(–x); f(x+1) = f(x)+1 при всех x�� ℝ.

27. Доказать, что не существует такой непрерывной функции f:, что f(x) рационально тогда и только тогда, когда f(x+1) иррационально.

28. Непрерывная функция f(x) удовлетворяет уравнению f(2x)=f(x). Найдите все такие функции.

29. Непрерывная функция f(x) такова, что для всех действительных x выполняется неравенство: f(x2)-(f(x))2≥1/4 . Верно ли, что функция f(x) обязательно имеет точки экстремума?

30. Пусть f(x) – непрерывная функция, определенная на единичной окружности. Докажите, что существуют две диаметрально противоположные точки a и b, что f(a)=f(b).

9-10 класс, бутерброды и блины

31. Постройте непрерывную функцию, имеющую на каждом отрезке бесконечно много максимумов и минимумов.

32. Найти все числа d, 0<d≤1, обладающие следующим свойством: если f(x) – произвольная непрерывная функция, определенная на [0,1], причем f(1)=f(0), то существует число x0, 0≤x0≤1-d, для которого f(x0)=f(x0+d).

33. Существует ли у функции y=x+[x] обратная? (если да – напишите её, если нет – докажите).

34. Докажите, что множество точек разрыва монотонной функции не более чем счетно.

35. Известно, что график некоторой функции обладает следующим свойством: хорда, соединяющая любые две точки графика, имеет с графиком хотя бы одну общую точку, отличную от концов. Докажите, что эта функция линейна.

36. Функция f(x) определена на всей прямой и обладает следующим свойством: для любого отрезка [a, b] и для любого c, заключенного между значениями f(a) и f(b), уравнение f(x)=c имеет конечное, большее нуля количество корней на отрезке [a, b]. Верно ли, что f(x) непрерывна на этом отрезке?

37. Лемма о бутерброде. На плоскости выбрали множество точек с корректно определённой площадью и прямую. Докажите, что существует прямая, параллельная данной, делящая выбранное множество на две равновеликие части.

38. Лемма о бутерброде-2. На плоскости выбрали множество точек с корректно определённой площадью. Покажите, что существует пара перпендикулярных прямых, делящая выбранное множество на четыре равновеликие части.

39. Лемма о блинах. На плоскости выбрали два множества точек с корректно определённой площадью. Докажите, что существует прямая, делящая оба множества на две равновеликие части каждое.

40. Найдите все непрерывные функции f: R → R такие, что 3f(2x) = f(x+1)+f(x) для каждого вещественного x.

9-10 класс, графы. Двусвязность

Ребро связного графа называется мостом, если при его удалении граф теряет связность. Вершина связного графа называется точкой сочленения,  если при ее удалении граф теряет связность.

1. a) В графе, имеющем хотя бы три вершины, нет точек сочленения.  Доказать, что между любыми двумя вершинами данного графа  существуют два пути, не имеющие общих вершин, кроме крайних;

Б) Несмежные вершины a и b таковы, что для любой вершины c существует путь из a в b, не проходящий через c. Доказать, что  между этими вершинами существуют два пути, не имеющие общих вершин, кроме крайних.

Связный граф называется двусвязным, если он содержит как минимум три вершины и при удалении любой вершины сохраняет связность.

2. а) Доказать, что в графе без мостов между любыми двумя вершинами существует два пути, не имеющие общих ребер;

б) Вершины a и b таковы, что для любого ребра C существует путь из a в b, не проходящий через C. Доказать, что существуют два пути из a в b, не имеющие общих ребер.

3. а) Ребра A, B и C таковы, что существует простой цикл, проходящий через  A и B, и существует простой цикл, проходящий через B и C. Доказать, что  существует простой цикл, проходящий через A и C; б) докажите, что в двусвязном  графе любые два ребра лежат на общем простом цикле.

4. В графе между любыми двумя вершинами существует простой путь четной длины. Доказать, что между любыми двумя вершинами существует простой путь нечетной длины.

5. В некотором государстве 1000 городов, из каждого из которых выходит не более девяти дорог, и от любого города можно добраться по дорогам до любого другого. Докажите, что можно выбрать 222 города так, чтобы любой замкнутый маршрут, проходящий только по этим городам, имел четную длину.

6. В государстве некоторые пары городов соединены беспосадочными (двусторонними) авиарейсами. Новый министр авиации решил раз в месяц перестраивать маршрутную сеть по следующему принципу: в следующем месяце будут соединены рейсами те и только те пары городов, для которых сейчас существует маршрут ровно с одной пересадкой. Через полгода выяснилось, что из любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что если реорганизация будет продолжаться, то и через год можно будет из любого города долететь до любого другого

7. В группе из нескольких человек некоторые люди знакомы друг с другом, а некоторые - нет. Каждый вечер один из них устраивает ужин для всех  своих знакомых, на котором знакомит их друг с другом. После того, как каждый человек устроил хотя бы один ужин, оказалось, что какие-то два человека еще не познакомились. Докажите, что на следующем ужине им тоже не удастся познакомиться.

8. В стране 192 города, из каждого города выходит по 10 дорог. а) Докажите, что можно найти 18 городов, попарно не связанных дорогами. б) Докажите, что если из любого города в этой стране можно попасть в любой  другой, то можно найти 20 таких городов.

9. В графе любое ребро входит в нечетное число треугольников. Докажите, что степени всех вершин в этом графе четны.

10. Докажите, что у двудольного графа с четным числом вершин и четным числом ребер количество остовных деревьев четно. (Остовное дерево – это подграф исходного графа, содержащий все его вершины и являющийся деревом.)

Указание: кроме остовных деревьев, рассмотрите множество подграфов, имеющих ровно один цикл, и установите между ними соответствие.

11.* В связном графе ровно k висячих вершин и нет вершин степени 2. Любой путь между любыми двумя висячими вершинами содержит не меньше четырёх ребер. Докажите, что в этом графе есть остовное дерево с не менее чем k+1 висячей вершиной.

Указание. Удалите все висячие вершины и рассмотрите оставшийся граф в двух случаях – когда он двусвязен и когда нет. В этом случае надо рассмотреть блоки и точки сочленения.