На канале у Савватеева наткнулся на нифига нетривиальную задачку.
Кто знает — не выкладывайте сразу решение.
Кому интересно — ЮТуб в помощь, он там объясняет решение.
Итак, берем СКОЛЬКО УГОДНО ДЛИННОЕ число.
Например
258547546789864313570008647790754467
Пусть шаг иттерации — это расстановка в каких угодно местах знаков «+» внутри этого числа и собственно сложение.
То есть в нашем примере это будет, например
25+854+7+54678+98+643+13+57000+8+647+790754+467
Ну и подсчет результата. Уж не буду это в этом примере делать. Получаем в результате сложения следующее огромное число. Следущая иттерация — то де самое делаем уже с результатом.
Надо доказать, что для любого сколь угодно длинного числа можно свести его к однозначному (цифре) максимум за 4 иттерации
То, что сколь угодно длинное и всего 4 шага — наиболее крышесносно в этой задаче
Давайте все ж пример приведу
Пусть число 545777
Шаг 1:
54+5+77+7 = 143
Шаг 2:
1+4+3 = 8
Ну вот, за 2 шага свели к цифре
UPD: небольшое пояснение. Не при любом расположении плюсиков будет за 4 шага. Но суть задачи именно в придумывании алгоритма расставления плюсиков.
Здравствуйте, Homunculus, Вы писали:
H>На канале у Савватеева наткнулся на нифига нетривиальную задачку. H>Кто знает — не выкладывайте сразу решение. H>Кому интересно — ЮТуб в помощь, он там объясняет решение.
H>Итак, берем СКОЛЬКО УГОДНО ДЛИННОЕ число. H>Например
H>258547546789864313570008647790754467
H>Пусть шаг иттерации — это расстановка в каких угодно местах знаков «+» внутри этого числа и собственно сложение. H>То есть в нашем примере это будет, например
H>25+854+7+54678+98+643+13+57000+8+647+790754+467
H>Ну и подсчет результата. Уж не буду это в этом примере делать. Получаем в результате сложения следующее огромное число. Следущая иттерация — то де самое делаем уже с результатом.
H>Надо доказать, что для любого сколь угодно длинного числа можно свести его к однозначному (цифре) максимум за 4 иттерации
H>То, что сколь угодно длинное и всего 4 шага — наиболее крышесносно в этой задаче
H>Давайте все ж пример приведу
H>Пусть число 545777
H>Шаг 1: H>54+5+77+7 = 143 H>Шаг 2: H>1+4+3 = 8
H>Ну вот, за 2 шага свели к цифре
H>UPD: небольшое пояснение. Не при любом расположении плюсиков будет за 4 шага. Но суть задачи именно в придумывании алгоритма расставления плюсиков.
Так должно быть и в "обратную" это верно, а оно вроде не верно.
Программа – это мысли спрессованные в код
Re[2]: Любое сколь угодно огромное число сводимо к однозначному
Здравствуйте, Homunculus, Вы писали:
H>Здравствуйте, Qulac, Вы писали:
Q>>Так должно быть и в "обратную" это верно, а оно вроде не верно.
H>Что «не верно»? Ты про нолики забыл? Любую цифру с помощью ноликов можно развернуть в любое сколь угодно длинное число.
Ну тогда ни чего "крышесносного" в этом факте нету. Нужно доказать просто.
Программа – это мысли спрессованные в код
Re[4]: Любое сколь угодно огромное число сводимо к однозначному
Здравствуйте, Homunculus, Вы писали:
H>Кому интересно — ЮТуб в помощь, он там объясняет решение.
Возможно, нахождение соответствующего ролика будет очевидно тому, кто регулярно смотрит канал, но мне на запрос "савватеев число сводимо" выдаются в первую очередь лекции про число Пи, календари и прочее. Просматривать все подряд совершенно неинтересно.
H>Пусть шаг иттерации — это расстановка в каких угодно местах знаков «+» внутри этого числа и собственно сложение.
Если сложение выполняется не по модулю, и результат не ограничен, то очевидно, что для получения наименьшего результата следует складывать отдельные цифры.
H>Надо доказать, что для любого сколь угодно длинного числа можно свести его к однозначному (цифре) максимум за 4 иттерации
При озвученных условиях это чрезвычайно сомнительно, поскольку сумма цифр числа, состоящего только из девяток, монотонно растет с ростом самого числа. Если за конечное число шагов получено однозначное число — всегда можно выбрать бОльшее исходное число, и однозначного результата уже не получится. Вы явно что-то напутали в условиях.
Re[2]: Любое сколь угодно огромное число сводимо к однозначному
ЕМ>Если сложение выполняется не по модулю, и результат не ограничен, то очевидно, что для получения наименьшего результата следует складывать отдельные цифры.
Не очевидно.
Это верно, если есть только одна итерация.
Например, если разрешено сделать две итерации, то складывая только цифры из числа 432568 получится 4+3+2+5+6+8 = 28, а из него получим 2 + 8 = 10.
Хотя если складывать как 432+568 = 1000, и 1+0+0+0 = 1, то получим меньший результат.
Re[2]: Любое сколь угодно огромное число сводимо к однозначному
ЕМ>Достаточно показать, что для неудачных лучшим способом будет сложение отдельных цифр.
Ну попробуй показать
ЕМ>Нет никакого смысла рассматривать подобные удачные варианты.
Есть смысл доказать, что для любого числа найдётся удачный вариант. В этом задача.
Re[5]: Любое сколь угодно огромное число сводимо к однозначному
Здравствуйте, Homunculus, Вы писали:
H>Один из топовых комментов глянь, там понятно и четко все чувак разложил
Я его читал — там рассуждения на уровне интуиции. Понятно, что исходное число можно разбить на какое-то количество сумм вида 10...xxxx, но я не уловил, из чего следует, что таких сумм всегда будет достаточно мало для успешного завершения за три дополнительных шага.
Re[2]: Любое сколь угодно огромное число сводимо к однозначному
Здравствуйте, Евгений Музыченко, Вы писали:
ЕМ>При озвученных условиях это чрезвычайно сомнительно, поскольку сумма цифр числа, состоящего только из девяток, монотонно растет с ростом самого числа. Если за конечное число шагов получено однозначное число — всегда можно выбрать бОльшее исходное число, и однозначного результата уже не получится. Вы явно что-то напутали в условиях.
Здравствуйте, Homunculus, Вы писали:
H>Надо доказать, что для любого сколь угодно длинного числа можно свести его к однозначному (цифре) максимум за 4 иттерации H>То, что сколь угодно длинное и всего 4 шага — наиболее крышесносно в этой задаче
А для шестнадцатеричной системы будет 7 итераций?
И каждый день — без права на ошибку...
Re[2]: Любое сколь угодно огромное число сводимо к однозначному
Здравствуйте, Homunculus, Вы писали:
BFE>>А для шестнадцатеричной системы будет 7 итераций? H>Пополам минус один? Хммм, не знай, так сразу не могу сказать.
Я тоже не знаю, но откуда ещё может взяться 4?
Впрочем, нам, программистам, надо начинать с привычного.
Я вот вчера немного размышлял на двоичной системой. Вроде бы любое число сводится к 1 за две итерации.
10101 -> 10+1+0+1 -> 100 -> 1+00 -> 1
1010111 -> 10+10+11+1 -> 1000 -> 1+000 -> 1
101010101 -> 10+10+10+1+0+1 -> 1000 -> 1+000 -> 1
111010101 -> 1+1+10+10+1+0+1 -> 1000 -> 1+000 -> 1
1110101011 -> 111010+101+1 -> 100000 -> 1+00000 -> 1
Т.е. на первом шаге нам надо разбить битовый поток так, чтобы сумма была равна степени двойки.
И каждый день — без права на ошибку...
Re[4]: Любое сколь угодно огромное число сводимо к однозначному
Здравствуйте, B0FEE664, Вы писали:
BFE>>>А для шестнадцатеричной системы будет 7 итераций? H>>Пополам минус один? Хммм, не знай, так сразу не могу сказать.
Четыре же и будет.
BFE>Я тоже не знаю, но откуда ещё может взяться 4?
Это берется их схемы построений сумм.
Строится разбиение, дающее число вида 1000...00XYZT (т.е. единица в начале и максимум четыре отличных от нуля цифры в конце).
Число сводится к двухзначному (4 цифры + 1)
Двухзначное число сводится к числу вида 1X, где X — строго меньше максимального разряда (т.е. все число <=18 для десятичной системы и <=1E для шеснадцатиричной)
Это число сходится в один прием к однозначному
Есть некоторые условия, чтобы все сведения работали. Но с ростом разрядности системы счисления они все сохраняются. Так что в шеснадцатиричной системе тоже сводимость за 4 шага.
BFE>Впрочем, нам, программистам, надо начинать с привычного. BFE>Я вот вчера немного размышлял на двоичной системой. Вроде бы любое число сводится к 1 за две итерации.
А вот это уже получается другая задача (тоже интересная). Т.е. здесь схема сведения совершенно отлична от исходной.
Re[4]: Любое сколь угодно огромное число сводимо к однозначному
Здравствуйте, alpha21264, Вы писали:
A>Я бы сказал, что они вообще ничего не объяснили.
Да ладно, нормальная схема доказательства . Хотя, конечно, зависит от того, какая область математики вам ближе. Мне ближе всего алгебра (символьные вычисления и все такое), поэтому могу рассказать по шагам.
Сначала пара наблюдений. Однозначные числа сводить никуда не нужно. Числа до 18 включительно сводятся максимум за одну итерацию (это либо однозначное, либо двухзначное и в один шаг даст максимум 9). Любое двухзначное число сводится не более, чем за две итерации. На первой итерации получается чило до 18 (включительно), далее действует предыдущее наблюдение. Далее, для других чисел
Лемма 1 (о небольших числах).
Число, в десятичной записи которого не более 11 ненулевых цифр, сводится к однозначному числу максимум за три итерации.
Доказательство. Суммируем все цифры. Получаем число до 99. Которое сводится максимум за две итерации по предыдущим наблюдениям. Лемма доказана.
Дальше. Будем строить последовательность разбиений исходного числа P(0), ... P(n):
P(i) = {a(i, 1), a(i, 2), ..., a(i, l(i))}, где
a(i,1)a(i,2)...a(i,l(i))=N
каждое P(i) — последовательность целых чисел, при записи подряд дающих исходное число N. l(i) — количество элементов в i-м разбиении.
Мы строим первое разбиение P(0) так, чтобы для любого элемента a(0, i) выполнялось одно из следующих условий:
a(0, i) = 0
1000 ≤ a(0, i) ≤ 9999
a(0, i) < 10 и i ≥ l(0)-2
Т.е. мы разбиваем на группы так, чтобы все первые были по четыре цифры либо нули. И только последние несколько ненулевых цифр (не более трех) могут быть взяты по-отдельности. Разбиение так и строится: Берем 4 цифры (если их уже меньше, по лемме о небольших числах досаточно трех шагов).
Если следующая цифра 0, берем его отдельно, повторяем с шага 2.
Если осталось меньше 3-х цифр, берем их по одной (это даст максимум три слагаемых).
Иначе есть 4 цифры и первая не ноль. Берем это в качестве очередного слагаемого, продолжаем с шага 2.
Далее, каждое P(i+1) строится из P(i) заменой одного четырехзначного числа на четыре.
Пусть k = первое, при котором 1000 ≤ a(i, k)
Тогда
a(i, k) = 1000*A + 100*B + 10*C + D
И мы строим
P(i+1):
a(i+1, j) = a(i, j) при j < k,
a(i+1, k) = A
a(i+1, k+1) = B
a(i+1, k+2) = C
a(i+1, k+3) = D
a(i+1, j) = a(i, j — 3) при j > k+3
Такое построение сохраняет свойство того, что P-разбиение исходного числа (порядок цифр не меняется). Более того, l(i+1) = l(i) + 3. И n (количество разбиений) — это количество четырехзначных чисел в P(0) (мы дальше разбивать не сможем).
Пусть S(i) — сумма чисел в разбиении P(i):
S(i) = sum(j ∈ [1,l(i)], a(i, j))
Тогда справедлива лемма 2.
Лемма 2
Последовательность S(i) — строго убывающая. Кроме того, S(i+1) > S(i) — 10000
Доказательство. По построению P(i+1), мы имеем
S(i+1) = S(i) — a(i, k) + a(i+1, k) + a(i+1, k+1) + a(i+1, k+2) + a(i+1, k+3).
(k — это то число, которые мы разбивали на шаге алгоритма). По определению P(i+1), у него почти все слагаемые те же, что и в P(i). Разница — записана. Из формулы (в предыдущих же обозначениях) мы имеем
S(i+1) = S(i) — 999 * A — 99 * B — 9 * C
В силу выбора a(i, k) у нас A > 0, остальные числа неотрицательные. Т.е. S(i+1) < S(i). По рекуррентному соотношению S(i+1) >= S(i) — a(i, k). В силу выбора a(i, k) ≤ 9999 имеем S(i+1) > S(i) — 10000.
Лемма 3
S(0) ≥ 1000*n
Это следует из построения. Если мы сделали n шагов, у нас было n четырехзначных чисел в первом разбиении (первая альтернатива, a(0, i) ≥ 1000).
Лемма 4
S(n) ≤ 9*4*n + 9*3
Тоже следует из построения. Каждое ненулевое начальное число (коих n штук) дает максимум 4 девятки. Еще остались максимум три девятки в конце (последнее ограничение на a(0, i)). Остальные числа — нули.
Пусть R(i) — количество цифр в записи S(i).
R(i) = floor(log10(S(i)))+1
Обе функции floor и log10 — неубывающие, S(i) — убывающая. Т.е. и R(i) — неубывающая. R(i+1) ≤ R(i).
Лемма 5
Сумма чисел в последнем разбиении имеет меньше разрядов, чем в первом. Т.е. R(n) < R(0).
Для этого покажем, что log10(S(0)) — log10(S(n)) > 1. Тогда (строго между) этими числами есть целое число, которое будет разделять их ceil, и следовательно R(0) и R(n) тоже будут разными. Доказательство (знак вопроса — то, что доказываем):
log10(S(0)) — log10(S(n)) (?)> 1, экспоненциируем (по основанию 10)
S(0)/S(n) (?)> 10
S(0) ≥ 1000*n (лемма 3)
S(n) ≤ 9*4*n + 9*3 < 9*4*n + 9*4 = 36*(n+1), (лемма 4) инвертируем
1/S(n) > 1 / (36*(n+1)), умножаем
S(0)/S(n) > 1000*n/(36*(n+1)) (?)>10
1000*n (?)> 360*(n+1)
1000*n (?)> 360*n + 360
640*n (?)> 360
Последнее верно при всех натуральных n. Т.е .верно и исходное неравенство. Т.е. R(n) < R(0).
Пусть p первое такое число, что R(p+1) < R(p), тогда мы имеем
Лемма 6
S(p) = exp10(R(p+1)) + b для некоторого b ∈ [0, 9999].
Доказательство:
R(p) = floor(log10(S(p))) + 1
R(p+1) ≤ R(p) — 1 = floor(log10(S(p))) в силу выбора p
exp10(R(p+1)) ≤ exp10(floor(log10(S(p)))) ≤ exp10(log10(S(p))) = S(p)
В то же время
R(p+1)=floor(log10(S(p+1)))+1 ≥ log10(S(p+1)) (в силу свойств floor)
exp10(R(p+1)) ≥ exp10(log10(S(p+1))) = S(p+1)
Объединяя с предыдущим,
S(p+1)≤exp10(R(p+1))≤S(p)
В силу леммы 2
S(p+1) > S(p) — 10000, подставляя в предыдущее
S(p) ≥ exp10(R(p+1)) ≥ S(p+1) > S(p) — 10000 или
exp10(R(p+1)) + 10000 > S(p) ≥ exp10(R(p+1))
Так что S(p) представимо в искомом виде. И лемма доказано.
Теперь можно перейти к задаче. Вот это рассмотренное разбиение P(p) и будет нашим разбиением для первого шага. Оно даст либо не более чем пятизначное число (при маленьких R(p)). Либо число вида 1000..000ABCD (для больших R(p)). В силу леммы 1 (о небольших числах), эта S(p) сводима за три шага к однозначному числу. Т.е. исходное число сводимо не более чем за четыре шага.
Что и требовалось доказать. В общем, ничего сложного. Но объяснение на пальцах проще
