Разбор задачи ММ142 Математического Марафона

======= 142 ========

ММ142 (4 балла)

Все 80 натуральных делителей натурального числа n расположили в порядке возрастания.
Оказалось, делители с первого по четвертый образуют геометрическую прогрессию,
делители с четвертого по седьмой - арифметическую прогрессию,
а восьмой делитель меньше 200. Найти n.
====================

Решение

Первые 4 делителя обязаны иметь вид:
Учитывая, что 8-й делитель меньше 200, имеем

Пусть Тогда первый член арифметической прогрессии, которую образуют делители с 4-го 7-й, равен 8.
Разность прогрессии d не может быть четна, как в этом случае 6-й делитель равен 24. Но это невозможно, поскольку 3 не является делителем.
Если разность прогрессии нечетна, тогда 5-й делитель - наименьший нечетный простой делитель n.
Поскольку меньше, 6-й делитель равен 16. Но тогда 5-й равен 12, что невозможно.
Итак, p не равно 2.

Пусть . Тогда все делители n нечетны и d обязано быть четным.
7-й делитель - кратен 3. Поэтому либо где либо
Легко проверить, что оба случая невозможны.

Остается случай Тогда 4-й делитель равен 125, а делители с 5-го по 7-й ( и ) должны быть простыми.
Из последнего следует, что d обязано быть кратно 6. Если , то 8-й делитель больше 200.
Итак
Поэтому d не может равняться 6 и 18.
Поэтому d не может равняться 12.
При получаем три простых делителя 149, 173 и 197.
Для восьмого делителя, который меньше 200, остается одна возможность - 199.

Итак, мы уже имеем 5 различных простых сомножителей n. один из которых входит в разложение n не менее, чем в 3-й степени.
Это дает не менее делителей.
Если у n найдется еще один простой делитель или еще один из имеющихся делителей будет в ходить в разложение n в степени выше 1-й, общее число делителей превысит 80.
Остается единственная возможность

Обсуждение

Задача не вызвала затруднений у участников. С ней успешно справились 15 человек (второй результат в истории Марафона).

Награды

За правильное решение задачи ММ142 Анатолий Казмерчук, Виктор Филимоненков, Алексей Волошин, Сергей Половинкин, Николай Дерюгин, Дмитрий Пашуткин, Андрей Халявин, Евгений Машеров, Кирилл Веденский, Александр Ларин, Евгений Гужавин, Галина Крюкова. iPhonograph, Sirion и Umnik получают по 4 призовых балла.

Эстетическая оценка - 4.3 балла

Разбор задачи ММ142 подготовил Владимир Лецко

Решения задач 6

Задача 19.

Обозначим





При этом
  , а .
Так что
 

Сравним
















Ответ: первое выражение больше.

Задача 20
Общий вид треугольных чисел: .

Т.к. оно должно быть квадратом, имеем диофантово уравнение:



Решим его как квадратное относительно n:
Дискриминант должен быть полным квадратом, так что имеем новое уравнение, на этот раз без первых степеней:



Такое диофантово уравнение называется уравнением Пелля. Очевидны его решения k=1, m=0 и k=3, m=1. Кроме того, треугольно-квадратным, как было сказано в условии, является число 36, поэтому имеем: m=6 и k=17.

Решения уравнения Пелля подчиняются рекуррентному соотношению, в данном случае это будет
  и .

Следующее m будет равно 6*6-1=35 и

Ответ: Таких чисел будет бесконечно много, а следующее – 1225.

Задача 21.
Прибавим и отнимем




Задача 22.
Остатки при делении на 7 будут имеют период длины 3 и равны: (1, 2, 4). Остатки при делении на 7 имеют период длины 7 и равны (0, 1, 4, 2, 2, 4, 1).

Чтобы разность делилась на 7 необходимо, чтобы эти остатки были равны. Это приводит нас к уравнениям:

а) n=3m=7k+1
n=21t+15

б) n=3m=7k+6
n=21t+6

в) n=3m+1=7k+3
n=21t+10

г) n=3m+1=7k+4
n=21t+4

д) n=3m+2=7k+2
n=21t+2

е) n=3m+2=7k+5
n=21t+5

Итак, число n должно давать остаток 2, 4, 5, 6, 10 или 15 при делении на 21.
До 10000 групп по 21 числу будет 476, что даёт нам 2856 решений. А т.к. 10000 даёт остаток 4 при делении на 21, то будет ещё два решения, соответствующие остаткам 2 и 4.

Ответ: 2858

Призовые баллы получают:
Alexisto: +12
Alexalkin (nazva.net): +11
Сергей Кузнецов: +5
Наталия Макарова: +5

Решения задач 3

Задача 7.

Поскольку в условии не сказано «различных», это даёт нам свободу манёвра:

203= 7*29*1*1*…*1=7+29+1+1+…+1 Единиц будет 167

Ответ:можно

Задача 8.

Можно представить даже три способа

Задача 9.

Достаточно вспомнить, что палиндромами являются все однозначные числа, и что наименьшее совершенное число – это 6=1+2+3.

В задаче не уточняется, нужно ли рассматривать только делители, меньшие самого числа, или же все. Но и для второго варианта подходит число 1=1.

Ответ: 6 (если рассматривать только делители, меньшие самого числа) и 1 (если рассматривать все делители)

Задача 10.

Пусть последняя цифра числа равна а, а остальные цифры формируют число Y. Тогда

10Y+a=nY

a=Y(n-10)

Т.к. a – цифра, то могут быть варианты:

n=10, a=0, Y – любое – подходят все числа, оканчивающиеся на 0;

n=11, a – любая цифра, Y=a – подходят все числа, состоящие из пары цифр;

n=12, a=2Y, подходят 12, 24, 36, 48;

n=13, a=3Y, подходят 13, 26, 39;

n=14, a=4Y, подходят 14, 28

Для n =15, 16, 17, 18, 19 подходят сами числа 15, 16, 17, 18, 19

Призовые баллы получают:

Семён Знаковян (*ALEX ALKIN*) - 20

Решения задач 2

Задача 4.

Рассмотрим остатки от деления степеней десяти на 93

n	10n mod 93
0	1
1	10
2	7
3	70
4	49
5	25
6	64
7	82
8	76
9	16
10	67
11	19
12	4
13	40
14	28
15	1

Они образуют период длиной 15. Среди этих чисел невозможно взять 2 таких, чтобы их сумма равнялась 93, значит, не существует числа вида 100..01, которое делится на 93. Из троек остатков на 93 будет делиться сумма r_n+r₁+r₀=82+10+1, она и укажет на минимальное число с минимальной суммой цифр, делящееся на 93 – это число 10000011.

Ответ: 10000011

Задача 5.

Поскольку каждое из чисел не превосходит 100, можем попросить компьютер предоставить нам значение выражения 100000000*число+1000000*месяц+10000*час+100*минуты+секунды.

Существует и более универсальный способ, который предложил Профессор Снейп (dxdy.ru): Нужно запросить результат 2^число*3^месяц*5^час*7^минуты*11^{секунды}. Такой способ будет работать для любого количества хранимых чисел любого размера.

Ответ: за один запрос

Задача 6.

Нужно найти, существует ли степень десятки, которая даёт остаток 58 при делении на 59. Такой степенью будет 10²⁹ . Значит 1{28нулей}1делится на 59.

Ответ: существует

Призовые баллы получают:

Николай (smekalka.pp.ru) – 8

Вован (nazva.net) – 5

Legioner93 (dxdy.ru) - 5

GENERATION (smekalka.pp.ru) – 3

Профессор Снейп (dxdy.ru) – 3

ИСН (dxdy.ru) – 3

Disciple (nazva.net) - 3 

Математический аукцион 1: необычное число.

Правила математического аукциона.

Даётся исследовательская задача. Участники в комментариях предлагают свои варианты решения. Каждое решение, оказавшееся лучше присланного перед этим решения другого участника, оценивается всё большим количеством баллов. Если участник присылает несколько решений подряд, оценивается самое лучшее из них.

Задача

Число 210 делится на 21 и на 10.

Найдите как можно более длинное число, которое делится на все двузначные числа, образованные его соседними цифрами.  (Нули внутри числа и повторяющиеся 2-значные фрагменты в нём не допускаются). 

Решения задач 1

Задача 1.

Треугольники AOM и BOА – прямоугольные, имеют равные острые углы и общий катет. Следовательно, они равны и AB=AM=MC. Значит АС=2АВ.

Троек последовталеьных чётных чисел, одно из которых вдвое больше другого – две. Это 2, 4, 6, не задающая треугольник и 4, 6, 8, которая и будет решением.

Ответ: 4, 6, 8.

Задача 2.

Рассмотрим три последовательных числа: n-1, n, n+1. Сумма их кубов равна (n-1)³ + n³ + (n+1)³ = n³ – 3n² + 3n – 1 + n³ + n³ + 3n² + 3n + 1 = 3n³ + 6n = 3n(n²+2).

Это говорит нам, что сумма трёх последовательных кубов всегда делится на 9, т.к при n делящемся на 3, на 9 будет делиться 3n, а в ином случае - 3(n²+2). Так что признак делимости на 9 ничего не проясняет.

Однако подбирая больше троек чисел для анализа, мы быстро натыкаемся на решение задачи.

n	3n(n2+2)
0	0
1	9
2	36
3	99
4	216
5	405
6	684
7	1071
8	1584
9	2241
10	3060
11	4059
12	5256
13	6669

12³ + 13³ + 14³=6669.

Следующая такая тройка:

22³ + 23³ + 24³=36639

Ответ: существуют.

.Задача 3.

Доказательство:

Рассмотрим 94 числа, записанных единицами: 1, 11, 111, …[число из 94 единиц]. Существует 93 возможных остатка от деления на 93. Следовательно, по принципу Дирихле, мы будем иметь два числа, сотосящих из одних едниц, дающие одинаковый сотаток при делении на 93. Разность их, число вида 11…10…0 будет делиться на 93. Т.к. 93 и 10 взаимно просты, то и число из одних единиц, полученное отбрасыванием нулей от разности, тоже будет делиться на 93. А, значит, существует и число из одних троек, которое будет делиться на 93.

Хотя само число приводить не требовалось, многие участники его нашли. Это пятнадцать троек:  333333333333333.

Призовые баллы получают:

Семён Знаковян (*ALEX ALKIN*) - 10

GENERATION (smekalka.pp.ru) – 9

николай (smekalka.pp.ru) – 3

lkob (nazva.net) – 3

НафтюФа (nazva.net) – 3