Комбинаторные задачки для разминки мозгов

[Trotil]

1) Найти сумму всех 10-значных чисел, получаемых при всевозможных перестановках цифр 4, 5, 5, 6, 6. 6, 7, 7, 7, 7.
2) Найти число различных подпоследовательностей длины (n-2) в слове (101010...10). n - четное.

@темы: Головоломки и занимательные задачи

Comments

[Dieter Zerium]

Trotil
я вечером попробую первую задачу решить. Идея кажется мне в следующем: мы фиксируем младший разряд и перебираем все возможные комбинации остальных разрядов (есть формула для перестановок с повторениями), и умножаем младший разряд на чилос получившихся перестановок... в общем, такой алгоритм

[Trotil]

Да пожалуйста. Главная сложность - разработать собственную схему решения, т.к. классические здесь не подходят. Возможно, твоя схема приведет к правильному ответу

[Dieter Zerium]

За вычисления не отвечаю, неплохо бы проверить)

\

[Minority]

я не математик.. я бы это запрограммировала..

[Trotil]

Dieter Zerium
Это правильный ответ, поздравляю, молодец!

Minority
Фишка в том, чтобы это математически решить... А путем программирования можно проверить вычисления, например )

[Dieter Zerium]

Trotil
Спасибо за задачу!

У меня кстати тоже была идея запрограммировать, но если бы я её реализовывал, то в лоб, т.е. было бы с точки зрения временных затрат неоптимально)

[Dieter Zerium]

Trotil
Спасибо за задачу!

У меня кстати тоже была идея запрограммировать, но если бы я её реализовывал, то в лоб, т.е. было бы с точки зрения временных затрат неоптимально)

[Minority]

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

[Amicus Plato]

Dieter Zerium

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

почему?
объясни, если не тяжело.

Trotil

Найти число различных подпоследовательностей длины (n-2) в слове (101010...10). n - четное.

то есть, нужно изъять из любых двух мест два символа. Так?

[Trotil]

то есть, нужно изъять из любых двух мест два символа. Так?

Вообще да.
Но если извлечь 1 и 2-ой, а в другом случае 3 и 4 - получится одна и таже подпоследовательность, а это нужно учитывать.

[Amicus Plato]

Trotil )))))
ага)
это то, на чем я прокалываюсь каждый раз))
Все изъятия 10 или 01 считаем один раз)

[Trotil]

объясни, если не тяжело.

Потому что мы таким образом получаем число комбинаций, оканчивающихся на 4, число комбинаций, оканчивающихся на 5, число комбинаций, оканчивающихся на 6 и число комбинаций, оканчивающихся на 7.
Сумма эта (S) - сумма последних разрядов всех комбинаций.

А дальше логически обнаруживаем тот факт, что эта сумма не зависит от того, какой разряд мы фиксируем. Поэтому сумма в соответствующем разряде будет S*10^(i-1), i - номер разряда.

[Amicus Plato]

Trotil
блин!
Какой же я тугодум ((((
Дошло наконец.

[Dieter Zerium]

Amicus Plato
Собственно, Trotil уже объяснил, я попытаюсь немного другими словами:
Главная идея заключается в том ,что мы суммируем все получившиеся 10-значные числа не прибавляя одно число к уже сосчитнной сумме других чисел (т.е. почисленно, как обычно), а поразрядно, т.е. мы складываем их в столбик Сначала единицы, потом десятки и т.д. (естественно, сдвигая поразрядные суммы, в общем, как в 5ом классе). Но так как мы рссматрваем перестановки, то эти поразрядные суммы будут одинаковыми, так как если расмотреть все числа, то в каждом разряде каждая цифра будет встречаться одинаковое число раз.
И потом суммируем эти одинаковые поразрядные суммы, со сдвигом, что видно из последней формулы 10^(i-1) - это и есть сдвиг

[Amicus Plato]

Dieter Zerium
ага) спасибо!))
Я поняла (не прошло и года )

[Dieter Zerium]

Amicus Plato

Какой же я тугодум ((((

это я неясно написал...

[Amicus Plato]

Dieter Zerium

это я неясно написал...

не утешай меня )))))
я бы могла бы и сама бы додуматься ведь...
А вообще — класс! Здорово получилось!

[Dieter Zerium]

Amicus Plato

не утешай меня )))))

гы)

А вообще — класс! Здорово получилось!

Самое забавное, что ничего нового не было придумано, складыать в столбик умели ещё, наверное, 1000 лет назад

[Amicus Plato]

Dieter Zerium

Самое забавное, что ничего нового не было придумано, складыать в столбик умели ещё, наверное, 1000 лет назад

Что ты! Ты заблуждаешься!
Я не помню, где я про это читала: надо поискать, но складывать в столбик научились не так давно! А до этого писали целые трактаты о науке сложения больших чисел и страшно мучились...
...
Гм... Хотя, может это как раз 1000 лет назад и было?...
Это я когда про историю ВТ писала что-то такое находила. Надо бы поискать. Интересно ведь!

[Dieter Zerium]

Amicus Plato
Я кстати долго думал, прежде чем про 1000 лет написать) Да, сейчас поищем, стало интересно))

[Amicus Plato]

Со второй задачей что-то никто не хочет связываться)))

10101010101010...10

1) Если мы из любого места выдернем 10 или 01, получим одну и ту же последовательность:
10101010101010...10, только на два символа короче начальной. n1=1 (в том смысле, что одна подпоследовательность)
2) Если из разных мест изымать две единицы, каждый раз будет получаться разная последовательность. Всего таких способов: n2=n/2*(n/2-1)
3) То же рассуждение для двух нулей: n3=n/2*(n/2-1)
Теперь осталось разобраться с изъятием одного нуля и одной единицы. Возможны варианты:
4) Изымается первая единица. Для нее подходят все нули, кроме второго (т.к. этот случай уже учтен в п. 1)). n4=n/2-1
5) Изымается последний ноль. К нему в пару подходят все единицы, кроме предпоследней. n5=n/2-1
6) Из середины берем 1 и 0. Они не могут быть соседними. Для каждого выбранного элемента нельзя брать ни правого ни левого соседа. n6=(n/2-1)(n/2-2)
n=n1+n2+n3+n4+n5+n6=1+n(n/2-1)+2(n/2-1)+(n/2-1)(n/2-2)=1+(n/2-1)(n+2+n/2-2)=1+3n/2(n/2-1)

Ну. Думаю, здесь миллиона два ошибок. )))

[Trotil]

Нет, не совпадает с ответом.

Ко второй задаче у меня есть ответ и авторское решение, которое я, два раза прочитав, его не понял. Он решает перебором всех вариантов.
Я попробовал решить другим методом.

Я подумаю на досуге над твоим решением )

[Amicus Plato]

Trotil
в бОльшую или в меньшую сторону моё не совпадает с авторским?
Я на самом деле с наскока писала. Надо бы посмотреть, всё ли там и в самом деле так гладко.

[Amicus Plato]

Trotil
Перечитала свое решение. Кажется, можно еще укоротить. Сейчас напишу.

[Amicus Plato]

Пункты 2) 3) и 6) можно объединить вместе.

1') Если мы из любого места выдернем 10 или 01, получим одну и ту же последовательность:
10101010101010...10, только на два символа короче начальной. n1=1 (в том смысле, что одна подпоследовательность)

2') Изымается первая единица. Для нее подходят все нули элементы, кроме второго нуля (т.к. этот случай уже учтен в п. 1)). n2=n-2
3') Изымается последний ноль. К нему в пару подходят все единицы элементы, кроме предпоследней единицы. n3=n-2
4') Из середины берем два любых элемента. Они не могут быть соседними. Для каждого выбранного элемента нельзя брать ни правого ни левого соседа. n4=(n-2)(n-4)
n-2 — обозначает, что элемент из серединки.
n-4 — элемент из серединки и не правый и не левый сосед первого.

n=n1+n2+n3+n4=1+(n-2)+(n-2)+(n-2)(n-4)= 2n-3+n²-6n+8 = n² - 4n + 5

Опять наверное не совсем верно, но уже логичнее.

[Trotil]

в бОльшую или в меньшую сторону моё не совпадает с авторским?

Просто выкинуть два символа из n: C(n,2) = n(n-1)/2

Понятно, что наше число меньше.

А у тебя по асимптотике главный член 3/4 n^2. Число растет быстрей.

[Amicus Plato]

Trotil
ага)
значит мое новое решение еще надо пополам поделить в некоторых частях!
Я как всегда не учла.
Сейчас.

[Amicus Plato]

В пункте четыре каждая комбинация учитывается дважды.
отсюда:

n= 2n-3+(n-2)(n-4)/2

[Trotil]

n= 2n-3+(n-2)(n-4)/2

Уже ближе к правильному ответу.

Правильный ответ (n-1)(n-2)/2 + 1 = (n^2 - 3n +4) / 2

Ориентируйся на него )

[Amicus Plato]

Trotil
Та-ак.
1 — это моя единица из пункта первого))) Это точно.
А все три остальных случая, видимо, тоже можно объединить.
Только мне кажется, у меня "прозрачнее"...
Посмотрю еще завтра.