Теория чисел на СПБГУ: десятичная запись, оценка+пример, разные системы счисления

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

Пусть кузнечик прыгал влево некоторое количество прыжков, и суммарно он прыгнул влево на единиц, тогда после прыжков он окажется в точке . Значит, чтобы попасть в , необходимо, чтобы было чётным. Значит, и прыжков не хватит. В качестве примера на можно прыгнуть влево на и на прыжках, а на остальных — вправо.

Числа и являются целыми числами, следовательно, каждое из чисел и являются целыми, а значит, и их сумма является целыми числом, таким образом, число также является целым, т.е. число целое, откуда .

_________________________________________________________________________________________________________________________________________________________________________________

Пусть . Тогда делится на 11, поскольку каждое из чисел 2024 и 33 кратно 11, но не делится на , т.к. первое слагаемое кратно , а второе — нет.

Пусть число дает остаток 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 при делении на 11, тогда число дает соответственно остаток 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1 при делении на 11. Докажем, что если хотя бы одно из чисел и не делится на 11, то и число не делится на 11.

Предположим обратное, тогда сумма остатков чисел и равна 11, следовательно, ровно одно из чисел и даёт четный остаток при делении 11, а значит, соответствующий квадрат даёт остаток 0 или 4 при делении на 11, но тогда второй остаток равен 0 или 7, что невозможно. Таким образом, каждое из чисел и кратно 11, следовательно, каждое из чисел и кратно , таким образом, кратно , но не кратно .

_________________________________________________________________________________________________________________________________________________________________________________

Тогда или

Пусть . Тогда , следовательно, кратно , а значит, как мы показали выше, каждое из чисел и кратно 11. Пусть , , где и являются целыми числами, следовательно, . Легко убедиться, что всеми решениями данного уравнения являются неупорядоченные пары Следовательно, все пары решений это , .

Пусть . Тогда . Если каждое из чисел и не превосходит по модулю 4, то сумма их квадратов не превосходит 32, следовательно, наибольшее из чисел и по модулю не меньше 5. С другой стороны, если какое-то из чисел по модулю больше 5, то его квадрат не меньше 36, что невозможно. Таким образом, в паре чисел хотя бы одно равно 5 по модулю, тогда второе равно 3 по модулю. Тем самым, мы показали, что все пары решений есть , .

Пусть

тогда

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

Первый способ.

Из неравенства следует, что

Таким образом, имеем систему из двух уравнений

Решаем её

Значит,

Следовательно,

Второй способ.

Если делится на то

Значит, это невозможно. Следовательно, делится на Заметим, что

Тогда если то

Значит,

Стало быть,

Но этого не может быть. Таким образом, осталось рассмотреть случаи и В первых двух из них не является удвоенным квадратом, а подходит.

Сделаем два замечания.

1) нечетно. Действительно, пусть четно. Среди семи чисел всегда есть три числа одной четности, и по условию они должны быть попарно соединены. Но на картинке нет циклов длины 3.

2) Если — простой делитель то среди четырех последовательно соединенных чисел существует пара соседних, сумма которых не кратна Возьмем цепочку последовательно соединенных чисел. По условию

Тогда числа и тоже соединены, то есть на картинке получился цикл длины 4, которого там нет.

Из 1) и 2) вытекает, что число имеет по крайней мере два различных нечетных простых делителя. Пусть их ровно два (скажем, и Покажем, что они отличны от 3. Допустим, например, что Не более двух чисел делятся на 3 (если их три, то они образуют цикл). Остальные числа разобьем на две группы, дающие при делении на 3 остатки 1 и 2. Одна из этих групп пуста, иначе любое число из меньшей группы будет соединено по крайней мере с тремя числами из другой группы, что невозможно. Сумма чисел из одной группы на 3 не делится. Поэтому существует трехзвенная цепочка, в которой сумма любой пары соединенных чисел не кратна 3 и, значит, делится на Но это противоречит 2).

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

Договоримся писать если Пусть Тогда

Из условия на вытекает равенство

(1)

где — некоторые -ичные цифры. Сделаем два наблюдения.

1) При любом натуральном

Левая часть кратна откуда

Поскольку взаимно просто с на делится Но это число лежит в интервале откуда

2) Приравняем остатки левой и правой частей от деления на

Поскольку взаимно просто с на делится Заметим, что , иначе число будет восьмизначным. Кроме того, . Поэтому

Таким образом,

Поскольку — -ичная цифра, из 2) вытекает, что , откуда Так как мы получаем и В силу 1) сумма цифр равна

Замечание.

Прямым вычислением проверяется, что . Таким образом, описанная в условии ситуация реализуется.

Обозначим нужное число за и попробуем его найти по индукции. Заметим, что если из монет мы можем собрать любое число большее , то из монет мы сможем собрать любое число большее так: если мы хотим получить число , то возьмем такое от 0 до 2, что делилось на 3. Тогда и значит, его можно представить как , где целые и неотрицательные. Тогда .

Теперь пусть из монет мы сможем собрать число , то есть , где целые и неотрицательные. Заметим, что 3 монеты вида можно обменять на 5 монет . Значит, можно считать, что . С другой стороны, делится на 3, и значит, и . Тогда , где целые и неотрицательные. Это значит, что из монет мы смогли собрать ?!

Значит, мы доказали, что из монет можно собрать любое число большее и нельзя собрать . Значит . Тогда . Из этого рекурсивного отношения получаем, что . Тогда и значит

Заметим, что для мы можем получить все числа хотя бы 10, так как для любого существует от 0 до 2 такое, что и . Значит, . Так же , , а вот 7 получить уже не получится. Значит . Отсюда и .

Пусть меньшее из простых чисел равно . Заметим, что так как число хотя бы 4-значное, то . Тогда может оканчиваться на 1, 3, 7 и 9. В этих случаях будут оканчиваться на 5, 1, 7 и 7 соответственно. Так как последнее из чисел не содержит 7, то не может оканчиваться на 7 и 9. Если оканчивается на 1, то оканчивается на 5, простое и больше 10?! Значит, оканчивается на 3 и равно . Тогда число на доске равно . Значит, последнее написанное число равно 21.

Если , то число на доске подходит

Если , то число на доске , 18192021, 161718192021, 15161718192021, 131415161718192021, 12131415161718192021 или 101112131415161718192021 делится на 3, но у числа должны быть только 2 простых делителя и оба больше 10.

Если , то число на доске 1718192021 делится на 7, но у числа должны быть только 2 простых делителя и оба больше 10.

Если , то первое число будет 14?!

Если , то число на доске будет 1112131415161718192021 делится на 11, но точно не равно или .

Если , то , что нам подходит. Пусть . Заметим, что

Положим . Эти числа взаимно просты, так как они нечётны и различаются на 2. Рассмотрим два случая.

1) чётно. Тогда делится на 101. Но и не имеют общих простых делителей, откуда при некотором натуральном . Мы получим

что невозможно, поскольку левая часть кратна 4 , а правая — нет.

2) нечётно. Тогда делится на 101 и аналогично при некотором натуральном . Поэтому

что невозможно, поскольку левая часть кратна 5 , а правая — нет.

Заметим, что единица не окрашена, так как Кроме того, в паре одно из чисел не окрашено. Рассмотрим набор чисел Все эти числа различны, так как Разобьём их на тройки вида где Поскольку в каждой тройке есть хотя бы одно неокрашенное число, а всего имеется таких троек. Таким образом, мы нашли неокрашенных чисел, поэтому количество жёлтых чисел не превосходит

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

Рассмотрим пары вида где В каждой паре имеется хотя бы одно непокрашенное число, поскольку

Аналогичным образом получается, что пары содержат не менее трех непокрашенных чисел. Наконец, числа и не попавшие ни в одну из пар, по условию тоже не окрашены. Таким образом, имеется не менее непокрашенных чисел, откуда

Покажем, что полученная оценка реализуется. Покрасим числа а также все числа от до Пусть и — зеленые числа. Нам достаточно проверить, что не является степенью двойки. Если то это очевидно. В случае мы получаем

Наконец, если и то

Для любого нечётного не кратного рассмотрим геометрическую прогрессию Очевидно, что прогрессии, у которых различные первые члены, не имеют общих членов. Также отметим, что любое число от до входит в какую-то прогрессию.

Всего существует таких прогрессий и из них имеют первый член, больший По условию в прогрессии может быть не более двух чёрных чисел. В прогрессий, у которой первый член больше не более одного чёрного числа (потому что их вторые члены уже больше ). Поэтому, всего не более чёрных чисел.

Предъявим пример: покрасим все нечётные числа между и Предположим, что нашлись такие чёрные числа что и тогда поскольку числа нечётные, противоречие.

Пусть окрашено чисел. Упорядочим их по возрастанию:

Заметим, что для любого справедливо неравенство

Действительно, в противном случае при , имеем

и мы не сможем представить в виде суммы двух красных чисел. Тогда

Значит, и . Осталось привести пример покраски 10 чисел: .

Договоримся восьмеричные числа писать в скобках, чтобы отличать их от десятичных. Запись содержит блоков вида поэтому

Кроме того, откуда

Поделив первое равенство на второе, мы получим

Так как и взаимно просты, на должно делиться число , поэтому нечётно. Заметим, что

где блок повторяется раз. Поскольку и

мы получаем:

где блок из троек повторяется раз. Таким образом, в восьмеричную запись входит троек. С другой стороны, запись числа содержит троек. Поэтому откуда При нам подходит число

Заметим, что

Значит, от 1 до 9 подходит. Осталось доказать, что не походит. Пусть . Тогда , где для и . Докажем, что по индукции.

База: . Значит, нам нужно доказать, что .

Если , то и . Тогда последняя цифра у будет 6, так как у последняя цифра 4, а первая цифра у будет 1 или 2?! Аналогично для .

Переход: Мы доказали, что . Теперь докажем, что . Мы знаем, последние цифр в . Значит мы знаем и первые цифр. Заметим, что . Если , то первая цифра у может быть только 1, с другой стороны для этого , то есть у должна быть последняя цифра 3 и тогда у последняя цифра 9?! Значит .

Отсюда

С другой стороны, для . Значит, при число ?!

Заметим, что Значит И С - С = С(И - 1) Тогда либо делится на 5 и С = 5, либо И - 1 делится на 5 и тогда И = 1 или 6.

Так же заметим, что а с другой стороны сумма цифр произведения это И + К + С. Значит - И - К - С делится на 9. Значит, И + К + С дает остаток 1 или 0 при делении на 9. Так же

и значит И + К + С = 9, 10, 18 или 19.

Пусть И = 1. Тогда последние 2 цифры произведения такие же как у

Заметим, что последние 2 цифры или КС или 0C. Если

то но C не 0?! Значит,

Если С = 2, то К = 6 и тогда нам подходит.

Если С = 3, то К = 1?!

Если С = 4, то К = 4?!

Если С = 5, то К = 5?!

Если С = 6, то К = 4 и С + К + И = 11?!

Если С = 7, то К = 1?!

Если С = 8, то К = 6 и С + К + И = 15?!

Если С = 9, то К = 9 и С + К + И = 11?!

Пусть И = 6. Тогда С нечетное. Так как

и у произведения первая цифра должна быть И = 6, то Понятно, что и поэтому и Если К = 8, то И + К + С = С + 14 = 9, 10, 18 или 19 и из-за того, что С четное, то оно равно 4, но такие И, К и С нам не подходят (проверяется подстановкой). Если К = 9, то И + К + С = С + 15 = 9, 10, 18 или 19 и из-за того, что С четное, то оно равно 4, но такие И, К и С нам не подходят (проверяется подстановкой).

Если С = 5, то И нечетное, не 1 и не 5. Если И = 3, то И + К + С = K + 8 = 9, 10, 18 или 19 и К = 1 или 2, но ни один из этих вариантов не подходит (проверяется подстановкой). Если И = 7, то И + К + С = K + 12 = 9, 10, 18 или 19 и К = 6 или 7, но ни один из этих вариантов не подходит (проверяется подстановкой). Если И = 9, то И + К + С = K + 14 = 9, 10, 18 или 19 и К = 4 или 5, но ни один из этих вариантов не подходит (проверяется подстановкой).

Представим исходное число в виде где — десятичная цифра, — неотрицательные целые числа, причём Стерев цифру мы получим число По условию

Заметим, что иначе и Тогда равенство примет вид В силу условия число оканчивается не на и потому не делится на Значит, и причём Поэтому возможны два случая:

Тогда а исходное число равно где

Тогда а исходное число равно

Представим исходное число в виде

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

Заметим, что (иначе будет отрицательным), откуда . Таким образом, нулём заменяется старшая цифра исходного числа. Кроме того, , иначе . Тогда число кратно 10 и потому оканчивается на 0. В силу условия число оканчивается не на 0. Значит, последняя цифра равна 5 и число нечётно. Поэтому не делится на 16, откуда . Рассмотрим три случая.

1) Пусть . Тогда . Так как число нечетно и меньше 1000, цифра может принимать значения , что дает нам 4 варианта.

2) Пусть . Тогда . Так как число нечетно и меньше 100, цифра равна 2 или 6. Эти значения дают нам еще 2 варианта.

3) Пусть . Тогда . Так как число нечетно и меньше 10, мы получаем .

Заметим, что в 1) получатся четырехзначные числа, во втором случае — трехзначные, в 3 случае — двузначные. Поэтому каждое число, удовлетворяющее условию задачи, входит ровно в один из наборов 1) - 3). Значит, общее количество вариантов равно .

Рассмотрим десять последовательных натуральных чисел. Докажем, что среди них выбрано не более четырех. Если выбрано хотя бы пять чисел, то три из них одной четности, но тогда их попарные разности не могут быть равны лишь 2 и 8. Действительно, если , то и , но тогда , что невозможно.

Таким образом, в каждой десятке не более четырех выбранных чисел, а в первой тысяче чисел их не более 400, поскольку в тысяче сто десяток.

Если взять все числа, оканчивающиеся на или то их будет ровно 400, но никакая разность не равна 4,5 или 6.

Речь идёт о числе Покажем, что оно делится на но не делится на Действительно, То же самое можно сказать про В то время как

То есть по модулю число сравнимо с Учитывая, что имеем Значит, входит в это число в степени, то есть оно не квадрат.