Научно-исследовательская работа школьников в РБ
Для m = 4
4x (x-1) +1 = 4x2 - 4x + 1 = (2x-1) (2x-1)
Ответ: f (g (x)) неприводим при всех целых mП{1; 4}.
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) = tЧdЧ (x-a1) 2… (x-an) 2+ (t+d) Ч (x-a1) … (x-an) +1.
Из равенства многочленов получаем m = tЧd и (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-4a<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) = tЧdЧ (x-a1) 2… (x-an) 2+ (t+d) Ч (x-a1) … (x-an) +1.
Из равенства многочленов получаем, что a = tЧd и b = t+d. Значит t и d являются корнями уравнения x2 -bx +a = 0. Но согласно предположению дискриминант этого уравнения b2-4a<0. Уравнение не имеет корней. Таким образом допущение не верно и при отрицательном дискриминанте многочлен aЧ (g (x)) 2+bЧg (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 |
| k |
|
|
|
|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 7722 | 28182 | 190740 | 796521 |
| 2 | 6412 | 23310 | 157926 | 659835 |
| 3 | 5131 | 18564 | 125922 | 526449 |
| 4 | 3906 | 14053 | 95449 | 399334 |
| 5 | 2771 | 9907 | 67382 | 282126 |
| 6 | 1766 | 6271 | 42711 | 178971 |
| 7 | 936 | 3300 | 22506 | 94380 |
| 8 | 330 | 1155 | 7887 | 33099 |
| 9 | 0 | 0 | 0 | 0 |
|
|
28974 | 104742 | 710523 | 2970715 |
Составим таблицу некоторых значений r (n,k,k2)
| k |
|
|
|
|
|
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 10 | 45 |
| 2 | 1 | 2 | 3 | 29 | 126 |
| 3 | 1 | 3 | 6 | 56 | 235 |
| 4 | 1 | 4 | 10 | 90 | 365 |
| 5 | 1 | 5 | 15 | 130 | 510 |
| 6 | 1 | 6 | 21 | 175 | 665 |
| 7 | 1 | 7 | 28 | 224 | 826 |
| 8 | 1 | 8 | 36 | 276 | 990 |
| 9 | 1 | 9 | 45 | 330 | 1155 |
|
|
10 | 45 | 165 | 1320 | 4917 |
| k |
|
|
|
|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 285 | 1155 | 9042 | 33099 |
| 2 | 810 | 3300 | 25806 | 94380 |
| 3 | 1531 | 6271 | 48982 | 178971 |
| 4 | 2406 | 9907 | 77289 | 282126 |
| 5 | 3396 | 14053 | 109502 | 399334 |
| 6 | 4499 | 18564 | 144486 | 526449 |
| 7 | 5586 | 23310 | 181236 | 659835 |
| 8 | 6732 | 28182 | 218922 | 796521 |
| 9 | 7887 | 33099 | 256938 | 934362 |
|
|
33099 | 137841 | 1072203 | 3905077 |
Ответ:
а) третьего типа: 2970715; четвертого типа: 3905077
б)


3. Используя
метод рекуррентного
соотношения
для подсчёта
количество
волнистых
чисел, можно
составить
рекуррентную
формулу для
любой конфигурации
знаков ”<”,”>”,”
”,”
”,”=".
Какой знак на
текущем шаге
вычисления
рекуррентного
соотношения
можно легко
определять
по остатку от
деления текущего
i-2 (
)
на количество
различных
знаков до повторения.
Например, выведем формулу для нахождения количества волнистых чисел типа:
![]()
Количество различных знаков до повторения - 3.
q (n,k1,k2) - количество n-значных волнистых чисел данного типа, начинающихся с цифры k1 и заканчивающиеся на цифру k2.
Начальные
значения
,
т.е. есть только
по одному
однозначному
волнистому
числу, начинающемуся
на i и
заканчивающемуся
на i (
).
Пусть
,
тогда по остатку
от деления i-2
на 3 определяем
текущий знак:
Если
(i-2) mod
3=0,
является суммой
всех количеств
i-1-значные
волнистых чисел
данного типа,
которые начинаются
на k1 и
у которых последняя
цифра меньше
либо равна k2.
Если
(i-2) mod
3=1,
равно количеству
i-1-значных
волнистых чисел
данного типа,
которые начинаются
на k1 и
у которых последняя
цифра равна
k2.
Если
(i-2) mod
3=2,
является суммой
всех количеств
i-1-значные
волнистых чисел
данного типа,
которые начинаются
на k1 и
у которых последняя
цифра больше
либо равна k2.
В итоге получаем формулу:
и

Количеством n-значных чисел данного типа будет:

Составим таблицу некоторых значений q (n,k,k2)
| k |
|
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |