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

Проект МЦНМО
при участии
школы 57
Задача 65251
Темы:    [ Четность и нечетность ]
[ Обыкновенные дроби ]
[ Разбиения на пары и группы; биекции ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

Пусть  n > 1  – натуральное число. Выпишем дроби  1/n, 2/n, ..., n–1/n  и приведём каждую к несократимому виду; сумму числителей полученных дробей обозначим через  f(n). При каких натуральных  n > 1  числа  f(n) и  f(2015n) имеют разную чётность?


Решение

  Пусть   n = 2t·m,  где  t ≥ 0,  а число m нечётно. Докажем, что число  f(n) чётно ровно в двух случаях: либо n нечётно и m ≡ 1 (mod 4),  либо же n чётно и  m ≡ 3 (mod4 ).

  Первый способ. Рассмотрим произвольную дробь k/n. Если k делится на 2t+1, то числитель этой дроби после сокращения будет чётен, в противном случае он будет нечётен. Среди чисел  1, 2, ..., n – 1  есть ровно m–1/2 чисел, делящихся на 2t+1. Значит, в сумме  f(n) имеется ровно  n – 1 – m–1/2  нечётных слагаемых. Поэтому  f(n) чётно тогда и только тогда, когда числа  n – 1  и m–1/2 имеют одинаковую чётность, что и требовалось.

  Второй способ. Пусть n нечётно (то есть  t = 0).  Тогда числитель дроби k/n не меняет чётность после сокращения. Значит, количество нечётных числителей будет равно n–1/2, и число  f(n) чётно ровно тогда, когда чётно число n–1/2, то есть при  m ≡ 1 (mod 4).
  Пусть n чётно  (t > 0).  Среди дробей со знаменателем n есть дробь, равная ½ и вносящая в  f(n) слагаемое 1. Все остальные дроби разбиваются на пары вида   (a/n, n–a/n).  Поскольку сумма дробей в паре равна 1, после сокращения они переходят в пары несократимых дробей с одинаковым знаменателем вида  (b/d, d–b/d).  Вклад такой пары дробей в  f(n) равен d, и, если d чётно, он не влияет на чётность числа  f(n).
  Таким образом, чётность  f(n) противоположна чётности аналогичной суммы для дробей     то есть чётности числа  f(m) (при  m = 1  она противоположна чётности  f(1) = 0).  Отсюда и следует требуемое.

  Осталось заметить, что числа n и 2015n имеют одну чётность; кроме того, при нечётном m числа m и 2015m дают разные остатки при делении на 4. Значит, числа  f(n) и  f(2015n) всегда имеют разную чётность.


Ответ

При всех натуральных  n > 1.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2014/2015
этап
Вариант 5
класс
Класс 11
задача
Номер 11.2

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

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