gegmopo4: (Default)
[personal profile] gegmopo4

Задачка для дошкольников: Разделить семь яблок на три разные кучки.

Задача для продвинутых школьников: Найти все m и n такие, что n можно единственным (с точностью до перестановки) способом представить в виде суммы m разных натуральных чисел.

Задача для ещё кого-нибудь: Сколькими (с точностью до перестановки) способами можно представить n в виде суммы m разных натуральных чисел?

Date: 2012-09-14 09:18 pm (UTC)
From: [identity profile] http://users.livejournal.com/_winnie/
Я тут обнаружил читерский способ находить формулу для комбинаторных задачек: считаем для первых десяти элементов, копируем ряд на http://oeis.org/

Date: 2012-09-14 10:04 pm (UTC)
From: [identity profile] slobin.livejournal.com
Задачка: найти интересных пар рядов, совпадающих в первых десяти членах, а потом различающихся. :-)
(прошу прощения за кривую формулировку -- я простыл, голова не варит)

... throw 22 ...

Date: 2012-09-14 10:14 pm (UTC)
From: [identity profile] slobin.livejournal.com
Я хотел сказать, что именно с появлением oeis, всяческих символических вычислялок и всего такого прочего, стало особенно интересно искать задачки, на которых ломается "интуитивная индукция" -- когда какое-нибудь свойство (например, совпадение двух последовательностей) соблюдается, соблюдается, а потом вдруг раз и перестаёт. Элементе этак на сороковом. Я такие примеры несколько раз находил и даже куда-то перепощивал, но, боюсь, собрать коллекцию как-то не догадался. :-( Правда, не уверен, что у меня были примеры именно на комбинаторику.

... Ускорение темпов роста повышения производительности труда ...

Date: 2012-09-15 08:24 am (UTC)
ext_605364: geg MOPO4 (geg_MOPO4)
From: [identity profile] gegmopo4.livejournal.com
Да, помню, очень красиво. Если есть примеры с интегрированием, то есть и на комбинаторику — это же суммирование, практически целочисленное интегрирование. Пример такой последовательности — площадь пересечения какой-нибудь трёхмерной фигуры плоскостью, в зависимости от её положения и наклона. При небольшом изменении параметров будет одна простая аналитическая формула, а при пересечении вершины или ребра — другая. В комбинаторике то же самое, но вдискретном пространстве.

Date: 2012-09-15 01:02 pm (UTC)
From: [identity profile] slobin.livejournal.com
Коллекции, как я уже говорил, нет, но вот тут есть несколько интересных примеров. (...) Ух ты! А pdf-ку по первой ссылке я в прошлый раз как-то протормозил скачать и посмотреть! Судя по первой странице, авторы как раз про это ("интуитивная индукция" и вообще использование мощных, но тупых вычислялок) пишут. Пошёл читать.

... Семнадцатая пятилетка ...

Date: 2012-09-15 07:35 am (UTC)
ext_605364: geg MOPO4 (geg_MOPO4)
From: [identity profile] gegmopo4.livejournal.com
Спасибо, интересно. И последовательности, которые возникают в этой задаче оно находит.

Date: 2012-09-15 01:04 pm (UTC)
From: [identity profile] slobin.livejournal.com
Я в своё время практически одновременно открыл для себя oeis и tineye, и с тех пор они у меня в голове служат примерами полезных "неканонических" искалок. :-)

... И они хитрили, и Аллах хитрил, а Аллах - величайший из хитрецов! ...

Date: 2012-09-14 11:25 pm (UTC)
From: [identity profile] http://users.livejournal.com/_winnie/
пусть есть разбиение на слагаемые
упорядочим слагаемые по порядку
вычтем из упорядоченных слагаемых 1, 2, 3, 4 ... m
получим набор m положительных чисел, сумма которых равна n - (1+2+...+m)
поэтому кол-во разложений на разные слагаемые - равно количеству разложений на любые слагаемые, без ограничения на разноту, числа n - m(m+1)/2
поскольку среди слагаемых могут быть и нули, то задача формулируется как google "Number of partitions of n into at most k parts"

Чуть подробней про равенство разных формулировок. Строится взаимно-однозначное соответствие разбиений на m разных положительных слагаемыех (твоя задача) и разбиений на m не более чем слагаемых.

Например, если m=4, то число 6 можно представить как два слагаемых, 3+3
Запишем как 4 возрастающих слагаемых с нулями впереди:
0+0+3+3
превратим это в разбиение на 4 разных слагаемы числа 6+m(m+1)/2 = 16:
(0+1)+(0+2)+(3+3)+(3+4) = 6+10 = 16

Гугл выдает некрасивые точные формулы в виде многочленов со случайными рациональными коэффициентами или же красивые generating ряды 1/((1-x)*(1-x^2)*(1-x^3)*...*(1-x^m))

Date: 2012-09-15 07:55 am (UTC)
ext_605364: geg MOPO4 (geg_MOPO4)
From: [identity profile] gegmopo4.livejournal.com
Не понял, какое это имеет отношение.

Date: 2012-09-15 10:11 am (UTC)
From: [identity profile] http://users.livejournal.com/_winnie/
Производящие функции или эквивалентность двух формулировок?
Edited Date: 2012-09-15 10:12 am (UTC)

Date: 2012-09-15 03:10 pm (UTC)
ext_605364: geg MOPO4 (geg_MOPO4)
From: [identity profile] gegmopo4.livejournal.com
Какое отношение имеют эти рассуждения к задаче? 6 можно представить и как 4 + 2, но разбиение (0 + 1) + (0 + 2) + (4 + 3) + (2 + 4) = 1 + 2 + 7 + 6 получается то же, что и при разложении 6 на 3 + 3. Я что-то по-видимому не понимаю?

Date: 2012-09-15 05:30 pm (UTC)
From: [identity profile] http://users.livejournal.com/_winnie/
А ты представь не как 4+2, а как 2+4. 0+0+2+4. Соответствующее разбиение будет 1+2+5+8 = 16.

пусть есть разбиение на слагаемые
упорядочим слагаемые по порядку
.....
Запишем как 4 возрастающих слагаемых с нулями впереди:
Edited Date: 2012-09-15 05:36 pm (UTC)

Date: 2012-09-15 06:42 pm (UTC)
ext_605364: geg MOPO4 (geg_MOPO4)
From: [identity profile] gegmopo4.livejournal.com
Не пойму, как это приближает к решению задачи.

Date: 2012-09-15 07:04 pm (UTC)
From: [identity profile] http://users.livejournal.com/_winnie/
После нахождения эквивалентности можно набрать в гугле "Number of partitions of n into at most k parts"

Profile

gegmopo4: (Default)
gegmopo4

May 2015

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930
31      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Oct. 17th, 2017 09:31 am
Powered by Dreamwidth Studios