РЕШУ ОЛИМП, математика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 2487 Добавить в вариант

Натуральное число x в восьмеричной системе 2019-значное, его младшая цифр равна 3, все остальные цифры отличны от 3 и совпадают через одну. Число y получается записью цифр x в обратном порядке. Оказалось, что восьмеричное представление $x умножить на y$   содержит только цифры 1 и 6. Найдите $x умножить на y$   (в восьмеричной системе).

Спрятать решение

Решение.

Решим задачу для $левая круглая скобка 2 n плюс 1 правая круглая скобка$ -значного x. Договоримся восьмеричные числа писать в скобках, чтобы отличать их от десятичных. Положим

$x= левая круглая скобка \underbracea b \ldots a b_2 n \text цифр 3 правая круглая скобка , \quad y= левая круглая скобка 3 \underbraceb a \ldots b a_2 n \text цифр правая круглая скобка .$

Младшая цифра $x умножить на y$ равна $3 a \bmod 8.$ При $a не равно q 3$ она не может быть 1, а с 6 совпадает только при $a=2.$ Так как $3 a меньше 8,$ следующая цифра $x умножить на y$ равна

$b левая круглая скобка a плюс 3 правая круглая скобка \bmod 8=5 b \bmod 8.$

Это дает 1 при $b=5$ и 6 при $b=6.$ Второй случай не подходит, поскольку в произведении (26 .. 263) (362 .. 62) в четвертом разряде окажется 4. Таким образом, $x= левая круглая скобка 25 \ldots 253 правая круглая скобка$ и $y= левая круглая скобка 352 \ldots 52 правая круглая скобка .$

Мы пока не Знаем, удовлетворяют ли найденные x и y условию задачи. Чтобы убедиться в этом и получить ответ, необходимо вычислить $x умножить на y.$ Заметим, что

$y минус x= левая круглая скобка 7 \ldots 7 правая круглая скобка =8 в степени левая круглая скобка 2 n правая круглая скобка минус 1, \quad 2 x плюс y= левая круглая скобка 52 \ldots 526 правая круглая скобка плюс левая круглая скобка 352 \ldots 52 правая круглая скобка = левая круглая скобка 11 правая круглая скобка умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка =9 умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка ,$

откуда

$3 x=2 x плюс y минус левая круглая скобка y минус x правая круглая скобка =8 в степени левая круглая скобка 2 n плюс 1 правая круглая скобка плюс 1, \quad 3 y=2 левая круглая скобка y минус x правая круглая скобка плюс 2 x плюс y=11 умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка минус 2 .$

Перемножим эти равен ства и поделим результат на 9. Мы получим

$x y= дробь: числитель: левая круглая скобка 8 в степени левая круглая скобка 2 n плюс 1 правая круглая скобка плюс 1 правая круглая скобка левая круглая скобка 11 умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка минус 2 правая круглая скобка , знаменатель: 9 конец дроби = левая круглая скобка 8 в степени левая круглая скобка 2 n плюс 1 правая круглая скобка плюс 1 правая круглая скобка умножить на левая круглая скобка 8 в степени левая круглая скобка 2 n правая круглая скобка плюс 2 умножить на дробь: числитель: 8 в степени левая круглая скобка 2 n правая круглая скобка минус 1, знаменатель: 9 конец дроби правая круглая скобка .$

Числитель и Знаменатель дроби в правой части равны соответственно (777 ... 7) и (11), поэтому частное равно (70 707 ... 07) (в нем фигурирует n семерок). Тогда

$x y= левая круглая скобка 8 в степени левая круглая скобка 2 n плюс 1 правая круглая скобка плюс 1 правая круглая скобка умножить на левая круглая скобка 1 \underbrace16 \ldots 16_2 n \text цифр правая круглая скобка = левая круглая скобка 1 \underbrace16 \ldots 16_2 n \text цифр 1 \underbrace16 \ldots 16_2 n \text цифр правая круглая скобка .$

Ответ: $x умножить на y=1 \underbrace1616 \ldots 16_2018 1 \underbrace1616 \ldots 16_2018$ при $x=\underbrace25 \ldots 25_2018 3.$

Приведем другое решение. Решим задачу для $левая круглая скобка 2 n плюс 1 правая круглая скобка$ -значного x. Договоримся писать числа в восьмеричной системе. Положим

$x_n=\underbracea b \ldots a b_2 n \text цифр 3, \quad y_n=3 \underbraceb a \ldots b a_2 n \text цифр .$

Младшая цифр а $x_n умножить на y_n$ равна $3 a \bmod 8.$ При $a не равно q 3$ она не может быть 1, а с 6 совпадает только при $a=2.$ Так как $3 a меньше 8,$ следующая цифра $x_n умножить на y_n$ равна

$левая круглая скобка a плюс 3 правая круглая скобка b \bmod 8=5 b \bmod 8.$

Это дает 1 при $b=5$ и 6 при $b=6.$ Второй случай не подходит поскольку в произведении

$26 \ldots 263 умножить на 362 \ldots 62$

в четвертом разряде окажется 4. Докажем по индукции, что

$\underbrace25 \ldots 25_2 n \text цифр 3 умножить на 3 \underbrace52 \ldots 52_2 n \text цифр =11 \underbrace61 \ldots 61_2 n \text цифр \underbrace16 \ldots 16_2 n \text цифр .$

База индукции очевидна: $253 умножить на 352=116 116.$ Предположим, что для некоторого n утверждение доказано. Заметим, что

$x_n плюс 1=\underbrace25 \ldots 25_2 n \text цифр 300 минус 25=8 в квадрате x_n минус 25,$

$y_n плюс 1=3 \underbrace52 \ldots 52_2 n \text цифр 00 плюс 52=8 в квадрате y_n плюс 52=8 в квадрате y_n плюс 2 умножить на 25.$

Воспользуемся формулой

$25 левая круглая скобка 2 x_n минус y_n правая круглая скобка =43 \underbrace0 \ldots 0_2 n минус 2 34, \qquad левая круглая скобка * правая круглая скобка$

которую проверим ниже. Мы получим

$x_n плюс 1 умножить на y_n плюс 1=8 в степени левая круглая скобка 4 правая круглая скобка умножить на x_n умножить на y_n плюс 25 умножить на 8 в квадрате левая круглая скобка 2 x_n минус y_n правая круглая скобка минус 25 умножить на 52=$
$=11 \underbrace61 \ldots 61_2 n \underbrace16 \ldots 16_2 n 0000 плюс 43 \underbrace0 \ldots 0_2 n минус 2 3400 минус 1562=$
$= 11 \underbrace61 \ldots 61_2 n плюс 2 \underbrace16 \ldots 16_2 n минус 2 0000 плюс 3400 минус 1562=11 \underbrace61 \ldots_2 n плюс 2 \underbrace16 \ldots 16_2 n плюс 2,$

что и требовалось доказать.

Осталось проверить равенство (*). Положим $z=\underbrace52 \ldots 52_2 n \text цифр .$ Тогда

$2 x_n=\underbrace52 \ldots 52_2 n \text цифр 6=8 z плюс 6, \quad y_n=z плюс 3 умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка .$

Заметим, что

$25 z=15 \underbrace7 \ldots 7_2 n минус 2 62=16 умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка минус 16=16 левая круглая скобка 8 в степени левая круглая скобка 2 n правая круглая скобка минус 1 правая круглая скобка .$

Поэтому

$25 левая круглая скобка 2 x_n минус y_n правая круглая скобка =25 левая круглая скобка 7 z плюс 6 минус 3 умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка правая круглая скобка =7 умножить на 16 левая круглая скобка 8 в степени левая круглая скобка 2 n правая круглая скобка минус 1 правая круглая скобка плюс 25 умножить на 6 минус 3 умножить на 25 умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка =$
$=8 в степени левая круглая скобка 2 n правая круглая скобка левая круглая скобка 7 умножить на 16 минус 3 умножить на 25 правая круглая скобка плюс 6 умножить на 25 минус 7 умножить на 16=43 умножить на 8 в степени левая круглая скобка 2 n правая круглая скобка плюс 34=43 \underbrace0 \ldots 0_2 n минус 2 34.$

Спрятать критерии

Критерии проверки:

Общая схема:

0 баллов  — выставляется, если участник к решению задачи не приступал или начатый ход решения полностью неверен;

1 балл  — выставляется, если участник приступил к решению задачи, указал верное направление решения задачи и получил правильные промежуточные результаты, но при этом не продвинулся настолько, чтобы можно было судить о том, каким образом он собирался получить окончательный ответ (то есть весь ход решения не представлен);

2 балла  — выставляется, если выбранный участником ход решения задачи является в принципе правильным, но при этом участник не смог его реализовать в силу серьёзных ошибок;

3 балла  — выставляется, если решение является в целом правильным, но содержит ошибки, повлиявшие на ответ;

4 балла  — выставляется, если участник решил задачу в целом правильно и получил верный ответ; при этом в решении допускаются незначительные неточности.

Факторы, влияющие на оценку.

1.  Одна из основных целей Олимпиады  — выявление у обучающихся творческих способностей. Поэтому в случае представления участником интересного оригинального подхода к решению задачи, оценка за решение может быть увеличена на 1 балл.

2.  Правильный ответ к задаче, приведенный без достаточных обоснований, либо при наличии ошибок в решении, либо при отсутствии решения, не ведёт к увеличению оценки, которая выставляется участнику за данную задачу.

3.  Если участник не довел задачу до ответа, то итоговая оценка за данную задачу не может превышать 1 балл.

4.  Если задача решена перебором возможных вариантов, и при этом перебор неполный, то за задачу выставляется до 1 балла. Если участник подобрал частное решение без обоснования и проверил его правильность, то в этом случае за задачу выставляется до 0,5 баллов.

5.  Если задача решена при дополнительном предположении, которое отсутствует в условии, то за задачу выставляется

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

6.  Если в работе приведены два решения или ответа к одной задаче, противоречащие друг другу, то за задачу ставится 0 баллов.

Олимпиада СПБГУ, 11, 10 класс, 2 тур (заключительный), 2019 год

Классификатор: Алгебра: числа. Различные системы счисления, Методы алгебры. Метод математической индукции

Спрятать решение · Спрятать критерии · Помощь