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

Проект МЦНМО
при участии
школы 57
Задача 73633
Темы:    [ Доказательство от противного ]
[ Обратный ход ]
[ Числовые таблицы и их свойства ]
[ Рекуррентные соотношения ]
[ Делимость чисел. Общие свойства ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

  а) Докажите, что в таблице

где каждое число равно сумме трёх стоящих над ним чисел, в каждой строке (начиная с третьей) есть чётное число.
  б) В каждой ли строке (кроме первых двух) встречается число, кратное 3?


Решение

  а) Будем в нашей таблице вместо чётных чисел писать 0, а вместо нечётных – 1. Тогда таблицу из нулей и единиц нужно будет составлять по тому же правилу (каждое число получается как сумма трёх, стоящих над ним в предыдущей строке), только сложение нужно выполнять по модулю два.
  Первый способ. Последние четыре числа в каждой строке зависят только от того, каковы последние четыре числа в предыдущей строке, поэтому эта четвёрка периодически повторяется (с периодом 4, см. рис. 1).

  Второй способ. Предположим, что какая-то строка целиком состоит из единиц. Тогда предыдущая строка, как легко убедиться, может быть только такой:  100100...001001,  а идущая перед ней – только такой:  110000110000...000011000011.  Но это невозможно, поскольку в каждой строке нашей таблицы нечётное количество чисел.

  б) Как легко убедиться, уже в следующей, четвёртой строке таблицы (верхней строке из одной единицы удобно присвоить номер 0)  1, 4, 10, 16, 19, 16, 10, 4, 1  ни одно число не кратно 3.

Замечания

1. Разобравшись в структуре нашей таблицы "по модулю 3" (на рис. 2 числа, дающие при делении на три остаток 0, 1, 2, заменены соответственно жёлтыми, чёрными и красными кружочками), можно заметить, что тем же свойством будут обладать строки с номерами
1,  1 + 3 = 4,  1 + 3 + 3² = 13,  1 + 3 + 3² + 3³ = 40 и т.д.

2. Другие свойства чисел этой таблицы можно вывести, пользуясь тем, что в n-й строке нашей таблицы стоят коэффициенты многочлена     (действуя примерно так же, как в статье "Арифметика биномиальных коэффициентов").

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

журнал
Название "Квант"
год
Год 1971
выпуск
Номер 8
Задача
Номер М98

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

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