Ошибка.
Попробуйте повторить позже
В некотором числе 10 единиц, 100 двоек, 1000 троек, …, девяток, расположенных в некотором порядке. Каждую секунду в нём стирают последнюю цифру. Правда ли, что в какой-то момент после начального получится число, делящееся на 9?
Источники:
Подсказка 1
Давайте подумаем, каким образом нам можно число, которое кратно 9, независимо от остатка, который будет нами получен на каждом этапе вычеркивания. Удобная конструкция для нас - чтобы в течение 9 шагов у нас постоянно менялся остаток и не повторялся. Тогда, за 9 шагов у нас точно будет момент, когда остаток равнялся 0. Попробуйте придумать такую конструкцию.
Подсказка 2
Давайте попробуем вычеркнуть все 9 из числа(действительно, к чему бы они, если на деление на 9 они никак не влияют). Значит, если докажем, что в какой-то момент было число кратное 9 у полученного числа, то и у начального оно тоже было. Также, заметим, что под нашу конструкцию из первой подсказки подходит вариант, когда у нас стоит много одинаковых цифр подряд(хотя бы 9), взаимнопростых с 9, ведь там будет постоянно меняться остаток. То есть, нам надо набрать много одинаковых цифр подряд. Как это можно сделать?
Подсказка 3
Заметим, что чисел 8 у нас очень много. Больше чем 9 раз суммарно всех остальных. Давайте разобьем наше число на блоки по 9 цифр, которые не пересекаются. Что можно сказать про эти блоки? А что тогда надо доказывать в условиях на восьмерку?
Подсказка 4
Остается доказать, что найдется блок из цифр, равных 8. И это правда, так как иначе, в каждом блоке есть цифра, которая не 8 и тогда, цифр, не равных 8, у нас хотя бы 1/9 от общего количества. Противоречие. Значит, есть блок восьмерок. Победа.
Заметим, что если для исходного числа существует такой момент, то и для числа , полученного вычеркиванием всех девяток из исходного, он так же существует, поскольку каждое вычеркивание не меняет остаток при делении суммы цифр на 9.
Рассмотрим число . В силу неравенства , отношение количества восьмерок к оставшимся числам, больше 9. Отметим подряд идущие блоки по 9 чисел. Докажем, что существует блок, элементами которого являются лишь восьмерки. Пусть это не так, тогда в каждом блоке есть цифра отличная от восьмерки, следовательно, количество цифр, не являющихся восьмерками, хотя бы от общего количество, что противоречит полученному неравенству.
Рассмотрим блок, состоящий только из восьмерок. Пусть число, полученное из вычеркиванием всех цифр до найденного блока, имеет остаток при делении на 9. Каждое вычеркивание 8 увеличивает остаток при делении на 9 на 1, следовательно, вычеркнув элементов в блоке, мы получим искомое число.
Ошибка.
Попробуйте повторить позже
Можно ли число 2024 представить в виде , где и — натуральные числа?
Источники:
Подсказка 1
Если a ≥ 5, то левая часть уже слишком большая. Остаётся перебрать четыре значения для а и проверить, чему равно b
Подсказка 2
Должен найтись подходящий вариант!
Ошибка.
Попробуйте повторить позже
Натуральные числа таковы, что Найдите наибольшее возможное значение величины
Источники:
Подсказка 1
Хочется получить какую-то оценку на эти НОДы. Понятно, что НОД(а,b) не больше чем a. Может попробовать что-то поделать с такой оценкой?
Подсказка 2
Если оценить так каждый НОД, получается как-то слишком грубо. Какой алгоритм приходит в голову, когда речь идёт о НОДах? Конечно же, алгоритм Евклида! Может, как-то улучшить оценку для НОД(a,b) с помощью него?
Подсказка 3
Если воспользоваться алгоритмом Евклида получиться, что: НОД(a,b)=НОД(a,b-a). Тогда т.к. НОД(a,b-a) не больше чем b-a, то и НОД(a,b) будет не больше чем b-a. если сделать тоже самое с НОД(b,c), что получится?
Подсказка 4
Итак, мы имеем что НОД(a,b) не больше b-a, а НОД(b,c) не больше c-b. Если их сложить, получится, что их сумма не больше чем (b-a)+(c-b)=с-а. Если оценить, что НОД(а,с) не больше чем a, то окончательно сумма всех НОДов будет не больше с, которое не больше 3000. Осталось только придумать пример...
Подсказка 5
Понятно, что с=3000. Чтобы достигалась оценка, необходимо, чтобы НОД(a,c)=a. Тогда с делится на a. Если мы сделаем так, что b тоже поделится на a, то, возможно, придумаем пример
Воспользуемся алгоритмом Евклида для получим
Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,
Аналогично получаем, что
А также
Складывая эти три неравенства, получаем
В качестве примера на можно предъявить, например, В этом случае
Ошибка.
Попробуйте повторить позже
Имеется дробь . Семиклассник Семёнов каждую минуту прибавляет к её числителю и знаменателю по и смотрит, можно ли сократить полученную дробь. Семёнов утверждает, что первый раз сократимая дробь получилась после шагов. Стоит ли ему верить?
Источники:
Подсказка 1
Давайте сначала поверим юному математику и посмотрим на дробь через 1000 минут. Какой вывод можно тогда сделать о делимости её знаменателя?
Подсказка 2
Верно, знаменатель кратен какому-то из простых делителей числа 1001. Пусть этот делитель равен p. Если бы мы хотели опровергнуть слова семиклассника, то скорее всего слова о том, что дробь сократилась впервые, верно?
Подсказка 3
Нужно найти такое число, которое выражается через слагаемые n и p и при этом делится на p. Хороша идея взглянуть на знаменатель дроби.
Подсказка 4
Мы обнаружили число n + p - 1, которое делится на р. Это как будто знаменатель дроби через р-1 минуту. А что с её числителем? Найдём противоречие, которое искали в подсказке 2?
Предположим, что Семёнов сказал правду, то есть в первый раз числитель и знаменатель имеют общий делитель больше единицы через минут.
Получится , откуда делится на какое-то число из множества давайте это число обозначим буквой
Заметим, что делится на (если непонятно, то посмотрите, что такое ). Тогда тоже делится на .
Но отсюда сразу следует, что дробь уже через шагов сократима: . А Семёнов сказал, что первый раз дробь сократима будет через шагов. Но . Семёнов, ты не прав!
нет
Ошибка.
Попробуйте повторить позже
Найдите все натуральные числа, у которых разность между суммой двух самых больших собственных делителей и суммой двух самых маленьких собственных делителей является простым числом. (Делитель натурального числа называется собственным, если он отличен от и самого этого числа.)
Источники:
Имеет место один из двух случаев.
(a) Пусть оба наименьших делителя и — простые числа. Тогда простым будет число откуда
Поскольку числа и взаимно просты, то откуда и Но тогда в силу выбора
получаем и
(b) Пусть наименьшие делители имеют вид и где простое. Тогда простым будет число откуда
Поскольку числа и взаимно просты, то Это возможно только в случае В этом
случае откуда Но этот случай невозможен, так как у один из двух наименьших делителей это
Ошибка.
Попробуйте повторить позже
Чётное число называется подходящим, если оно делится на модуль разницы между наибольшим из своих чётных делителей, отличных от , и наибольшим из своих нечётных делителей. Сколько существует подходящих чётных чисел, не превосходящих
Подсказка 1
Попробуем записать число в виде 2^k*m, где m - нечетно. Запишем условие и подумаем, какие ограничения можно наложить на переменные!
Предположим, что число подходящее. Пусть где нечётное. Если то условие говорит, что делится на что возможно только при условии Если и где минимальный простой нечетный делитель то делится на откуда имеем значит, Число или имеет остаток по модулю или имеет остаток по модулю Тем самым число является подходящим, если число может иметь остаток по модулю Это значит, что в каждом ряду из последовательных четных чисел ровно пять подходящих. Используя равенство получаем ответ
Ошибка.
Попробуйте повторить позже
Найдите все натуральные числа от 400 до 600 такие, что если перемножить все делители числа (включая 1 и ), получим число .
Утверждается, что удовлетворяет условию задачи, если и только если его разложение на простые множители имеет вид либо , либо .
Действительно, для каждого имеется делителей числа , содержащих в степени в разложении на простые множители: все эти делители имеют вид . Следовательно, произведение всех делителей числа содержит в степени . Условие, что произведение всех делителей равно , эквивалентно утверждению, что каждое входит в их произведение в степени , и, тем самым, предыдущее выражение равно . Другими словами,
С другой стороны, . Отсюда следует, что . Пусть . Тогда одно из , скажем, равно 1 , а тогда (простота числа 5). В случае, когда , получаем уравнение , то есть . Итак, все числа , удовлетворяющие условию задачи, имеют разложение на простые множители вида либо , либо . Перечислим те из них, которые лежат между 400 и 600.
Числа . Имеем , тем самым, . Итак, . Следовательно, , а, значит,
Выписывая всевозможные произведения , лежащие в промежутке от 400 до 600 , с вышеуказанными и , получаем .
Единственное , лежащее между 400 и 600 , есть . Итого получаем список всех возможных чисел :
Ошибка.
Попробуйте повторить позже
Тройка целых чисел наибольший общий делитель которых равен является решением уравнения
Докажите, что является кубом целого числа.
Источники:
Запишем равенство в следующем виде: Если мы докажем, что НОД и равен то тогда будет кубом. Предположим, что в этой ситуации не является кубом. Тогда в разложение входит какое-то простое число в степени, не кратной Скобка на не делится, значит входит в в степени, не кратной чего быть не может.
Итак, докажем взаимною простоту и Ясно, что НОД этих чисел равен НОДу и предположим, что этот НОД равен Тогда делится на Пусть делится на некоторое простое число тогда на делится и Значит, также делится на Также делится на а значит и на Получается, что НОД и больше противоречие. Значит, НОД и равен что и требовалось.
Ошибка.
Попробуйте повторить позже
Найдите все натуральные числа от до включительно такие, что если перемножить все делители числа (включая и ), получим число
Ясно, что подходит, ведь произведение из условия будет равно Рассмотрим теперь Обозначим произведение его делителей буквой
Если число не является точным квадратом, то его делители можно разбить на пар с произведением в каждой (если число делится нацело на , то оно делится нацело и на ). Например, . Так что делители бьются на пары с произведением в каждой, откуда
По условию , тогда Число должно иметь делителей.
Если число является точным квадратом, то есть ещё делитель поэтому — противоречие с тем, что — целое число пар.
Для количество различных делителей равно (берём каждое простое в каждой степени, считая нулевую). Если число должно иметь ровно делителей, то .
При получаем . Среди чисел от до подходит только
При получаем Из условия на промежуток
.
Добавим также условие , затем остаётся просто перебрать по очереди все , а затем выбрать подходящие простые , получим числа
Ошибка.
Попробуйте повторить позже
Найдите все натуральные числа , такие, что число является точным квадратом натурального числа.
Источники:
Решим уравнение в натуральных числах. Преобразуем левую часть следующим образом: Теперь запишем уравнение в виде Домножим равенство на и разложим левую часть на множители через разность квадратов: Осталось перебрать возможные варианты. Для упрощения перебора заметим, что Следовательно, для скобочек возможны следующие варианты: и и и и Осталось разобрать каждый случай и написать ответ.
Ошибка.
Попробуйте повторить позже
Найдите все пары взаимно простых натуральных чисел и такие, что делится на
Источники:
Подсказка 1
Пусть m = 2а+3b. Тогда отсюда выражается, например, 2а, которое при возведении в квадрат превращается в 4а^2. А у нас в изначальном выражении есть 2а^2, значит таким образом мы сможем узнать что-то о соотношении b и m. Аналогично узнаем про число а и m.
Подсказка 2
Верно, и 15b^2 кратно m, и 10a^2. Используя понимание взаимной простоты чисел а и b мы должны осознать, какие простые делители есть у m.
Подсказка 3
Могут ли простые делители числа m входить в него больше, чем в первой степени? Получив ответ на этот вопрос, мы найдем единственно возможные варианты числа m = 2а+3b и проверим их, помня, что работаем с натуральными числами.
Заметим, что отсюда и Пусть содержит некоторый делитель который взаимно прост с и — тогда на это число должны делиться и что невозможно, поскольку Отсюда делится только на (из простых чисел). Если какое-то простое число входит в него большей степени то делит и значит, степень каждого простого не больше первой. То есть может принимать значения Первые три невозможны, пятёрка даёт нам что подходит. Пятый случай также невозможен, в шестом условие взаимной простоты не выполнено. Для есть случаи и нам подойдёт только второй. Для получаем — подойдут первый и третий случаи. Остаётся выписать ответ.