Прошедшая олимпиада

[Fsb4000]

Сегодня прошла олимпиада, если кто-нибудь захочет порешать, то вот задачки:

1)f(x) полином n-ой степени с целыми коэффициентами. Дано f(2a)=a, f(2b)=b. Вопрос: могут ли а и b быть оба целыми числами?

2) В выпуклом n-угольнике провели всевозможные диагонали. Никакие 3 диагонали не пересекаются в 1 точке. Найти количество точек пересечения диагоналей.

3) Решить 2f(x) +f($\frac {x}{x-1}$)= 2x, $\forall x\neq 1$

4) Сходится ли последовательность x_n= \sqrt{n} + \sqrt{n-1} - ( 1+ \frac {1}{\sqrt{2}}+\dots+\frac {1}{\sqrt{n}})

5) Найти наименьшее натуральное m, такое что во всяком множестве из m элементов, меньших 2009 найдутся 2 элемента делящиеся друг на друга.(Элементы - целые числа).

(П.С. условий с собой нет, восстанавливал задачи по памяти, если надо что то уточнить, спрашивайте.)
(П.П.С. сам решил 1,3,4 и написал что то подобное на решение на 2,5)

[Хорхе]

5) я думаю, имеются в виду все же натуральные числа. Это боян Эрдеша, а ответ -- 1005. Подсказка: 1004 числа указать легко; чтобы доказать для 1005, надо разбить числа от 1 до 2008 на 1004 группы, так что в любой паре чисел из одной группы одно делится на другое, и разбиение это донельзя простое.

[id]

1) Вычесть одно из другого и посмотреть на что делится каждый член, и сравнить с правой частью.
3) Можно через эквивалентность сходимость последовательности сходимости соотв. ряда.

[arqady]

Fsb4000 в сообщении #254844 писал(а):

2) В выпуклом n-угольнике провели всевозможные диагонали. Никакие 3 диагонали не пересекаются в 1 точке. Найти количество точек пересечения диагоналей.

$\binom{n}{4}$
B 3) вместо $x$ подставляем $\frac{x}{x-1}$ и решаем систему.

[Sasha2]

В третьей задаче можно воспользоваться легко доказываемым неравенством

$2*\sqrt{n+1}-2*\sqrt{2}+1<(1+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}})<2*\sqrt{n}-1$.
После чего ограниченность указанной в условии последовательности видна невооруженным глазом.
Далее, наверно также тривиально можно установить и монотонность.
Ну а далее уже дело техники.
Все это аккуратно расписать и решение готово.
Поправьте, если ошибаюсь.

[nn910]

Fsb4000 в сообщении #254844 писал(а):

3) Решить 2f(x) +f($\frac {x}{x-1}$)= 2x, $\forall x\neq 1$
(П.С. условий с собой нет, восстанавливал задачи по памяти, если надо что то уточнить, спрашивайте.)

По памяти там в правой части 3х,
2f(x) +f($\frac {x}{x-1}$)= 3x, $\forall x\neq 1$
что приводит к чуть более эстетичному ответу (можно начать как arqady)

[Fsb4000]

nn910 в сообщении #255119 писал(а):

Fsb4000 в сообщении #254844 писал(а):

3) Решить 2f(x) +f($\frac {x}{x-1}$)= 2x, $\forall x\neq 1$
(П.С. условий с собой нет, восстанавливал задачи по памяти, если надо что то уточнить, спрашивайте.)

По памяти там в правой части 3х,
2f(x) +f($\frac {x}{x-1}$)= 3x, $\forall x\neq 1$
что приводит к чуть более эстетичному ответу (можно начать как arqady)

Да и вправду 3x. А еще там в 1) a и b разные целые
Ну 1) и 3) почти очевидны.

5)В 5 у меня ответ 1006 получался. В множестве {2009, 2008, 2007, ...,1005} нельзя выбрать 2 таких числа. А в этом множестве вроде 1005 элементов. Ну а дальше я думал примерно как Хорхе, то же пытался разбить на 2 класса.


А в 4) я делал так: (По теореме Штольца)

$$\lim\limits_{n\to \infty}{\frac {2\sqrt{n} }{ 1+ \frac {1}{\sqrt{2}}+\dots+\frac {1}{\sqrt{n}} }}=1$$

$$\lim\limits_{n\to \infty}{\frac {\sqrt{n}+\sqrt{n-1} }{ \sqrt{n}+\sqrt{n-1}}=1$$

По свойству производных дробей.

$$\lim\limits_{n\to \infty}{\frac {\sqrt{n}+\sqrt{n-1} -2\sqrt{n}}{ \sqrt{n}+\sqrt{n-1}-(1+ \frac {1}{\sqrt{2}}+\dots+\frac {1}{\sqrt{n}})}=1$$

- Т.к.

$$\sqrt{n}+\sqrt{n-1} -2\sqrt{n}$$

-сходится то и

$${ \sqrt{n}+\sqrt{n-1}-(1+ \frac {1}{\sqrt{2}}+\dots+\frac {1}{\sqrt{n}})$$

сходится.

Вот вторую как сделать? Ну найдем количество диагоналей: n(n-3)/2. Ну найдем что у каждой диагонали точек пересечения k*m. Где k количество вершин лежащих в одной полуплоскости по отношению к диагоналям,а m- количество вершин лежащих в другой полуплоскости. А что дальше?

[nn910]

Fsb4000 в сообщении #255140 писал(а):

Вот вторую как сделать? Ну найдем количество диагоналей: n(n-3)/2. Ну найдем что у каждой диагонали точек пересечения k*m. Где k количество вершин лежащих в одной полуплоскости по отношению к диагоналям,а m- количество вершин лежащих в другой полуплоскости. А что дальше?

Доводится и этот путь,умением суммировать прогрессии и ряды из квадратов.
Но ответ arqady $C^4_n$Вам не подсказка? Какие бы мы ни взяли 4 вершины из n,...?

[Хорхе]

Fsb4000 в [url=http://dxdy.ru/post255140.html#p255140] писал(а):

5)В 5 у меня ответ 1006 получался. В множестве {2009, 2008, 2007, ...,1005} нельзя выбрать 2 таких числа. А в этом множестве вроде 1005 элементов. Ну а дальше я думал примерно как Хорхе, то же пытался разбить на 2 класса.

Так все-таки "меньших" или "не больших"? Число 2009 никак не меньше 2009. Если "не больших", то да, ответ 1006 (и такой же для 2010). Кстати, я не на два класса разбивал, а на 1004 (если "не больших", то на 1005).

[TOTAL]

Хорхе в сообщении #255159 писал(а):

Кстати, я не на два класса разбивал, а на 1004 (если "не больших", то на 1005).

Можно каждое из $m$ чисел разделить на максимальное число вида $2^k.$
Если $m$ больше числа нечетных чисел, не превосходящих $n,$ то после деления получим два одинаковых числа.