Оценка + пример в задачах по теории чисел

Известно, что Теперь понятно, что наименьшее число в принципе четырёхзначное, так как трёхзначное число с произведением составить невозможно(как минимум из-за ). Первая наименьшая цифра, которая может идти в разряде тысячных это Она может получиться из первой или В первом случае число во втором Итого наименьшее число

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

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

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

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

Разобьем числа на пары с суммой

В каждой такой паре нужно “испортить” хотя бы одно число. За каждую операцию мы “портим” числа, то есть можем “испортить” максимум две пары. Нужно “испортить” пар, поэтому нужно минимум операций. Приведем пример на действий:

Сложим сначала с , затем с и так далее до . После проделанных действий получаем

Ряд не содержит числа , а также никакие несколько чисел не дают в сумме , так как их сумма как минимум

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

6 простых чисел уже может быть:

У числа шестнадцать делителей и все они являются делителями числа . Если делится на , то к этим делителям добавляются ещё числа 16,48 и 80 , то есть 120 — это уже как минимум девятнадцатый делитель.

Если делится на , то к исходным шестнадцати делителям добавляются 9,18 и 45 . Если делится на , то к исходным шестнадцати делителям добавляются 25,50 и 75.

Значит, делится на какое-то простое число , кроме 2,3 и 5 . Если это число не превосходит 40 , то числа и являются делителями , меньшими 120 , и мы опять получаем слишком много делителей. Значит, хотя бы 41 , то есть . Заметим, что это число нас как раз устраивает.

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

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

Сумма любых четырех соседних чисел положительна, поэтому среди них должно быть хотя бы одно положительное число.

Возьмем какое-то положительное число из чисел (такое найдется, потому что в кругу чисел ). Оставшиеся числа разобьем на группы по последовательных числа.

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

Приведем пример на отрицательных чисел:

Поскольку произведение первых 6 натуральных чисел равно то искомое число не больше

Осталось доказать, что произведение любых подряд идущих 6 натуральных чисел делится на . Поделим:

и получим натуральное число способов выбрать шестёрку из элементов. Действительно, делится.

Оценка.

Будем считать, что первое число в тройках минимальное из трёх, последнее — максимальное. Рассмотрим произвольную тройку где . Ясно, что , откуда , откуда . Таким образом, первыми числами в тройке могут быть лишь числа от до . Значит, всего можно взять не больше троек, так как числа не повторяются.

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

Пример.

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

Давайте попробуем составить какое-нибудь число. Например, Получается 7-значное число, которое значительно больше одного миллиона. Попробуем составить минимально возможное 7-значное число. Для этого нужно выбирать на каждом шаге карточку с минимальной первой цифрой, но у нас две карточки с первой цифрой 5, рассмотрим два случая. Первый вариант — второй — Второе число ближе к 1 000 000. Но можно брать не все карточки и получить 6-значное число. 6-значное число получается из 7-значного убиранием одной цифры. Так как у нас только одна карточка с одной цифрой, то нужно не использовать именно её. Любое 6-значное число меньше одного миллиона, поэтому нужно составить максимально возможное число. Тогда искомое 6-значное число —

Рассматривать 5-значные и меньшие числа нет смысла, так как они будут находиться точно дальше от одного миллиона, чем 6-значные. Тогда нужно только сравнить, какое из чисел и ближе к 1 000 000.

Значит, искомое число — это

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

Докажем для начала, что четырьмя и меньше цветами обойтись не удастся. Посмотрим на числа . Разности между ними равны

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

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

Докажем теперь, что пять цветов достаточно. Для этого разобьём все натуральные числа на группы по 5 подряд идущих чисел, а группы покрасим так: первую - в первый, вторую - во второй, ..., пятую - в пятый, шестую - в первый, седьмую - во второй, .... При такой раскраске числа одного цвета будут или отличаться не более чем на 4, если лежат в одной пятёрке, или хотя бы на 21 - если в разных. Значит, числа, отличающиеся на и 18, будут покрашены в разные цвета.

Заметим, что Тогда

Получается, что всегда делится на . Чтобы делилось на , получается, что делится на откуда , а наибольшее натуральное равно

Чтобы произведение было минимальным, числа не должны иметь простых делителей, отличных от и

Пусть (показатели всех степеней — целые неотрицательные числа). Тогда

Рассмотрим отдельно делимость на и

Из того, что делится на делится на делится на следует, что

Складываем полученные неравенства и получаем:

Покажем, что значение достигается. Для этого возьмём

Из того, что делится на делится на делится на следует, что

Складываем полученные неравенства и получаем:

Покажем, что значение достигается. Для этого возьмём

Из того, что делится на следует, что Заметим, что

может равнятся если, например,

Так как минимум каждой из трёх сумм не зависит от оставшихся, то и минимальное значение равно

Пример для

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

Если — нечётное, то возьмём числа и Суммы, где оба слагаемых одного знака, по модулю больше Суммы, в которых слагаемые разных знаков, принимают значения из отрезка

Теперь докажем оценку на по индукции:

База при Есть числа Если выбрать все, то Выбрать числа можно.

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

Ясно, что в этом случае брать нельзя. Рассмотрим случаи.

Если чётно, то разобьём оставшиеся числа на пары: и — штук.

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

Если нечётно, то разобьём так: и Числа оставим без пары. Получили пару, из каждой можно взять не более числа. Также среди чисел можно взять не более одного, потому что Таким образом, мы взяли не более чисел. Оценка доказана.

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

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

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

Выберем числа Их попарные разности кратны трём, поэтому, очевидно, не равняются 1, 4 или 5. При этом выбранных чисел ровно 675, то есть максимально возможное количество.

Текущий год — это год 21 века, поэтому номер года точно четырёхзначный, поэтому нулями являются разряд десятков и либо разряд единиц, либо разряд сотен. В первом случае ближайшим годом может быть 2000 или 2100, а во втором — 2009. В текущий год ближайшим является 2009. Ответ поменяется в 2055 году, когда до 2100 будет 45 лет, а до 2009 — 46 лет.

Обозначим количество леденцов у Кати, Лизы, Маши и Насти соответственно за . Тогда . Складывая эти неравенства, получаем . Причем , откуда , или же в целых числах . Пример на существует: .

Докажем, что год должен быть . В каждом разряде искомого года должна стоять , и год должен быть => искомый год .

Заметим, что 2111 год подходит.