Научно-исследовательская работа школьников в РБ
b>2
. Допустим, что
m (
x-
a1) 2… (
x-
an) 2+1 приводим, тогда
m (
x-
a1) 2… (
x-
an) 2+1 =
f1 (
x)
f2 (
x).Как и выше,
f1 (
x) =
f2 (
x) =1 либо
f1 (
x) =
f2 (
x) = - 1 для всех
x из {
a1; …;
an}. Если
f1 (
x) принимает значения и 1 и - 1, то в силу непрерывности многочлена,
f1 (
x) = 0 для некоторого
x. Но тогда для этого
x выполнено равенство
m (
x-
a1) 2… (
x-
an) 2+1 =
f1 (
x)
f2 (
x) = 0,чего быть не может ни при одном натуральном
m. Поэтому для определенности будем считать, что
f1 (
ai) =
f2 (
ai) =1 для всех
i от 1 до
n. (В случае, когда,
f1 (
ai) =
f2 (
ai) =-1 для всех
i от 1 до
n доказательство проводится аналогично) Как и в пункте 1, получаем
f1 (
x) =
t (
x-
a1) … (
x-
an) +1;
f2 (
x) =
d (
x-
a1) … (
x-
an) +1.Отсюда,
m (
x-
a1) 2… (
x-
an) 2+1 =
f1 (
x)
f2 (
x) =
td (
x-
a1) 2… (
x-
an) 2+ (
t+
d) (
x-
a1) … (
x-
an) +1.Из равенства многочленов получаем
m =
td и (
t+
d) (
x-
a1) … (
x-
an) = 0. Последнее равенство выполнено при всех значениях
x, поэтому из него следует, что
t+
d = 0, то есть
t = -
d. Откуда натуральное
m = -
t2. Противоречие показывает, что многочлен
m (
x-
a1) 2… (
x-
an) 2+1 неприводим. Утверждение доказано.
3. Рассмотрим неприводимый многочлен
ax2+
bx+1. Допустим, дискриминант
b2-4
a<0, а многочлен
a (
x-
a1) 2… (
x-
an) 2 +
b (
x-
a1) … (
x-
an) +1 =
f1 (
x)
f2 (
x) приводим. Как и в пункте 2, учитывая, что при отрицательном дискриминанте многочлен не будет обращаться в 0, получаем:
f1 (
x) =
t (
x-
a1) … (
x-
an) +1;
f2 (
x) =
d (
x-
a1) … (
x-
an) +1.Отсюда,
a (
x-
a1) 2… (
x-
an) 2 +
b (
x-
a1) … (
x-
an) +1 ==
f1 (
x)
f2 (
x) =
td (
x-
a1) 2… (
x-
an) 2+ (
t+
d) (
x-
a1) … (
x-
an) +1.Из равенства многочленов получаем, что
a =
td и
b =
t+
d. Значит
t и
d являются корнями уравнения
x2 -
bx +
a = 0. Но согласно предположению дискриминант этого уравнения
b2-4
a<0. Уравнение не имеет корней. Таким образом допущение не верно и при отрицательном дискриминанте многочлен
a (
g (
x)) 2+
bg (
x) +1 неприводим.
3.2 Пример 2: волнистые числаНазовем девятизначное число волнистым числом первого типа, если Например, число 162539581 волнистое число первого типа. Назовем девятизначное число волнистым числом второго типа, если а) Найдите количество девятизначных волнистых чисел первого и второго типа.б) Найдите формулу для вычисления количества волнистых
п-значных чисел первого и второго типа.Назовем девятизначное число волнистым числом третьего типа, если Назовем девятизначное число волнистым числом четвертого типа, если а) Найдите количество девятизначных волнистых чисел третьего и четвертого типа.б) Найдите формулу для вычисления количества волнистых
п-значных чисел третьего и четвертого типа.Предложите свои обобщения этой задачи и исследуйте их.
РешениеЛемма 1. Обозначим через
f (
n,
k1,
k2) - количество
n-значных волнистых чисел первого типа, начинающихся с цифры
k1 и заканчивающиеся на цифру
k2,
g (
n,
k1,
k2) - количество
n-значных волнистых чисел второго типа, начинающихся с цифры
k1 и заканчивающиеся на цифру
k2. Тогда иТакже, и
Доказательство. Рассмотрим
n-значные волнистые числа первого типа.Нетрудно заметить, как они получаются. Берутся все
n-1-значные волнистые числа и, в зависимости от текущего знака (“<" или ”>”), дописывается каждому числу цифра, меньшая или большая последней, т.е. чтобы найти количество
n-значных волнистых чисел, заканчивающихся на
k, надо найти сумму всех количеств
n-1-значных чисел заканчивающихся на цифры от 0 до
k-1 или от
k+1 до 9.Т. к. на каждом шаге мы корректно вычисляем волнистые числа, то нет необходимости знать всё число: все зависит от последней цифры.Следовательно, можно составить рекуррентную формулу, которая будет корректно вычислять количество
n-значных волнистых чисел первого типа начинающихся на цифру
k1 и заканчивающихся на цифру
k2.Рассмотрим рекуррентную формулу для волнистых чисел первого типа.Начальные её значения , т.е. есть только по одному однозначному волнистому числу, начинающемуся на
i и заканчивающемуся на
i (
).Пусть , тогда по четности/нечетности
i () определяем текущий знак “<” или “>”:Если
i-нечетное, то является суммой всех количеств
i-1-значные волнистых чисел первого типа, которые начинаются на
k1 и у которых последняя цифра меньше
k2.Если
i-четное, то является суммой всех количеств
i-1-значные волнистых чисел первого типа, которые начинаются на
k1 и у которых последняя цифра больше
k2.Аналогично, выводится рекуррентное соотношение для волнистых чисел второго типа.
Теорема 1. Количество
n-значных волнистых чисел первого типа: и количество
n-значных волнистых чисел второго типа: .Составим таблицу некоторых значений
f (
n,
k,
k2)
|
k | | | | | | |
0 | 1 | 0 | 0 | 0 | 0 | |
1 | 1 | 8 | 44 | 276 | 1650 | |
2 | 1 | 7 | 42 | 259 | 1561 | |
3 | 1 | 6 | 39 | 235 | 1430 | |
4 | 1 | 5 | 35 | 205 | 1260 | |
5 | 1 | 4 | 30 | 170 | 1055 | |
6 | 1 | 3 | 24 | 131 | 820 | |
7 | 1 | 2 | 17 | 89 | 561 | |
8 | 1 | 1 | 9 | 45 | 285 | |
9 | 1 | 0 | 0 | 0 | 0 | |
| 10 | 36 | 240 | 1410 | 8622 | |
|
|
k | | | | | |
0 | 0 | 0 | 0 | 0 | |
1 | 10032 | 60654 | 367422 | 2224299 | |
2 | 9471 | 57309 | 347073 | 2101296 | |
3 | 8651 | 52403 | 317253 | 1920984 | |
4 | 7596 | 46067 | 278782 | 1688269 | |
5 | 6336 | 38471 | 232715 | 1409487 | |
6 | 4906 | 29820 | 180312 | 1092234 | |
7 | 3345 | 20349 | 123003 | 745161 | |
8 | 1695 | 10317 | 62349 | 377739 | |
9 | 0 | 0 | 0 | 0 | |
| 52032 | 315390 | 1908909 | 11559469 | |
|
Составим таблицу некоторых значений g (n,k,k2)
|
k | | | | | | |
0 | 1 | 0 | 0 | 0 | 0 | |
1 | 1 | 1 | 9 | 45 | 285 | |
2 | 1 | 2 | 17 | 89 | 561 | |
3 | 1 | 3 | 24 | 131 | 820 | |
4 | 1 | 4 | 30 | 170 | 1055 | |
5 | 1 | 5 | 35 | 205 | 1260 | |
6 | 1 | 6 | 39 | 235 | 1430 | |
7 | 1 | 7 | 42 | 259 | 1561 | |
8 | 1 | 8 | 44 | 276 | 1650 | |
9 | 1 | 9 | 45 | 285 | 1695 | |
| 10 | 45 | 285 | 1695 | 10317 | |
|
|
k | | | | | |
0 | 0 | 0 | 0 | 0 | |
1 | 1695 | 10317 | 62349 | 377739 | |
2 | 3345 | 20349 | 123003 | 745161 | |
3 | 4906 | 29820 | 180312 | 1092234 | |
4 | 6336 | 38471 | 232715 | 1409487 | |
5 | 7596 | 46067 | 278782 | 1688269 | |
6 | 8651 | 52403 | 317253 | 1920984 | |
7 | 9471 | 57309 | 347073 | 2101296 | |
8 | 10032 | 60654 | 367422 | 2224299 | |
9 | 10317 | 62349 | 377739 | 2286648 | |
| 62349 | 377739 | 2286648 | 13846117 | |
|
Ответ:
а) первого типа: 11559469; второго типа: 13846117
б)
Лемма 2. Обозначим через t (n,k1,k2) - количество n-значных волнистых чисел третьего типа, начинающихся с цифры k1 и заканчивающиеся на цифру k2, r (n,k1,k2) - количество n-значных волнистых чисел четвертого типа, начинающихся с цифры k1 и заканчивающиеся на цифру k2. Тогда
и
Также и
Доказательство. Рассмотрим n-значные волнистые числа третьего типа.
Нетрудно заметить, как они получаются. Берутся все n-1-значные волнистые числа и, в зависимости от текущего знака (”", ”<”, ”>", ””), дописывается каждому числу цифра, меньшая, равная или большая последней, т.е. чтобы найти количество n-значных волнистых чисел, заканчивающихся на k, надо найти сумму всех количеств n-1-значных чисел заканчивающихся на цифры от 0 до k, или от 0 до k+1, или от k+1 до 9, или от k до 9.Т. к. на каждом шаге мы корректно вычисляем волнистые числа, то нет необходимости знать всё число: все зависит от последней цифры.
Следовательно, можно составить рекуррентную формулу, которая будет корректно вычислять количество n-значных волнистых чисел третьего типа начинающихся на цифру k1 и заканчивающихся на цифру k2.
Рассмотрим рекуррентную формулу для волнистых чисел третьего типа.
Начальные её значения , т.е. есть только по одному однозначному волнистому числу, начинающемуся на i и заканчивающемуся на i ().
Пусть , тогда по остатку от деления i-2 на 4 определяем текущий знак: ”", ”<”, ”>", ””:
Если (i-2) mod 4=0, является суммой всех количеств i-1-значные волнистых чисел третьего типа, которые начинаются на k1 и у которых последняя цифра меньше либо равна k2.
Если (i-2) mod 4=1, является суммой всех количеств i-1-значные волнистых чисел третьего типа, которые начинаются на k1 и у которых последняя цифра меньше k2.
Если (i-2) mod 4=2, является суммой всех количеств i-1-значные волнистых чисел третьего типа, которые начинаются на k1 и у которых последняя цифра больше.
Если (i-2) mod 4=3, является суммой всех количеств i-1-значные волнистых чисел третьего типа, которые начинаются на k1 и у которых последняя цифра больше либо равна k2.
Аналогично, выводится рекуррентное соотношение для волнистых чисел четвертого типа.
Теорема 2. Количество n-значных волнистых чисел третьего типа:
и количество n-значных волнистых чисел четвертого типа:
.
Составим таблицу некоторых значений t (n,k,k2)
|
k | | | | | | |
0 | 1 | 0 | 0 | 0 | 0 | |
1 | 1 | 9 | 36 | 240 | 990 | |
2 | 1 | 8 | 28 | 196 | 826 | |
3 | 1 | 7 | 21 | 154 | 665 | |
4 | 1 | 6 | 15 | 115 | 510 | |
5 | 1 | 5 | 10 | 80 | 365 | |
6 | 1 | 4 | 6 | 50 | 235 | |
7 | 1 | 3 | 3 | 26 | 126 | |
8 | 1 | 2 | 1 | 9 | 45 | |
9 | 1 | 1 | 0 | 0 | 0 | |
| 10 | 45 | 120 | 870 | 3762 | |
|
Страницы: 1, 2, 3, 4