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

Задания

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

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

Даны натуральные числа x и y. В восьмеричной системе они 4n-значные, причем в записи x цифры повторяются через одну, в записи y  — через три. Оказалось, что восьмеричная запись $x умножить на y$   состоит из последовательных блоков по 4 одинаковых цифры. При каких n это возможно?

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

Решение.

Договоримся все числа писать в восьмеричной системе. Пусть λ и μ — четырехзначные числа, образованные младшими цифрами x и y (то есть $\lambda=x \bmod 8 в степени левая круглая скобка 4 правая круглая скобка$ и $\mu=y \bmod 8 в степени левая круглая скобка 4 правая круглая скобка правая круглая скобка .$ Число $\lambda умножить на \mu$   — семизначные или восьмизначное, а четверка его младших цифр такая же, как у $x умножить на y.$ Поэтому мы можем записать

$\lambda умножить на \mu=\overlinea b c d z z z z=\overlinez z z z плюс 8 в степени левая круглая скобка 4 правая круглая скобка умножить на \overlinea b c d.$

Заметим, что на 101 делится любое четырехзначное число, у которого пара старших цифр совпадает с парой младших. В частности, λ и $\overlinez z z$ кратны 101. Тогда

$0= левая круглая скобка \lambda умножить на \mu правая круглая скобка \bmod 101=8 в степени левая круглая скобка 4 правая круглая скобка умножить на \overlinea b c d \bmod 101=\overlinea b c d \bmod 101= левая круглая скобка \overlinec d минус \overlinea b правая круглая скобка \bmod 101,$ $0= левая круглая скобка \lambda умножить на \mu правая круглая скобка \bmod 101=8 в степени левая круглая скобка 4 правая круглая скобка умножить на \overlinea b c d \bmod 101=$
$=\overlinea b c d \bmod 101= левая круглая скобка \overlinec d минус \overlinea b правая круглая скобка \bmod 101,$

откуда $a=c$ и $b=d.$ Положим $u=\overlinez z z z$ и $v=\overlinea b a b.$ Числа x, y получаются умножением соответственно λ, μ на число

$p=1 плюс 8 в степени левая круглая скобка 4 правая круглая скобка плюс 8 в степени левая круглая скобка 8 правая круглая скобка плюс \ldots плюс 8 в степени левая круглая скобка 4 левая круглая скобка n минус 1 правая круглая скобка правая круглая скобка .$

Тогда

$x умножить на y =\lambda умножить на \mu умножить на p в квадрате = левая круглая скобка u плюс 8 в степени левая круглая скобка 4 правая круглая скобка v правая круглая скобка левая круглая скобка 1 плюс 2 умножить на 8 в степени левая круглая скобка 4 правая круглая скобка плюс \ldots плюс левая круглая скобка n минус 1 правая круглая скобка умножить на 8 в степени левая круглая скобка 4 левая круглая скобка n минус 2 правая круглая скобка правая круглая скобка плюс n умножить на 8 в степени левая круглая скобка 4 левая круглая скобка n минус 1 правая круглая скобка правая круглая скобка плюс левая круглая скобка n минус 1 правая круглая скобка умножить на 8 в степени левая круглая скобка 4 n правая круглая скобка плюс \ldots правая круглая скобка =$
$=u плюс левая круглая скобка v плюс 2 u правая круглая скобка умножить на 8 в степени левая круглая скобка 4 правая круглая скобка плюс левая круглая скобка 2 v плюс 3 u правая круглая скобка умножить на 8 в степени левая круглая скобка 8 правая круглая скобка плюс \ldots плюс левая круглая скобка левая круглая скобка n минус 1 правая круглая скобка v плюс n u правая круглая скобка умножить на 8 в степени левая круглая скобка 4 левая круглая скобка n минус 1 правая круглая скобка правая круглая скобка плюс левая круглая скобка n v плюс левая круглая скобка n минус 1 правая круглая скобка u правая круглая скобка умножить на 8 в степени левая круглая скобка 4 n правая круглая скобка плюс \ldots$ $x умножить на y =\lambda умножить на \mu умножить на p в квадрате =$
$= левая круглая скобка u плюс 8 в степени левая круглая скобка 4 правая круглая скобка v правая круглая скобка левая круглая скобка 1 плюс 2 умножить на 8 в степени левая круглая скобка 4 правая круглая скобка плюс \ldots плюс левая круглая скобка n минус 1 правая круглая скобка умножить на 8 в степени левая круглая скобка 4 левая круглая скобка n минус 2 правая круглая скобка правая круглая скобка плюс n умножить на 8 в степени левая круглая скобка 4 левая круглая скобка n минус 1 правая круглая скобка правая круглая скобка плюс левая круглая скобка n минус 1 правая круглая скобка умножить на 8 в степени левая круглая скобка 4 n правая круглая скобка плюс \ldots правая круглая скобка =$
$=u плюс левая круглая скобка v плюс 2 u правая круглая скобка умножить на 8 в степени левая круглая скобка 4 правая круглая скобка плюс левая круглая скобка 2 v плюс 3 u правая круглая скобка умножить на 8 в степени левая круглая скобка 8 правая круглая скобка плюс \ldots плюс левая круглая скобка левая круглая скобка n минус 1 правая круглая скобка v плюс n u правая круглая скобка умножить на 8 в степени левая круглая скобка 4 левая круглая скобка n минус 1 правая круглая скобка правая круглая скобка плюс левая круглая скобка n v плюс левая круглая скобка n минус 1 правая круглая скобка u правая круглая скобка умножить на 8 в степени левая круглая скобка 4 n правая круглая скобка плюс \ldots$

(большие степени 8⁴ нас не интересуют). Отметим три факта.

1)  Для любого $k принадлежит левая фигурная скобка 1, \ldots, n правая фигурная скобка$ число $левая круглая скобка k минус 1 правая круглая скобка v плюс k u$ четырехзначное. Действительно, при $k=1$ это очевидно. Пусть $k меньше n$ и для $1, \ldots, k$ утверждение доказано. Число $k v плюс левая круглая скобка k плюс 1 правая круглая скобка u$ не более чем пятизначное, поскольку это сумма четырехзначных чисел $левая круглая скобка k минус 1 правая круглая скобка v плюс k u,$ u и v. Если s  — цифра в пятом разряде $k v плюс левая круглая скобка k плюс 1 правая круглая скобка u,$ то число $k v плюс левая круглая скобка k плюс 1 правая круглая скобка u минус 8 в степени левая круглая скобка 4 правая круглая скобка s$ есть $левая круглая скобка k плюс 1 правая круглая скобка$ -я четверка цифр $x умножить на y,$ которая по условию постоянна и, следовательно, кратна 101. Но числа u и v также делятся на 101, откуда

$0=8 в степени левая круглая скобка 4 правая круглая скобка s \bmod 101=s \bmod 101.$

Значит, $s=0$ и число $k v плюс левая круглая скобка k плюс 1 правая круглая скобка u$ четырехзначное.

2)  Число $n v плюс левая круглая скобка n минус 1 правая круглая скобка u$ четырехзначное. Действительно,

$n v плюс левая круглая скобка n минус 1 правая круглая скобка u= левая круглая скобка n минус 1 правая круглая скобка v плюс n u плюс v минус u.$

Если $v меньше или равно u,$ то утверждение сразу следует из 1), а в случае $v больше u$ оно проверяется так же, как в 1).

3)  Имеем: $v=\overlinea a a a.$ Действительно, вторая четверка цифр $x умножить на y$ кратна 11, а в силу 1) она равна $v плюс 2 u.$ Но u также делится на 11, откуда

$0=v \bmod 11=\overlinea b a b \bmod 11=2 левая круглая скобка b минус a правая круглая скобка \bmod 11,$

то есть $b=a.$

Заметим, что $a больше 0,$ иначе число $\lambda умножить на \mu$ будет не более чем четырехзначным. Из 2) и 3) вытекает, что число $n умножить на \overlinea a a a$   — четырехзначное. Значит, $7 больше или равно n a больше или равно n.$ Поэтому $n больше 7$ не удовлетворяет условию задачи.

Пусть теперь $n меньше или равно 7.$ Положим $x=22 \ldots 22$ и $y=4000 \ldots 4000.$ Тогда $\lambda умножить на \mu=2222 умножить на 4000=11 110 000,$ откуда

$x умножить на y=\lambda умножить на \mu умножить на p в квадрате =11 112 222 \ldots nnnn \ldots 222 211 110 000.$

Таким образом, $n меньше или равно 7$ удовлетворяет условию задачи.

Ответ: $n принадлежит левая фигурная скобка 1, 2, \ldots, 7 правая фигурная скобка .$

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

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

Общая схема:

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 год

Классификатор: Алгебра: числа. Различные системы счисления

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