Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given a number K of length N, the task is to find the smallest possible number that can be formed from K of N digits by swapping the digits any number of times.
Examples:
Input: N = 15, K = 325343273113434
Output: 112233333344457
Explanation:
The smallest number possible after swapping the digits of the given number is 112233333344457Input: N = 7, K = 3416781
Output: 1134678
Approach: The idea is to use Hashing. To implement the hash, an array arr[] of size 10 is created. The given number is iterated and the count of occurrence of every digit is stored in the hash at the corresponding index. Then iterate the hash array and print the ith digit according to its frequency. The output will be the smallest required number of N digits.
Below is the implementation of the above approach:
C++
#include <iostream>
using namespace std;
string smallestPoss(string s, int n)
{
string ans = "";
int arr[10] = { 0 };
for (int i = 0; i < n; i++) {
arr[s[i] - 48]++;
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < arr[i]; j++)
ans = ans + to_string(i);
}
return ans;
}
int main()
{
int N = 15;
string K = "325343273113434";
cout << smallestPoss(K, N);
return 0;
}
Java
import java.util.*;
import java.io.*;
class GFG
{
static String smallestPoss(String s, int n)
{
String ans = "";
int arr[] = new int[10];
for (int i = 0; i < n; i++)
{
arr[s.charAt(i) - 48]++;
}
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < arr[i]; j++)
ans = ans + String.valueOf(i);
}
return ans;
}
public static void main(String[] args)
{
int N = 15;
String K = "325343273113434";
System.out.print(smallestPoss(K, N));
}
}
Python3
def smallestPoss(s, n):
ans = "";
arr = [0]*10;
for i in range(n):
arr[ord(s[i]) - 48] += 1;
for i in range(10):
for j in range(arr[i]):
ans = ans + str(i);
return ans;
if __name__ == '__main__':
N = 15;
K = "325343273113434";
print(smallestPoss(K, N));
C#
using System;
class GFG
{
static String smallestPoss(String s, int n)
{
String ans = "";
int []arr = new int[10];
for (int i = 0; i < n; i++)
{
arr[s[i] - 48]++;
}
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < arr[i]; j++)
ans = ans + String.Join("",i);
}
return ans;
}
public static void Main(String[] args)
{
int N = 15;
String K = "325343273113434";
Console.Write(smallestPoss(K, N));
}
}
Javascript
<script>
function smallestPoss(s, n)
{
var ans = "";
var arr = Array(10).fill(0);
for (var i = 0; i < n; i++) {
arr[s[i].charCodeAt(0) - 48]++;
}
for (var i = 0; i < 10; i++) {
for (var j = 0; j < arr[i]; j++)
ans = ans + i.toString();
}
return ans;
}
var N = 15;
var K = "325343273113434";
document.write( smallestPoss(K, N));
</script>
Time Complexity: O(N)
Auxiliary Space: O(N + 10)
Last Updated :
20 Dec, 2022
Like Article
Save Article
|
Введём обозначения $%x$% и $%y$% для числа орехов в первой и второй коробке. Тогда первое условие означает, что $%2(x-100)=y+100$%, то есть $%2x=y+300$%. Теперь пусть из второй коробки переложили в первую какое-то количество $%k$% орехов, где $%0 < k < y$%. Тогда $%x+k=6(y-k)$%. Это значит, что $%x+7k=6y$%. Выражая из первого уравнения $%y=2x-300$% и подставляя во второе уравнение, получим $%x+7k=12x-1800$%, то есть $%11x=7k+1800$%. Теперь надо найти наименьшее натуральное $%k$%, при котором число в правой части делится на $%11$%. Разделим $%1800$% на $%11$% с остатком. Частное равно $%163$%, остаток равен $%7$%. Таким образом, $%11x=7k+11cdot163+7$%, то есть $%11(x-163)=7(k+1)$%. Отсюда понятно, что $%k+1$% должно делиться на $%11$%, а наименьшее значение будет при $%k=10$%. Следовательно, $%x-163=7$%, откуда находим наименьшее возможное $%x$%, а далее по формулам выражаем через него $%y$%. В конце полезно сделать проверку. |
На этой странице вы узнаете
- Как реализуется динамическое решение задачи?
- Бери топор, руби хардкор. Как разделить целостную задачу на части и получить с этого приятности?
- Как динамический метод решения кодом Python может облегчить нашу жизнь?
Подозвал старец своих сыновей, дал им веник и сказал сломать его.
— Мы не можем, отец, — ответили они ему.
Тогда старец развязал веник и сказал им ломать прутья по отдельности.
— Это очень просто, отец, — сказали они ему.
— В этом и заключается идея динамического подхода к решению задач, — ответил он им.
А теперь давайте разбираться, что же там такого легкого и как это поможет нам в жизни.
Принцип динамического подхода
Идея динамического решения состоит в том, чтобы делить одну сложную задачу на несколько подзадач меньшего размера и сложности. Основываясь на результате, мы можем искать итоговый ответ.
Если подробнее, то план динамического решения состоит в следующем:
- Разбиение задачи на подзадачи меньшего размера.
- Нахождение оптимального решения подзадач.
- Использование полученного решения подзадач для получения решения исходной задачи.
Решение подзадачи происходит делением ее на еще более мелкие подзадачи до тех пор, пока не будет получена подзадача, ответ на которую заранее известен или считается моментально.
По сути, готовясь к экзаменам, вы уже решаете эту проблему динамически:
- Чтобы подготовиться к экзамену, надо подготовиться к каждому отдельному заданию.
- Чтобы подготовиться к заданию, нужно прорешать задачи на возможные вариации этого задания.
- Чтобы прорешать задачи, необходимо изучить теорию.
В итоге глобальная задача “Подготовка к экзамену” превратилась в набор конкретных последовательных действий. Мы нашли, с чего нам нужно начать. Выполнив самую маленькую подзадачу, сможем выполнить подзадачу больше, а затем решить подзадачу еще больше. Рано или поздно мы решим и исходную, самую большую задачу.
Динамическое решение задач на графы
Поиск необходимого маршрута — хороший пример задачи, которая легче решается динамически, причем в каком бы то ни было виде.
Например, нам дана цель максимально быстро пройти через болото из одного его конца в другой. Карта самого этого болота представлена в виде таблицы, каждый сектор которой имеет значения опасности и дискомфорта.
Раз добраться надо максимально быстро, будем двигаться только по направлению к финишу — вниз и вправо. Но также мы хотим набрать как можно меньше очков опасности и дискомфорта. Мы не любим опасность и дискомфорт. Каждый раз, заходя в ячейку, мы “собираем” значение из нее, накапливая очки.
Наша глобальная задача: узнать, какое наименьшее возможное количество очков дискомфорта мы можем собрать, пройдя по всему болоту.
Разбивая эту задачу на подзадачи, будем постепенно узнавать наименьшие значения собранных очков там, куда мы можем пройти:
- Можем узнать, сколько мы получим очков в ячейках, соседних с начальной.
- Зная новые значения, узнаем соседние уже с ними. Выберем наименьшее значение там, где это возможно.
- Продолжим заполнять соседние ячейки, пока не дойдем до самого конца.
Для удобства и большего взаимопонимания можем пронумеровать все ячейки и сразу сделать первые возможные шаги из начальной позиции вправо и вниз.
Так как в А1 нет никакого начального значения очков, в ячейках В1 и А2 останутся соответствующие им значения.
Следующие шаги мы уже делаем из этих позиций. Мы можем пройти вправо или вниз. К ячейкам, в которые мы заходим, будем прибавлять значение предыдущих пунктов. Пройдя через них, мы соберем их значения.
В С1 и А3 можно прийти только с одной стороны, слева и сверху соответственно. Для В2 есть выбор — пройти сверху или слева?
Так как мы хотим собрать наименьшее возможное количество очков, будем идти в В2 из наименьшего варианта.
Эта логика продолжается — с помощью ячеек, в которых мы нашли кратчайшие пути, ищем оптимальные пути в следующие — А4, В3, С2 и D1.
И так до самого конца, пока не найдем значение в интересующей нас ячейке D4:
Применяя метод динамического решения, мы находили наименьшие возможные собранные значения очков в каждой ячейке, до которой смогли добраться. Используя эти значения, мы определяли, какие значения будут собраны дальше и повторяли до тех пор, пока не нашли значение в самой последней ячейке.
Динамическое программирование
Вспомним принцип работы рекурсивной функции из статьи «Функция и рекурсия». Она при необходимости может вызвать саму же себя с другими входными значениями. Здесь можно провести аналогию с методом динамического решения. И там, и там для подсчета итогового результата будут высчитываться промежуточные значения.
Для решения динамических задач программированием действительно можно использовать рекурсивную функцию. Так мы свалим всю работу по решению на программу, а сами потратим время на что-нибудь приятное.
Рассмотрим это на примере поиска чисел Фибоначчи.
Первое и второе числа Фибоначчи — единицы. Каждое последующее число будет равно сумме двух предыдущих.
Например, мы хотим найти пятое число Фибоначчи, обозначим его как Fib(5).
При ручном решении мы бы искали его как сумму двух предыдущих чисел Фибоначчи, а предыдущие числа — как сумму предыдущих для них:
- Fib(5) = Fib(4) + Fib(3)
- Fib(4) = Fib(3) + Fib(2)
- Fib(3) = Fib(2) + Fib(1)
- Fib(2) = 1
- Fib(1) = 1
Найдя исходные значения, которые мы знаем, мы двигались бы в обратную сторону, высчитывая каждое следующее число Фибоначчи, пока не нашли бы значение нужного:
- Fib(3) = Fib(2) + Fib(1) = 1 + 1 = 2
- Fib(4) = Fib(3) + Fib(2) = 2 + 1 = 3
- Fib(5) = Fib(4) + Fib(3) = 3 + 2 = 5
Похожим принципом будет работать и рекурсивная функция — только с нашими минимальными усилиями:
- Объявим ее командой def и передадим ей на вход номер числа Фибоначчи, которое мы хотим найти.
- Запишем условие выхода — первое и второе число Фибоначчи равны единице.
- Если число не первое и не второе, оно равно сумме двух предыдущих.
def Fib(n):
if n == 1 or n == 2:
return 1
else:
return Fib(n - 1) + Fib(n - 2)
print(Fib(5))
Вывод: 5Фактчек
- Принцип динамического подхода заключается в разбиении целостной задачи на маленькие подзадачи и поиске итогового ответа на основе решения этих подзадач.
- Каждая подзадача решается разбиением ее на еще более мелкие подзадачи до тех пор, пока мы не получим самую простую подзадачу, ответ на которую известен заранее или может быть рассчитан простым действием.
- Для реализации динамического решения программой из-за схожести принципа работы используется рекурсивная функция.
Проверь себя
Задание 1.
Что подразумевает метод динамического решения задачи?
- Быстрое, веселое и энергичное решение задачи под музыку.
- Решение задачи строго по описанному в условии алгоритму.
- Разбиение задачи на более мелкие подзадачи.
Задание 2.
Реализация динамического решения задачи программированием…
- … невозможна.
- … осуществляется с помощью вложенных циклов.
- … осуществляется с помощью рекурсии.
Задание 3.
Вернитесь чуть выше, к задаче про болото. Какой был бы ответ на эту задачу с той же таблицей, если бы надо было собрать не наименьшее, а наибольшее количество очков?
- 155
- 71
- 73
- 110
Ответы: 1. — 3; 2. — 3; 3. — 1.
15. В лесу на разных кустах висят 100 шнурков. Сова утверждает, что в среднем 3 шнурка из четырех, которые можно найти в лесу, ей не подходят, поскольку они слишком длинные для дверного звонка. Ослик Иа утверждает, что в среднем 4 из пяти шнурков из леса ему не подходят, поскольку они слишком короткие, чтобы сделать из них хвост. Оба правы. сколько шнурков, висящих на кустах, не подходят ни Сове, ни Иа? Найди наименьшее возможное число.
19. Задачи на теорию чисел
1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения
Решение задач на теорию чисел из ЕГЭ прошлых лет
Задание
1
#6330
Уровень задания: Равен ЕГЭ
На доске написано 10 различных натуральных чисел. Среднее арифметическое шести наименьших из них равно 5, а среднее арифметическое шести наибольших из них равно 15.
а) Может ли наименьшее из этих десяти чисел равняться 3?
б) Может ли среднее арифметическое всех десяти чисел равняться 11?
в) Найдите наибольшее среднее арифметическое всех чисел.
(ЕГЭ 2018, основная волна)
а) Когда в задаче дается набор различных натуральных чисел, а также дается либо сумма чисел, либо их среднее арифметическое (зная среднее арифметическое чисел и их количество, можно легко посчитать их сумму), как правило, работает классическая идея минимальной суммы.
Предположим, что наименьшее число равно 3. Тогда наименьшая возможная сумма шести наименьших чисел равна (3+4+5+6+7+8=33). Тогда наименьшее среднее арифметическое шести наименьших чисел равно (frac{33}6>5).
Мы взяли шесть самых маленьких различных натуральных чисел при условии, что наименьшее из них равно 3. И если их среднее арифметическое оказалось больше 5, то и среднее арифметическое шести любых различных натуральных чисел, наименьшее из которых равно 3, будет больше 5.
Следовательно, мы получили противоречие, значит, наименьшее число в наборе не может быть равно 3.
б) Пусть мы имеем набор упорядоченных по возрастанию чисел (a_1,
a_2, dots, a_{10}). Так как ((a_1+a_2+dots+a_6):6=5), то (a_1+dots +a_6=30). Аналогично (a_5+a_6+dots a_{10}=90). Тогда (a_1+a_2+dots +a_{10}+(a_5+a_6)=120).
Наименьшее возможное значение (a_5) – это 5, так как числа натуральные и различные и они упорядочены по возрастанию. Тогда самое маленькое возможное значение (a_6) – это 6. Но тогда наибольшая возможная сумма (a_1+dots +a_{10}=120-(5+6)=109). Но тогда наибольшее возможное среднее арифметическое всех десяти чисел равно (109:10=10,9<11). Следовательно, среднее арифметическое всех чисел не может быть равно 11.
в) В предыдущем пункте мы сказали, что (a_1+a_2+dots
+a_{10}=120-(a_5+a_6)). Следовательно, для того, чтобы найти наибольшую возможную сумму всех чисел, нужно найти наименьшую возможную сумму (a_5+a_6).
Ранее мы доказали, что минимальная сумма (a_5+a_6=11). Заметим, что, учитывая условие, что сумма наименьших шести чисел равна 30, такая ситуация невозможна: наибольшее возможное (a_5) тогда равно 5, значит, наибольшая возможная сумма первых четырех чисел равна (1+2+3+4=10), откуда мы получаем, что наибольшая сумма первых шести чисел равна (1+2+3+4+5+6<30).
Рассмотрим случаи:
1) Пусть (a_5+a_6=12). Тогда (a_1+a_2+a_3+a_4=18). Тогда наибольшее возможное значение для (a_5) – это 5. Следовательно, наибольшая возможная сумма первых четырех чисел равна (1+2+3+4<18). Следовательно, такой случай невозможен.
2) Пусть (a_5+a_6=13). Тогда (a_1+a_2+a_3+a_4=17). Тогда наибольшее возможное значение для (a_5) – это 6. Следовательно, наибольшая возможная сумма первых четырех чисел равна (2+3+4+5<17). Следовательно, такой случай невозможен.
3) Пусть (a_5+a_6=14). Тогда (a_1+a_2+a_3+a_4=16). Тогда наибольшее возможное значение для (a_5) – это 6. Следовательно, наибольшая возможная сумма первых четырех чисел равна (2+3+4+5<16). Следовательно, такой случай невозможен.
4) Пусть (a_5+a_6=15). Тогда (a_1+a_2+a_3+a_4=15). Тогда наибольшее возможное значение для (a_5) – это 7. Следовательно, наибольшая возможная сумма первых четырех чисел равна (3+4+5+6=18). Это не больше 15, следовательно, противоречия мы не получили. Попробуем построить пример.
Возьмем (a_5=7, a_6=8). Возьмем также (a_1=2, a_2=3, a_3=4, a_4=6). Тогда действительно (a_1+dots +a_6=2+3+4+6+7+8=30).
Подберем последние четыре числа: (a_7=9, a_8=10, a_9=11, a_{10}=45). Действительно (a_5+dots +a_{10}=90).
Пример приведен, следовательно, наибольшая возможная сумма десяти чисел равна (120-15=105). Тогда наибольшее вреднее арифметическое всех чисел равно (10,5).
Ответ:
а) нет
б) нет
в) 10,5
Задание
2
#4033
Уровень задания: Равен ЕГЭ
Пусть (q) – наименьшее общее кратное, а (d) – наибольший общий делитель натуральных чисел (x) и (y), удовлетворяющих равенству (7x=16y-73).
а) Может ли (dfrac qd) быть равным (204)?
б) Может ли (dfrac qd) быть равным (2)?
в) Найдите наименьшее значение (dfrac qd).
(ЕГЭ 2018, СтатГрад, 19 апреля 2018)
а) Предположим, что существуют такие (x,y), что (q:d=204).
Рассмотрим самый простой случай, когда (d=1), то есть числа взаимно просты. Тогда (q=204).
Так как (qcdot d=xcdot y), то получаем: (xy=204).
Заметим, что (204=2^2cdot 3cdot 17). Следовательно, нужно составить из множителей (2, 2, 3, 17) такие числа (x) и (y), чтобы их НОД был равен (1), и они подходили в (7x=16y-73). Перебором убеждаемся, что подходят (x=17) и (y=12).
Ответ: да.
б) Выпишем решения уравнения (7x=16y-73) в натуральных числах. Выразим: [x=dfrac{16y-73}7=2y-10+dfrac{2y-3}7] Чтобы (x) был натуральным, как минимум нужно, чтобы (frac{2y-3}7) было целым числом. Это возможно только тогда, когда (2y-3) делится без остатка на (7). Все возможные остатки при делении (y) на (7) – это (0, 1, 2, 3, 4, 5, 6). Заметим, что нам подходит только случай, когда (y) при делении на (7) дает в остатке (5), то есть (y=7k+5) ((kgeqslant 0)). Тогда [x=2(7k+5)-10+dfrac{2(7k+5)-3}7=16k+1, kgeqslant 0] Таким образом, решением уравнения (7x=16y-73) будут (x=16k+1,
y=7k+5), (kgeqslant 0).
Предположим, что существуют такие (x,y), что (q:d=2).
1) Если (d=1), то (q=2). Следовательно, аналогично пункту а), (2=q=xy).
Заметим, что так как (kgeqslant 0), то (xygeqslant (0+1)(0+5)=5). Следовательно, (q) не может быть равно (2). Получили противоречие.
2) Пусть (d>1). Следовательно, можно записать (x=ds), (y=dr) ((s,r) – натуральные). И тогда уравнение (7x=16y-73) перепишется как (d(16r-7s)=73). Тогда, так как (d, r, s) – натуральные числа, то (73) должно делиться на (d). Но (73) – простое число, и делится только на (1) или на (73). Следовательно, (d=73). Тогда (16r-7s=1). Полученное уравнение также можно решить в натуральных числах (аналогично пункту б)) и получить решения (r=7p+4), (s=16p+9), (pgeqslant 0).
Следовательно, (x=73(16p+9)), (y=73(7p+4)), (pgeqslant 0).
Тогда (2cdot 73^2=frac qdcdot d^2=qd=xy).
Но (xygeqslant 73(0+9)cdot 73(0+4)=73^2cdot 9cdot 4), а это явно больше (2cdot 73^2). Следовательно, также получили противоречие.
Ответ: нет.
в) Заметим, что в пункте б) мы доказали, что существует лишь два варианта, чему может быть равно (d): либо (1), либо (73). Причем:
1) если (d=1), то (xygeqslant 5). Значит, (q:d=q=xygeqslant 5), то есть минимальное значение для (q:d=5).
2) если (d=73), то (xygeqslant 73^2cdot 9cdot 4). Значит, (q:d=xy:d^2geqslant73^2cdot 9cdot 4:73^2=36). То есть минимальное значение для (q:d) равно (36).
Таким образом, мы видим, что минимально возможное значение для (q:d) равно (5).
Приведем пример.
Этот минимум мы получили из случая, когда (d=1) и (x=16k+1), (y=7k+5) при (k=0). Следовательно, пример: (x=1, y=5).
Ответ:
а) да
б) нет
в) 5
Задание
3
#4014
Уровень задания: Равен ЕГЭ
Последовательность (a_1, a_2, dots, a_n, dots) состоит из натуральных чисел, причем (a_{n+2}=a_{n+1}+a_n) при всех натуральных (n).
а) Может ли выполняться равенство (4a_5=7a_4)?
б) Может ли выполняться равенство (5a_5=7a_4)?
в) При каком наибольшем натуральном (n) может выполняться равенство (6na_{n+1}=(n^2+24)a_n)?
(ЕГЭ 2018, СтатГрад, 26 января 2018)
а) Пусть (a_1=x), (a_2=y). Тогда (a_3=x+y, a_4=x+2y, a_5=2x+3y). Предположим, что выполняется (4a_5=7a_4). Тогда: [4(2x+3y)=7(x+2y)quadLeftrightarrowquad x=2y] Если взять, например, (x=2), (y=1), то получим последовательность: (2, 1, 3, 4, 7, dots) Следовательно, такое возможно.
б) Аналогично пункту а): [5(2x+3y)=7(x+2y)quadLeftrightarrowquad 3x=-y] Следовательно, один из (x) или (y) должен быть отрицательным (оба они не могут быть равны (0), так как последовательность состоит из натуральных чисел). Но это невозможно, так как последовательность состоит из натуральных чисел. Следовательно, ответ: нет.
в) Отметим основные свойства последовательности, где (a_{n+1}=a_n+a_{n-1}) при натуральных (ngeqslant 2). Заметим, что первые два элемента этой последовательности задаются произвольно, а вот каждый следующий, начиная с третьего, равен сумме двух предыдущих. Следовательно, так как последовательность состоит из натуральных чисел, то каждый элемент, начиная с третьего, больше предыдущего, то есть (a_{n+1}:a_n>1) при (ngeqslant 2).
Это же свойство можно переформулировать по-другому: каждый элемент, начиная со второго, меньше следующего: (a_n:a_{n+1}<1) при (ngeqslant 2).
Но тогда [dfrac{a_{n+1}}{a_n}=1+dfrac{a_{n-1}}{a_n}<1+1=2, quad ngeqslant 3] (каждый элемент, начиная с 4-ого, менее чем в два раза больше предыдущего)
Предположим, что равенство (6na_{n+1}=(n^2+24)a_n) вплоть до какого-то большого (n) (то есть (ngeqslant 3)). Тогда [dfrac{a_{n+1}}{a_n}=dfrac{n^2+24}{6n}<2] Решим неравенство: [dfrac{n^2+24}{6n}<2quadRightarrowquad n^2-12n+24<0
quadLeftrightarrowquad nin (6-sqrt{12};6+sqrt{12})] Так как (n) – натуральное, а (9<6+sqrt{12}<10), то (nleqslant 9).
Следовательно, наибольший элемент, для которого может быть выполнено равенство из пункта в), это (a_{10}).
Попробуем привести пример. Для этого нам понадобиться равенство (a_{n+2}=a_{n+1}+a_n) использовать в виде (a_n=a_{n+2}-a_{n+1}), а также то, что каждый элемент последовательности, начиная с третьего, должен быть больше предыдущего.
Пусть (n=9). Тогда [begin{aligned}
&6cdot 9cdot a_{10}=105a_9\
&18a_{10}=35a_9quadRightarrow\
&a_{10}=35k\
&a_9=18k\
&a_8=17k\
&a_7=k\
&a_6=16kend{aligned}] Получили, что (a_6>a_7) – противоречие.
Пусть (n=8). Тогда [begin{aligned}
&6cdot 8cdot a_9=88a_8\
&6a_9=11a_8quadRightarrow\
&a_9=11k\
&a_8=6k\
&a_7=5k\
&a_6=k\
&a_5=4kend{aligned}] Получили противоречие.
Пусть (n=7). Тогда [begin{aligned}
&6cdot 7cdot a_8=73a_7quadRightarrow\
&a_8=73k\
&a_7=42k\
&a_6=31k\
&a_5=11k\
&a_4=20kend{aligned}] Получили противоречие.
Пусть (n=6). Тогда [begin{aligned}
&6cdot 6cdot a_7=60a_6\
&3a_7=5a_6quadRightarrow\
&a_7=5k\
&a_6=3k\
&a_5=2k\
&a_4=k\
&a_3=kend{aligned}] Получили противоречие.
Пусть (n=5). Тогда [begin{aligned}
&6cdot 5cdot a_6=49a_5quadRightarrow\
&a_6=49k\
&a_5=30k\
&a_4=19k\
&a_3=11k\
&a_2=8k\
&a_1=3kend{aligned}] Противоречия нет, следовательно, наибольшее возможное (n) – это (n=5). Пример: (3; 8; 11; 19; 30; 49).
Ответ:
а) да
б) нет
в) 5
Задание
4
#3253
Уровень задания: Равен ЕГЭ
С натуральным числом проводят следующую операцию: между каждыми двумя его соседними цифрами записывают сумму этих цифр (например, из числа (194) получается число (1109134)).
а) Приведите пример числа, из которого получается число (411781109).
б) Может ли из какого-нибудь числа получиться число (210811495)?
в) Какое наибольшее число, кратное (9), может получиться из трехзначного числа, в десятичной записи которого нет девяток?
(ЕГЭ 2017, резервный день)
а) Так как (4+7=11), то первая цифра искомого числа (4), вторая (7): (47…)
Так как (7+1=8), то третья цифра – это (1): (471…)
Аналогично четвертая, последняя, цифра числа – это (9).
Таким образом, число (4719).
б) Предположим, что такое число существует. Начнем так же, как в пункте а), определять цифры этого числа слева направо. Очевидно, что первые две цифры – это (2) и (8), то есть число (28…)
Третья цифра не может быть (1), так как (8+1ne 1), также третья цифра не может быть (4), так как (8+4ne 11). Также она не может быть равна (9) или (5), так как в этом случае сумма двух цифр уже должна быть равна трех- или четырехзначному числу.
Следовательно, ответ: нет.
в) Пусть дано трехзначное число (overline{abc}). Тогда из него получится число (N=overline{a,(a+b),b,(b+c),c}).
Заметим, что при (a+bgeqslant 10) и (b+cgeqslant 10) данное число будет семизначным, а во всех остальных случаях — шести- или пятизначным. Таким образом, так как мы ищем наибольшее возможное число, то найдем его среди семизначных чисел.
Пусть (a+b=10+x, b+c=10+y), где (0leqslant x,yleqslant 6) (так как (a, b, cne 9)).
Тогда число имеет вид: (N=overline{a1xb1yc}).
По признаку делимости число делится на (9) тогда и только тогда, когда сумма его цифр кратна (9). То есть: [a+1+x+b+1+y+c vdots 9] Так как (x=a+b-10), (y=b+c-10), то получаем: [a+1+a+b-10+b+1+b+c-10+c vdots 9quadRightarrowquad
2a+3b+2c-2cdot 9 vdots 9 quadRightarrowquad 2a+3b+2c
vdots 9] Для того, чтобы число (N) было наибольшим, его первая цифра должна быть наибольшей. Следовательно, если возьмем наибольшее возможное (a=8), тогда можно взять наибольшее возможное (b=8). Следовательно, для того, чтобы (2a+3b+2c vdots 9), нужно взять (c=7).
Таким образом, наибольшее число получится из числа (887) и равно (N=8168157).
Ответ:
а) 4719
б) нет
в) 8168157
Задание
5
#3240
Уровень задания: Равен ЕГЭ
С натуральным числом проводят следующую операцию: между каждыми двумя его соседними цифрами записывают сумму этих цифр (например, из числа (194) получается число (1109134)).
а) Приведите пример числа, из которого получается число (176148179).
б) Может ли из какого-нибудь числа получиться число (3107611090)?
в) Какое наибольшее число, кратное (11), может получиться из трехзначного числа?
(ЕГЭ 2017, резервный день)
а) Так как (1+6=7), то первая цифра искомого числа (1), вторая (6): (16…)
Так как (6+8=14), то третья цифра – это (8): (168…)
Аналогично четвертая, последняя, цифра числа – это (9).
Таким образом, число (1689).
б) Предположим, что такое число существует. Начнем так же, как в пункте а), определять цифры этого числа слева направо. Очевидно, что первые две цифры – это (3) и (7), то есть число (37…)
Третья цифра не может быть (1), так как (7+1ne 6) и (7+1ne 61). Также она не может быть равна (0), (9) или (0), так как в этом случае сумма двух цифр уже должна быть равна трех-, четырех- или пятизначному числу.
Следовательно, ответ: нет.
в) Пусть дано трехзначное число (overline{abc}). Тогда из него получится число (N=overline{a,(a+b),b,(b+c),c}).
Заметим, что при (a+bgeqslant 10) и (b+cgeqslant 10) данное число будет семизначным, а во всех остальных случаях — шести- или пятизначным. Таким образом, так как мы ищем наибольшее возможное число, то найдем его среди семизначных чисел.
Пусть (a+b=10+x, b+c=10+y), где (0leqslant x,yleqslant 
.
Тогда число имеет вид: (N=overline{a1xb1yc}).
По признаку делимости число делится на (11) тогда и только тогда, когда сумма его цифр, стоящих на нечетных местах, минус сумма цифр, стоящих на четных местах, кратна (11). То есть: [(a+x+1+c)-(1+b+y):11] Так как (x=a+b-10), (y=b+c-10), то получаем: [(a+a+b-10+1+c)-(1+b+b+c-10):11quadRightarrowquad 2a-b:11] Для того, чтобы число (N) было наибольшим, его первая цифра должна быть наибольшей. Следовательно, если (a=9), то (b=7) (чтобы (2a-b:11)). Заметим, что (c) может быть любым. Следовательно, возьмем максимальное (c=9).
Таким образом, наибольшее число получится из числа (979) и равно (N=9167169).
Ответ:
а) 1689
б) нет
в) 9167169
Задание
6
#3286
Уровень задания: Равен ЕГЭ
Учитель задумал несколько натуральных чисел (не обязательно различных). Эти числа и все их возможные произведения (по два числа, по три числа и т.д.) он выписал на доску. Если какое-то число, выписанное на доску, повторяется несколько раз, то на доске оставляют только одно такое число, а другие числа, равные ему, стирают.
Например, если задуманы числа (1, 5, 6, 5), то на доске будет набор (1,5, 6, 30, 25, 150.)
а) Приведите пример задуманных чисел, для которых на доске будет записан набор
(2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90.)
б) Существует ли пример таких задуманных чисел, для которых на доске будет записан набор
(3, 5, 7, 9, 15, 21, 35, 45, 105, 315, 945)?
в) Приведите все примеры шести задуманных чисел, для которых на доске будет записан набор, наибольшее число в котором равно (82).
(ЕГЭ 2017, основная волна)
а) Очевидно, что в нашем задуманном наборе чисел должны быть числа (2, 3, 5). Для того, чтобы на доске появилось число (9), в нашем наборе либо должна быть (9), либо еще одна (3).
Рассмотрим набор (2, 3, 5, 9). Так как на доске должны быть записаны все попарные произведения, то на доске должно быть число (3cdot
9=27). Его там нет. Следовательно, этот набор невозможен.
Рассмотрим набор (2, 3, 3, 5). Проверкой убеждаемся, что он нам подходит.
Ответ: (2, 3, 3, 5).
б) Очевидно, что в задуманном наборе должны быть числа (3, 5, 7). Для того, чтобы на доске была написана (9), нужно, чтобы в нашем наборе была либо (9), либо еще одна (3).
Рассмотрим последнее написанное на доске число: (945=7cdot 3cdot
3cdot 3cdot 5). Заметим, что последнее записанное на доске число – это всегда произведение всех задуманных чисел.
Следовательно, либо этот набор точно содержит числа (3, 5, 7, 9), либо содержит (3, 3, 3, 5, 7).
Пусть в задуманном наборе как минимум есть числа (3, 3, 3, 5, 7). Тогда на доске должно быть записано число (3cdot 3cdot 3=27), которого там нет. Следовательно, набор с такими числами точно не может быть задуман.
Пусть в задуманном наборе как минимум есть числа (3, 5, 7, 9). Проверим, подходит ли он. Тогда на доске, например, должно быть число (7cdot 9=63). А его там нет. Следовательно, набор не подходит.
Ответ: нет.
в) Как уже говорилось в п. б), наибольшее число на доске – это произведение всех задуманных чисел. Следовательно, (82=2cdot 41) (разложили на простые множители) – произведение всех чисел.
Таким образом, либо у нас набор (82, 1, 1, 1, 1, 1), либо (2, 41, 1, 1, 1, 1).
Если бы в наборе было какое-то число, отличное от (1, 2, 41) и (82), то оно было бы делителем (82). А мы уже выяснили, что у (82) делители только (1, 2, 41, 82).
Ответ:
а) 2, 3, 3, 5
б) нет
в) 1, 1, 1, 1, 1, 82 или 1, 1, 1, 1, 2, 41
Задание
7
#3221
Уровень задания: Равен ЕГЭ
На доске написано (30) натуральных чисел. Какие-то из них красные, а какие-то — зеленые. Все красные числа кратны (8), а зеленые – кратны (3). Все красные числа отличаются друг от друга, все зеленые числа также отличаются друг от друга. Но между красными и зелеными числами могут быть одинаковые.
а) Может ли сумма всех чисел, записанных на доске, быть меньше (1395=3+6+dots+90), если на доске написаны только кратные (3) числа?
б) Может ли на доске быть написано только одно красное число, если сумма всех записанных на доске чисел равна (1066)?
в) Какое наименьшее количество красных чисел может быть написано на доске, если сумма всех чисел равна (1066)?
(ЕГЭ 2017, основная волна)
а) Заметим, что среди красных чисел также могут встречаться числа, кратные (3). Например, число (24) может встретиться в списке два раза: один раз как красное, второй – как зеленое.
Так как (1395=3+6+dots+90), и чисел (3, 6, dots, 90) – ровно тридцать штук, и они все кратны (3), то уберем из них, например, число (90), а вместо него возьмем число (24) (которое будет красным). Тогда мы получим 29 зеленых чисел: (3, 6, dots, 87) и одно красное (24) (кратное (3)), причем очевидно, что сумма всех чисел будет строго меньше (1395).
Ответ: да.
б) Упорядочим зеленые числа по возрастанию. Тогда наименьшее возможное значение первого числа – это (3), второго – это (6) и т.д. Наименьшее значение последнего, тридцатого числа, это (87). Сумма всех этих чисел равна (1305) – и это наименьшее возможное значение суммы 29-ти зеленых чисел. Следовательно, если сумма всех чисел равна (1066), то красное число должно быть отрицательным, что невозможно. Ответ: нет.
в) Докажем, что наименьшее возможное количество красных чисел – это 7.
Рассмотрим минимальное значение для суммы всех чисел для всех случаев, когда красных чисел от 2 до 6 (то, что на доске не может быть написано одно красное число, мы рассмотрели в пункте б)). Оформим это в таблице: [begin{array}{|c|c|c|}
hline text{зеленые} & text{красные}
& text{минимальная сумма}\
hline 28 text{чисел} & 2 text{числа}
& 1242\
3, 6, dots, 84 & 8, 16
& \
hline 27 text{чисел} & 3 text{числа}
& 1182\
3, 6, dots, 81 & 8, 16, 24
&\
hline 26 text{чисел} & 4 text{числа}
& 1133\
3, 6, dots, 78 & 8, 16, 24, 32
&\
hline 25 text{чисел} & 5 text{чисел}
& 1095\
3, 6, dots, 75 & 8, 16, 24, 32, 40
&\
hline 24 text{числа} & 6 text{чисел}
& 1068\
3, 6, dots, 72 & 8, 16, 24, 32, 40, 48
&\
hline end{array}] То есть мы брали самые маленькие зеленые числа и самые маленькие красные числа и общая сумма чисел получалась больше (1066). Следовательно, для любых наборов красных и зеленых чисел, где красных чисел от 2 до 6, общая сумма чисел будет больше, чем (1066).
Итак, мы имеем пример для 6 красных чисел, когда сумма всех чисел (зеленых и красных) равна (1068). Нужно добавить одно красное число и убрать одно зеленое так, чтобы общая сумма чисел стала равна (1066). Для этого нужно убрать одно зеленое число, которое больше добавленного красного числа на (2). Теперь смотрим: если мы добавим красное (56), то нам нужно убрать зеленое (58). Но такого числа среди зеленых нет.
Перебираем дальше: если добавить красное (64), то убрать нужно зеленое (66), которое как раз у нас имеется! Таким образом, мы построили пример, когда на доске написано 7 красных чисел: [begin{array}{|c|c|c|}
hline text{зеленые} & text{красные}
& text{сумма}\
hline 23 text{числа} & 7 text{чисел}
& 1066\
3, 6, dots ,63, 69, 72 & 8, 16, 24, 32, 40, 48, 64
& \
hline end{array}]
Ответ:
а) да
б) нет
в) 7
Как готовиться к сочинению за 2 дня до ЕГЭ? Четко и без воды
Как готовиться к сочинению за 2 дня до ЕГЭ? Четко и без воды