close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Экстремум – поиск и обоснование
Лекции В.В.Шеломовского
Использование оценок
Лекция 6
Оценки часто используют для решения задач с поиском экстремума. Для того, чтобы
нечто доказывать и до того требуется понять, в чём смысл проблемы, которую требуется
решить. Рассмотрим пример.
1
1. Специфический многочлен
Дан многочлен P(x) = a2nx2n + a2n−1x2n−1 +...+ a1x + a0, у которого каждый коэффициент ai
принадлежит отрезку [m, m + 1], m > 5. При каком минимальном n у такого многочлена может
найтись действительный корень?
Размышляем. Коэффициенты рассматриваемого многочлена близки к одинаковым
числам, поэтому многочлен P(x) близок к многочлену F(x) = a2n(x2n + x2n−1 +...+ x + 1).
F(0)= F(–1) = a2n , F(1) = (2n + 1)a2n. Если x > 0, F(x) монотонно возрастает с ростом х, F(x)> 0.
x 2 n+1−1
Для отрицательных икс запишем многочлен в форме F ( x)=a 2 n
. Для любых иксов
x−1
F(x) > 0, причём если |x|  2, то F(x) определяет первый член числителя, он быстро возрастает
по модулю при удалении х от единицы, F(x) ≈ x2n.
Многочлен P(x) близок к F(x), поэтому корень он может иметь только при х близких к
–1. P(–1) = a2n – a2n−1 + a2n−2.– a2n−3+...+ a2 – a1 + a0 = a2n – (a2n−1 – a2n−2) – (a2n−3– a2n−4) – (a1 – a0).
Члены в скобках не больше единицы, значит, P(–1)  a2n – n  m – n. Корень, равный –1,
может возникнуть если n  m.
В ходе решения нужно показать, что при n = m существуют такие коэффициенты аi, что
уравнение имеет корень, и доказать, что при n < m многочлен P(x) всегда положителен.
Решение. Если n = m, a2k = m, a2k+1 = m + 1, то многочлен P(x) имеет корень:
P(–1) = a2n – a2n−1 + a2n−2.– a2n−3+...+ a2 – a1 + a0 = a2n – (a2n−1 – a2n−2) – (a2n−3– a2n−4) – (a1 – a0) = 0.
Докажем, что если n < m, то многочлен P(x) всегда положителен.
Если x  0, то Р(x)  Р(0) = a0  m > 0.
Пусть x < 0, F(x) = m(x2n + x2n−2 +...+ x2 + 1) > 0, G(x) = (m+1)(x2n−1 + x2n−3 +...+ x) < 0.
Заметим, что T(x) = Р(x) – F(x) + G(x) < Р(x).
T(x) = (a2n – m) x2n + (m +1 – a2n−1)(–x)2n−1 +...+ (a2 – m) x2 + (m + 1 – a1)(–x) + (a0 – m)  0.
Действительно, коэффициенты при чётных степенях переменной неотрицательные, как и
сама степень. Коэффициенты при нечётных степенях переменной неотрицательные, а
степени минус икса также положительные. Значит, и при отрицательных x < 0, Р(x) > 0.
Ответ: n = m.
1.a 1,a. 2013-14, 11 класс, задача 7
Дан многочлен P(x) = a2nx2n + a2n−1x2n−1 +...+ a1x + a0, у которого каждый коэффициент ai
принадлежит отрезку [100, 101]. При каком минимальном n у такого многочлена может
найтись действительный корень?
Ответ: n = 100.
2
Числа без нулей делятся на часть себя
Найдите два наибольших натуральных числа, не содержащих нулей в своей записи и
делящихся на каждое из чисел, образованных их последними одной, двумя и так далее
цифрами. Например, 816 делится на 16 и 6: 816 = 5116 = 1366.
Размышляем. Рассмотрим часть задачи. Расчленим число, содержащее k + 1 цифру, на
число, определяемое первой цифрой a10k и число b из k цифр, получаемое из искомого
путём отбрасывания первой цифры. Тогда искомое число имеет вид:
N = a  10k + b = a  5k  2k + b, где 10k > b > 10k–1.
k
k
Значит, a⋅5 ⋅2 делится на b, причём b не содержит нулей, то есть не делится на 10.
Значит, на b делится один из множителей числа a5k2k, который не делится на 10. Таких
множителей всего два:
– число a  5k делится на b, причём цифра a  9 нечётная и не 5, то есть 1, 3, 7 или 9;
– число a  2k делится на b, причём цифра a  9 не равна 5.
В первом случае a  5k  b > 10k–1  45  5a > 2k–1  6  k.
Во втором случае a  2k  b > 10k–1
 18  2a > 5k–1
 2  k. В этом случае
искомое число будет не больше, чем 1000, поэтому сначала анализируем первый случай.
N a⋅5 k⋅2k +b a⋅5 k k
Отношение искомого числа к числу b равно
=
≥
⋅2 +1≥2k +1 .
b
b
b
Проверяем наибольшее возможное значение k = 6. Тогда a5k  b > 10k–1, a56  105, 5a > 32.
Если a = 9, то b > 105 = 100000 делитель числа 956 = 140625. Значит, b = 140625, N =
9140625, но это число содержит нуль, что противоречит условию.
Если a = 7, то b > 105 = 100000 делитель числа 756 = 109375. Значит, b = 109375, N =
7109375, но это число содержит нуль.
Проверяем значение k = 5. Тогда a5k  b > 10k–1, a55  104, 5a > 16. 2k + 1 = 33.
Если a = 9, то b > 104 = 10000 делитель числа 955 = 28125. Значит, b = 28125, N = 928125.
Однако это число не делится на 8125.
Если a = 7, то b > 10000 делитель числа 755 = 21875. Значит, b = 21875, N = 721875.
721875 = 3321875 = 3851875 = 825875 = 962575. Оно удовлетворяет условию.
Проверяем значение k = 4. Тогда a5k  b > 10k–1, a54  103, 5a > 8.
Если а = 9, то b > 103 = 1000 делитель числа 954 = 5625. Если b = 5625, то N = 95625,
N = 175625 = 153625. Оно удовлетворяет условию. Оба искомых числа найдены.
Ответ: 721875 = 3321875 = 3851875 = 825875 = 962575 =1443755;
95625 = 17  5625 = 153  625 = 3825  25 = 19125  5.
3
Коэффициенты бинома
Найдите, при степень m такую, что коэффициент при хm в разложении бинома: (1 + ax)n
по степеням икс является наибольшим.
Решение: Коэффициенты при хm в разложении (1 + ах)n = bmхm имеют вид bm = аmCmn.
Найдём отношение коэффициентов при двух соседних степенях (m + 1) и m:
bm +1 a m +1 C m+1
(n−m)!⋅m! a(n−m)
n!
= m nm =a⋅
⋅
=
.
bm
(n−m−1)!⋅( m+1) !
n!
m+1
a Cn
an−1
an−1
an−1
, то b m+1=b m , если m<
, то b m+1 >b m , если m>
, то b m+1 <b m .
Если m=
a+1
a+1
a+1
an−1
an−1
, m 2=
+1 или оба одновременно.
Ответ: один из коэффициентов m1=
a+1
a+1
[
] [
]
Например, для разложения (1 + 2x)8 наибольший коэффициент 1792 при x5 и x6, так как
m=
an−1 2⋅8−1
=
=5 .
a+1
2+1
4
Рыбы в пруду и французы в горах
Требуется оценить число N рыб в пруду. Для этого из пруда случайным образом
извлечены M рыб, помечены и отпущены в пруд. Через некоторое время, извлекли вторую
группу из n рыб и установили, что в этой группе m отмеченных. Считая, что пойманные в
первый раз рыбы ко второму разу равномерно перемешались с не пойманными, найдите
максимально вероятное количество рыб в пруду.
Решение: Известно, что количество способов выбрать случайным образом n объектов из
N данных равно СNn. Значит, число способов извлечь случайным образом группу n рыб из N
рыб, обитающих в пруду, равно СNn. Количество способов извлечь ровно m рыб из М
отмеченных равно СMm. Количество способов извлечь ровно n – m
рыб из N – M не
C n−m
N −M . Два последних события независимы, поэтому число способов
отмеченных равно
извлечь случайным образом именно ту группу, которая была реально извлечена, равно
m
M
C ⋅C
n−m
N −M
. Вероятность извлечь её равна: P M,n,m ( N )=
C mM C n−m
N− M
C nN
.
Для поиска максимума этой величины, найдём отношение
PM , n, m ( N  1)
PM , n, m ( N )

m nm
m nm
CM
C N 1 M CM
CN  M
( N  1)( N  1  m  M  n)
:

n
n
( N  1  n)( N  1  M )
C N 1
CN
Это выражение равно единице при N 
Mn
 1 . При меньших N оно больше единицы,
m
то есть вероятность растёт по мере роста N. При больших оно меньше единицы, то есть
 Mn 
убывает с ростом N. Значит, при целом Nˆ  
 искомая вероятность максимальная. Это
 m 
число и принимается, как оценка для искомой величины N.
Ответ:
[ ]
Mn
.
m
5
Выражение с корнями
Найдите наибольшее целое число, которое может получиться, если в выражении:
√* √ * √*... √* с числом радикалов n  3 заменить каждую звёздочку числом из набора 2 , 2 ,
1
2
23,…, 2n, используя каждое число ровно один раз.
Размышляем: Чем больше степень корня, тем меньше становится число, которое
√ √ √
√
n
n−1
... 23 √ 22 √ 2 . Однако,
больше, чем единица. Значит, самое большое число это a n= 2 2
оно не целое. Значит, нужно переставлять числа под последними радикалами и искать целое.
Решение: Чтобы получить наибольшее число заданного вида требуется упорядочить
степени двойки в порядке убывания по мере роста числа корней, то есть максимально
возможное (не целое) число:
√ √ √
√ √
n n−1 n−2
3
2
1
+
+
+...+ n−2 + n−1 + n
2
4
8
2
2
2
n n n
n
n
n
+ + +...+ n−2 + n−1 + n
2 4 8
2
2
2
y= 2 2
... 2 2 √ 2 =2
<2
< 2n .
Искомое целое число an сформировано из степеней двойки. Оно может быть только
степенью двойки an = 2k, так как an в степени 2n есть степень двойки. В этом числе не
останется корней, а все множители – только двойки. Значит, число an может быть только
степенью двойки. Оно меньше чем 2n, значит, оно не может превышать число 2n – 1.
Докажем, методом математической индукции, что число 2n – 1 получить можно.
n
n−1
3
2
1
√
База индукции. Если n = 3, то a 3= 2 3 √ 2 √ 22 =√ 23 √ 22= √ 2 4=23−1 .
√ √ √ √ √
Индукционный шаг: a =√ 2 √ 2 √ 2 √ ... √ 2 √ 2 √ 2=√ 2 ⋅2 =2 =2
.
В соответствии с принципом математической индукции, доказано, что a = 2 .
Предполагаем, что a n= 2n 2 n−1 . .. 23 2 √ 2 2=2n−1 , n≥3 .
n +1
n
n−1
3
2
n+1
n−1
n
(n +1)−1
n +1
n
n–1
n –1
Доказано, что число 2 получить можно. Больших целых чисел быть не может, так как
следующая степень двойки уже недостижима. Найденное число и есть ответ.
Ответ: 2n – 1.
1/--страниц
Пожаловаться на содержимое документа