М.Двач / Математика

1,5 Мб, 2000x2000
Усложнение простой олимпиадной задачи. # OP 21 фев 2020, 20:06 65315 В конец треда | Веб

Сап. Кароче, помогал племяннику решать олимпиадные задачи.

Была там задача, вот краткое условие: "У чисел от 1 до 1000, у каждого посчитали сумму цифр, и расставили по возрастанию (если у чисел одинаковая сумма цифр, то выбирается большее изначально, 19, 91, 46, то будет по порядку 19, 46, 91). На каком месте стоит число 997? "
Изичная задача, у 997 сумма 25, и чисел с большей суммой цифр всего 5, 998, 989, 899, и 999. Значит 997 стоит на 1000 - 5 ом месте, то есть на 995.

Окей, но сегодня я подумал, что это очень годная задача. Если взять другое число, которое нельзя так просто найти, допустим 717 (чисто на рандом взял), там уже не получится просто с конца или с начала. Ну и как его найти? Алсо, скинул другу методисту,
но ему нужно решение. А оно мне непонятно, вообще.

Собсна, если это возможно решить, то напишите решение, или накидайте статьи по этой фигне. Если думаете что это нерешаемо, то напишите почему? Доказательство того что задача нерешаемая, тоже является решением.

Ответы326

2 22 фев 2020, 00:56 2 65325

Всегда считал, что задачи где фигурируют суммы цифр каких то чисел это какой-то астрологический магический нумерологический рак. Позиционные системы счисления это чисто человеческая отсебятина для удобства записи количеств и в природе аналогов хоть сколько нибудь этой природе полезных они не имеют. Это как искать в Войне и Мире скрытые стихотворения перебирая слова рандомно или в какой-то закономерности.

Ответы334

3 22 фев 2020, 00:58 3 65326

>>65315 (OP)
У 717 сумма 15, а всего у нас сумм от 1 до 27
Тогда нужно посчитать сколько у нас представлений каждого числа от 16 до 27 (от 1 до 14) в виде суммы 3 натуральных чисел <10 (пусть f(n)=(n+1)*(n+2)/2, тогда это будет f(n)-g(n) если нигде не ошибся)
Тогда
1: 3 + 1
2: 6
...
9: 55
10: 66 - 3
11: 78 - 9
...
14: 120 - (15+12+9+6+3)
это всё суммируется, после чего мы находим и прибавляем порядковый номер 717 относительно чисел с суммой 15. Этот же алгоритм годится и для любых других чисел из интервала [1; 1000

Хотя я бы посчитал на пеке и не парился)
извиняюсь что не подробно, просто я уже спать собирался

Ответы337

4 22 фев 2020, 10:24 4 65334

>>65325
Исторически в позиционных системах очень много смысла, потому что они удобны для записи, чтения и счёта. Математически - ну, p-адические числа довольно удобно определять похожим способом, так что, глядишь, и не зря придумали.

5 22 фев 2020, 15:15 5 65337

>>65326
Спасибо, еще вопрос, можно ли сделать что либо такое же, но если сумма не складывается, а перемножается?

Ответы348

6 22 фев 2020, 20:26 6 65342

И да, почему f(n) именно такое?

Ответы348

7 23 фев 2020, 00:00 7 65348

>>65337
Можно, для этого надо найти сколькими способами можно представить число n как произведение 3 натуральных чисел <10 (учитывая порядок)

>>65342
Сколько у нас способов представить число n как сумму 2 натуральных чисел (учитывая порядок)? Вот и иди от этого.
или гугли представление чисел в виде слагаемых через многочлены

Ответы351

8 23 фев 2020, 01:30 8 65351

>>65348
Прости, может я слишком тупой, но как кол-во вариантов представления числа суммой двух связано с самой задачей?

Ответы362

9 23 фев 2020, 12:07 9 65362

>>65351
Первое.

4=0+4=1+3=2+2=3+1=4+0
5=1+s(4)=1+0+4=1+1+3=1+2+2=1+3+1=1+4+0
5=s(4)+1=0+4+1=1+3+1=2+2+1=3+1+1=4+0+1
...
S(5) = (5+s(0)) + (4+s(1)) + (3+s(2)) +...+ (0+s(5)) = f(5)

s(n) - представление суммой двух
S(n) - представление суммой 3-х

Но не исключено что и я нигде не ошибся, лень перепроверять.

Ответы371

10 23 фев 2020, 19:44 10 65371

>>65362
Я думаю ты обсчитался. Смотри, комплюхтер считает, что для того же 5 кол-во вариантов - 21.
5--1
14--2
23--3
32--4
41--5
50--6
104--7
113--8
122--9
131--10
140--11
203--12
212--13
221--14
230--15
302--16
311--17
320--18
401--19
410--20
500--21
Вот, вроде ничего не пропустил.
S(5)=(5)+(4+2)+(3+3)+(2+4)+(1+5)+(5)=34. Если я сам нигде не обсчитался, и правильно понял про что ты говоришь.
И все же, что такое g(n). Все твои ответы совпадают с комплюхтерными, так что если сможешь обьяснить, то я буду очень благодарен.

Ответы380

11 23 фев 2020, 22:21 11 65380

>>65371
g(n) - это количество представлений числа n в виде суммы 3 слагаемых, где хотя бы одно слагаемое > 9.
15 = 15 + a + b = a + 15 + b = a + b + 15 (отсюда множитель 3)
15 = 14 + a + b = a + 14 + b = a + b + 14 итд. до 10
Тогда g(15) = 3 (1 + s(0)) + 3 (1 + s(1)) +...+ 3 (1 + s(5))

В общем виде g(n) = 3 (n - 9) * (n - 8) / 2 для n > 9
и g(n) = 0 для n < 10

>>Я думаю ты обсчитался
Скорее опечатался. Надо было так:
S(5) = (1+s(0)) + (1+s(1)) + (1+s(2)) +...+ (1+s(5)) = f(5)
Т.е. кол-во способов представить 5 одним слагаемым + s(0)
кол-во способов представить 4 одним слагаемым + s(1)
Итд.

Ответы441507

12 24 фев 2020, 22:12 12 65441

>>65380
Так, я хотя бы понял что значит f(n) и g(n).
Но можешь ли ты обьяснить как ты получаешь эти значения?
C S() и s() вообще ничего не понял.

Заранее спасибо, что хотя бы пытаешься обьяснить

Ответы442

13 24 фев 2020, 23:43 13 65442

>>65441
Нет, ничего я "обьяснять" больше не буду. Тут и так разжеванно так, что даже ежу станет понятно. Ты либо знаешь
- комбинаторику
- сумму арифметической прогрессии
либо нет. Если последнее, возьми учебник и повтори. Всё.

14 25 фев 2020, 17:28 14 65507

>>65380

Анон, последний вопрос.
Все понял уже, но с чего 15 сначала =15+а+б и перестановки этого, а потом становится =14+а+б?

И почему кол-во сумма способов представить от n до 1 одним слагаемым и кол-во способов представить от n до 1 двумя слагаемым равняется кол-ву вариантов представления n тремя числами?

Ответы512

15 25 фев 2020, 22:10 15 65512

>>65507
Неа, думай сам, привыкай.

a и b из 15 + a + b и a и b из 14 + a + b это совершенно разные пары чисел. Запись была с "ошибкой" намеренно мне было лень их заменять, думал ты догадаешься.

Обновить тред
« /math/В начало тредаВеб-версияНастройки/a//b//mu//s//vg/Все доски

Скачать тред только с превьюс превью и прикрепленными файлами

Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах.Подробнее

Пользуетесь скринридером — пишите, что можно улучшить.
Host-Food.ru — надёжный хостинг от 12 руб/мес | Free DNS
Зеркала М.Двача: m2ch.hk, m2ch.lib, m2chfapiswfw2wcakptqp4o6ltgchvjuxfab7urxlduraomtlnhw5xad.onion