Номер 552, страница 116, часть 2 - гдз по математике 5 класс учебник Петерсон, Дорофеев

C 552 Записаны все числа подряд от 1 до 40. Не изменяя порядка записи, вычеркни 60 цифр так, чтобы оставшиеся 11 цифр выражали:

а) наименьшее число;

б) наибольшее число.

Сначала выпишем последовательность цифр, которая получается при записи всех чисел от 1 до 40 подряд.

Числа от 1 до 9: 123456789 (9 цифр).
Числа от 10 до 39: это 30 двузначных чисел, всего $30 \times 2 = 60$ цифр.
Число 40: 2 цифры.
Общее количество цифр в последовательности: $9 + 60 + 2 = 71$ цифра.

Полная последовательность цифр (назовем ее S):
S = 12345678910111213141516171819202122232425262728293031323334353637383940.

По условию, нужно вычеркнуть 60 цифр, чтобы осталось 11. Проверка: $71 - 60 = 11$. Все верно.
Для нахождения наименьшего и наибольшего числа будем использовать жадный алгоритм. Мы будем формировать искомое 11-значное число по одной цифре слева направо.

а) наименьшее число

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

1-я цифра: Мы ищем 11-значное число, значит, после первой цифры должно остаться еще 10. Всего в последовательности 71 цифра. Следовательно, первую цифру мы можем выбрать из первых $71 - 10 = 61$ цифр исходной последовательности. Первая цифра не может быть нулем. Наименьшая ненулевая цифра в начальном отрезке S — это 1. Чтобы оставить больше вариантов для последующих (потенциально меньших) цифр, мы должны выбрать самую первую 1. Это самая первая цифра в последовательности S.
Выбираем 1.

2-я цифра: Теперь нам нужно выбрать еще 10 цифр. После нашей 1 осталась последовательность, начинающаяся с 234... В этой последовательности 70 цифр. Вторую цифру нужно выбрать так, чтобы после нее можно было выбрать еще 9. Значит, ищем в первых $70 - 9 = 61$ цифрах оставшейся последовательности. Наименьшая цифра здесь — 0 (из числа 10).
Выбираем 0. Получаем 10.

3-я цифра: После 0 из числа 10 начинается последовательность 111213... Нам нужно выбрать еще 9 цифр. Ищем наименьшую цифру в доступном диапазоне. Это будет 0 из числа 20.
Выбираем 0. Получаем 100.

4-я цифра: Аналогично, следующая наименьшая цифра, которую мы можем выбрать — это 0 из числа 30.
Выбираем 0. Получаем 1000.

5-я цифра: После 0 из числа 30 последовательность продолжается с числа 31. Наименьшая цифра, которую можно выбрать — это 1 из числа 31.
Выбираем 1. Получаем 10001.

6-я цифра: После 1 из 31 идет последовательность, начинающаяся с числа 32. Наименьшая доступная цифра — 2 из числа 32.
Выбираем 2. Получаем 100012.

7-я, 8-я, 9-я, 10-я цифры: Продолжая этот процесс, мы будем последовательно выбирать самые маленькие из доступных цифр. Это будут цифры 3 (из 32), 3 (из 33), 3 (из 33), 3 (из 34).
Получаем 1000123333.

11-я цифра: Для последней цифры мы ищем наименьшую в оставшейся части последовательности. После 3 из числа 34 остается последовательность цифр, начинающаяся с 4 (из 34) и заканчивающаяся на 40. В этой части есть цифра 0 (из числа 40).
Выбираем 0.

Итоговое наименьшее число: 10001233330.
Выбранные цифры и их источники: 1 (из 1), 0 (из 10), 0 (из 20), 0 (из 30), 1 (из 31), 2 (из 32), 3 (из 32), 3 (из 33), 3 (из 33), 3 (из 34), 0 (из 40).
Ответ: 10001233330

б) наибольшее число

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

1-я цифра: Ищем самую большую цифру в первых $71-10=61$ цифрах последовательности S. Самая большая цифра — 9. Она встречается в числах 9, 19, 29. Чтобы оставить как можно больше вариантов для следующих цифр, нужно выбирать самую первую из них. Это 9 из числа 9.
Выбираем 9.

2-я цифра: После 9 из числа 9 последовательность продолжается с 10. Ищем наибольшую цифру в доступном диапазоне. Это будет 9 из числа 19.
Выбираем 9. Получаем 99.

3-я цифра: Аналогично, следующая по порядку наибольшая доступная цифра — это 9 из числа 29.
Выбираем 9. Получаем 999.

4-я цифра: После 9 из числа 29 последовательность продолжается с 30. Ищем наибольшую цифру в доступном диапазоне. Это 9 из числа 39. Но нужно проверить, хватит ли нам оставшихся цифр. После 9 из 39 (позиция 69) остаются только 2 цифры (40). А нам нужно выбрать еще $11-4=7$ цифр. Значит, 9 из 39 брать нельзя. Самая большая цифра, которую мы можем выбрать, чтобы после нее осталось не менее 7 цифр, — это 6 из числа 36.
Выбираем 6. Получаем 9996.

5-я цифра: После 6 из 36 ищем следующую наибольшую цифру. Это 7 из числа 37. После нее остается достаточно цифр.
Выбираем 7. Получаем 99967.

Оставшиеся 6 цифр: После выбора 7 из числа 37 до конца исходной последовательности S остается 6 цифр: 383940. А нам как раз нужно выбрать еще $11-5=6$ цифр. Поэтому мы должны взять все оставшиеся цифры без вычеркивания. Это цифры 3, 8, 3, 9, 4, 0.

Итоговое наибольшее число: 99967383940.
Выбранные цифры и их источники: 9 (из 9), 9 (из 19), 9 (из 29), 6 (из 36), 7 (из 37), 3 (из 38), 8 (из 38), 3 (из 39), 9 (из 39), 4 (из 40), 0 (из 40).
Ответ: 99967383940