В общем, я доказал по индукции, что $%n$% окружностей делят плоскость максимум на $%n(n-1)+2$% частей.
У множества $%2^n$% подмножеств.
То есть, если я не ошибаюсь, решение сводится к "доказать, что $% n^2-n+2=2^n$% только при $%n=1,2,3$%."
Если нарисовать графики двух функций, то видно, что вроде как неоткуда взяться четвертой общей точке.
Но как это строго доказать?

задан 11 Июн '15 14:54

изменен 11 Июн '15 17:20

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Если показать что при n>3 обе функции будут строго возрастать, при чем одна быстрее другой, то ясно что они не встретятся. Как это сделать?

(11 Июн '15 15:08) R0b
10|600 символов нужно символов осталось
0

Речь идёт о доказательстве неравенства $%2^n > n^2-n+2$% при $%n\ge4$%. При $%n=4$% это очевидно, а при $%n\ge5$% оно следует из более сильного неравенства $%2^n > n^2$%, доказываемого по индукции. При $%n=5$% получается $%32 > 25$%. Пусть доказано, что $%2^k > k^2$% при некотором $%k\ge5$%. Тогда $%2^{k+1}=2\cdot2^k > 2k^2 > (k+1)^2$% за счёт того, что $%k^2\ge5k > 2k+1$%.

ссылка

отвечен 11 Июн '15 15:01

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×476
×65

задан
11 Июн '15 14:54

показан
259 раз

обновлен
11 Июн '15 16:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru