ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 107]      



Задача 111922

Темы:   [ Треугольник Паскаля и бином Ньютона ]
[ НОД и НОК. Взаимная простота ]
[ Сочетания и размещения ]
[ Подсчет двумя способами ]
Сложность: 4
Классы: 8,9,10,11

Автор: Фольклор

Докажите, что при любых натуральных  0 < k < m < n  числа    и    не взаимно просты.

Решение

Согласно задаче 60413 а)     . Но      Поэтому    и    не взаимно просты.

Прислать комментарий

Задача 116706

Темы:   [ Треугольник Паскаля и бином Ньютона ]
[ Простые числа и их свойства ]
[ Произведения и факториалы ]
Сложность: 5-
Классы: 11

Обозначим через  S(n, k)  количество не делящихся на k коэффициентов разложения многочлена  (x + 1)n  по степеням x.
  а) Найдите  S(2012, 3).
  б) Докажите, что  S(20122011, 2011)  делится на 2012.

Решение

  Пусть p – простое число и  n = n0 + n1p + n0p² + ... + nkpk = (nk...n1n0)p  – p-ичное представление числа n. Покажем, что
S(n, p) = (n0 + 1)(n1 + 1)...(nk + 1).

  Первый способ. Будем рассматривать многочлены над полем вычетов Zp по модулю p. Здесь  S(n, p)  равно количеству ненулевых коэффициентов многочлена  (x + 1)n.  Заметим, что биномиальный коэффициент     делится на p при  m = 1, ..., p – 1,  а     не делится на p при любом  n < p,
m
= 0, ..., n. .
  Отсюда сразу следует, что над Zp   (x + 1)p = xp + 1,  (x + 1)p² = (xp + 1)p = xp² + 1,  ...,  (x + 1)pm = xpm + 1,  ...
  Поэтому   (x + 1)n = (x + 1)n0(x + 1)n1p...(x + 1)nkpk = (x + 1)n0(xp + 1)n1...(xpk + 1)nk.   Раскладывая  (xpi + 1)ni  по биному, мы получаем многочлен от xpi, все коэффициенты которого, как сказано выше, отличны от нуля. Этих коэффициентов ровно  ni + 1.  Перемножив теперь все скобки мы получим сумму  (n0 + 1)(n1 + 1)...(nk + 1)  одночленов вида xm0xm1p...xmkpk с ненулевыми коэффициентами. Поскольку  mini < p,  среди этих одночленов нет одинаковых, то есть "приведения подобных" не происходит и число  S(n, p)  ненулевых коэффициентов многочлена  (x + 1)n  равно
(n0 + 1)(n1 + 1)...(nk + 1).

  Второй способ. Надо подсчитать, сколько чисел среди   ,  m = 0, 1, ..., n  не делятся на p.

  Степень простого числа p, на которую делится n!, равна     (см. задачу 60553). Поэтому степень p, на которую делится

,  равна   ...

  Но  [a + b] ≥ [a] + [b]  для любых действительных чисел a и b. При этом  [a + b] = [a] + [b]  тогда и только тогда, когда  {a} + {b} < 1,  то есть
{a} ≤ {a + b}.  Получаем, что все слагаемые в выписанной выше сумме неотрицательны, и для того, чтобы      не делилось на p, надо, чтобы все они равнялись 0, а это равносильно тому, что     и т. д.
  Пусть  n = (nk...n1n0)p  и  m = (mk...m1m0)p  – p-ичные представления чисел n и m. Тогда требуемое условие равносильно тому, что  m0n0m1n1,
m2n2  и т. д. Значит, mi может принимать ровно  ni + 1  значений. Всего вариантов для m:  (n0 + 1)(n1 + 1)...(nk + 1).

  Вернёмся к решению задачи.

  а) Так как 3 – простое число, а  2012 = (2202112)3,  то  S(2012,3) = 34·2² = 324.

  б) Число 2011 простое, а  
  В этой сумме все слагаемые, начиная с четвёртого, делятся на 20114, а первые три слагаемых дают  1 + 2011² + 1005·2011³.  Это означает, что в представлении числа 20122011 в системе счисления с основанием 2011 младшие разряды такие:  n0 = 1,  n1 = 0,  n2 = 1,  n3 = 1005.  Поэтому
S(20122011, 2011)  делится на  (n0 + 1)(n3 + 1) = 2012.

Ответ

а) 324.

Прислать комментарий

Задача 73773

Темы:   [ Треугольник Паскаля и бином Ньютона ]
[ Бином Ньютона ]
[ Индукция (прочее) ]
[ Делимость чисел. Общие свойства ]
[ Рекуррентные соотношения (прочее) ]
Сложность: 5
Классы: 9,10,11

Автор: Шлейфер Р.

Для любого натурального числа n сумма     делится на 2n–1. Докажите это.

Решение

  Обозначим нашу сумму через sn. Будем вести индукцию по n.
  База.  s1 = 1  делится на 20,  s2 = 2  делится на 21.
  Шаг индукции. Обозначим     и заметим, что    
Поскольку  an – bn = (an–1bn–1)(a + b) – ab(an–2bn–2) = 2(an–1bn–1) + 1972(an–2bn–2),  то и  sn = 2sn–1 + 4·493sn–2.
  По предположению индукции  sn–1 кратно 2n–2sn–2 кратно 2n–3;  значит,  sn делится на 2n–1.

Прислать комментарий

Задача 35547

Темы:   [ Правило произведения ]
[ Треугольник Паскаля и бином Ньютона ]
Сложность: 2+
Классы: 7,8

Сколькими способами можно прочитать слово "строка", двигаясь вправо или вниз?:
С Т Р О К А
Т Р О К А
Р О К А
О К А
К А
А

Подсказка

Если двигаться с первой буквы "С", то каждый раз предоставляется две возможности – идти вправо или вниз.

Решение

Ясно, что начать движение можно только с первой буквы "C". Каждым ходом мы опускаемся на одну диагональ ниже, и перед перед нами имеется выбор – идти вправо или вниз. При каждой из этих двух возможностей мы вновь опускаемся на диагональ ниже и тем самым продолжаем чтение слова "СТРОКА". Таким образом, возможностей прочитать слово "СТРОКА" столько же, сколько возможностей последовательного пятикратного выбора из двух вариантов, то есть  25 = 32.

Ответ

32 способами.

Прислать комментарий

Задача 60871

Темы:   [ Доказательство тождеств. Преобразования выражений ]
[ Треугольник Паскаля и бином Ньютона ]
Сложность: 3
Классы: 8,9,10

При каких натуральных n число  ( + 1)n – ( – 1)n  будет целым?

Ответ

При нечётных n.

Прислать комментарий

Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 107]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .